李滎++王芳++景棟盛++朱斐

摘 要：針對傳統(tǒng)路由算法不能很好解決無線傳感器網(wǎng)絡(luò)的能量消耗和負載均衡的問題，提出一種將路徑跳數(shù)和能量消耗因素考慮在內(nèi)的基于Q學(xué)習(xí)的能量負載均衡算法。通過多跳和殘余能量來估計網(wǎng)絡(luò)狀態(tài)，從而找到復(fù)雜度最低的最優(yōu)路由策略，得到的數(shù)據(jù)傳輸路徑滿足能量消耗最小與負載均衡兩個條件，在降低網(wǎng)絡(luò)能量消耗的同時也延長了網(wǎng)絡(luò)的生存周期。實驗結(jié)果表明了算法在節(jié)點存活個數(shù)、節(jié)點剩余能量分布和節(jié)點發(fā)送成功率方面均取得較好的效果，同時驗證了算法可以降低能量消耗，延長網(wǎng)絡(luò)的整體壽命。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò) ；Q學(xué)習(xí)；路由；能量負載均衡

中圖分類號：TP311.5 文獻標(biāo)識碼：A

Abstract： Aiming at dealing with the problems of energy consumption and load balancing in wireless sensor networks that traditional routing algorithm cannot solve， a new energy load balancing algorithm based on Q-learning is proposed， which takes into account the number of hops， the residual energy of sensor nodes and the node energy consumption， to estimate the state of the network through multi hop and residual energy， and find the optimal routing strategy with the lowest of the complexity. The data are transferred along routine with minimum the energy consumption and the balanced load， thus reducing network energy consumption and prolong the network life cycle. The simulation results showed that the algorithm has a good effect in survival nodes， transfer success rate and residual energy distribution and transmission， which indicates that the algorithm can effectively reduce energy consumption and prolong the network lifetime.

Key words： wireless sensor network Q learning routing energy-efficient load-balancing

1 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）由傳感器節(jié)點組成，其計算和交互信息的能力受到約束 [1]。無線傳感器網(wǎng)絡(luò)的工作方式主要是傳感器節(jié)點采集環(huán)境中的信息的同時通過轉(zhuǎn)發(fā)機制最終把這些信息傳遞到稱之為Sink節(jié)點[2]的網(wǎng)關(guān)節(jié)點或匯聚節(jié)點，接著通過微波、衛(wèi)星通信或其他方式將匯集到的信息傳送到一個主要的位置，直至到達觀測者的接收終端。在整個信息的傳送過程中，中間的傳感器節(jié)點需要根據(jù)當(dāng)前的狀態(tài)來選擇下一跳的節(jié)點。然而，從整體和長期來看，全局信息的缺乏使得所選擇的下一跳轉(zhuǎn)發(fā)節(jié)點往往未必最佳的。所以，人們更加關(guān)注無線傳感器網(wǎng)絡(luò)的路由問題。

在無線傳感器網(wǎng)絡(luò)中，Sink節(jié)點附近需要比其他節(jié)點轉(zhuǎn)發(fā)更多的數(shù)據(jù)包，從而引起不均勻的網(wǎng)絡(luò)節(jié)點能量消耗。由于這個限制在傳統(tǒng)的網(wǎng)絡(luò)路由算法中很少被考慮到，這往往會導(dǎo)致靠近Sink節(jié)點或者關(guān)鍵路上的節(jié)點由于過早消耗完能量而提前“死亡”，進而整個網(wǎng)絡(luò)的功能受到較大影響。另一方面，無線傳感器網(wǎng)絡(luò)較高的動態(tài)性使得節(jié)點間需要頻繁交換信息以便節(jié)點了解網(wǎng)絡(luò)的動態(tài)變化情況。

無線傳感器網(wǎng)絡(luò)路由算法是一個多目標(biāo)優(yōu)化問題：在保證節(jié)點能實時掌握網(wǎng)絡(luò)動態(tài)情況的前提下，保證信息發(fā)送的正確性并盡可能發(fā)送最小數(shù)量的數(shù)據(jù)包以減少能耗，并從網(wǎng)絡(luò)整體的角度延長網(wǎng)絡(luò)的生命期。近年來，針對由于節(jié)點提前死亡而導(dǎo)致網(wǎng)絡(luò)生存周期短的問題，很多相關(guān)的算法被研究人員所提出。算法EAMHR[3]實現(xiàn)了能量跳數(shù)最小路由，但未能從網(wǎng)絡(luò)的整體角度考慮均勻分配節(jié)點能量消耗。Ileri等人[4]將貨幣機制引入無線傳感網(wǎng)，節(jié)點間在通信時支付一定的“貨幣”作為代價，但是由于其方法要求節(jié)點頻繁的協(xié)商，在加劇了鏈路的負擔(dān)的同時也增加了節(jié)點能量的消耗。李響等人[5]提出一種基于能量感知的多路徑路由算法，但是其路徑維護的方法較為復(fù)雜。賈杰等人[6]提出了一種基于博弈論的路由策略。但是，由于需要掌握的全局節(jié)點信息比較多，而傳感器節(jié)點的存儲和計算能力有限，因此，其方法實用性有限。董國勇等人[7]提出了一種基于蟻群算法的能量均衡路由算法，但是派遣螞蟻會造成通信開銷和網(wǎng)絡(luò)額外負載。

針對能量消耗不均衡而導(dǎo)致的網(wǎng)絡(luò)生存周期短的問題，本文提出了一個基于Q學(xué)習(xí)的無線傳感網(wǎng)絡(luò)路由算法，該算法在保證把信息經(jīng)過傳感節(jié)點轉(zhuǎn)發(fā)到Sink節(jié)點的前提下，能夠找出能源消耗和性能的最優(yōu)平衡點。算法以全局網(wǎng)絡(luò)作為著眼點進行優(yōu)化，網(wǎng)絡(luò)中的節(jié)點交換剩余能量，彼此之間的狀態(tài)-動作對和功能以協(xié)作的方式進行協(xié)調(diào)，使得整個網(wǎng)絡(luò)的生存周期最長。本文余下的內(nèi)容組織如下：首先，介紹強化學(xué)習(xí)一些相關(guān)工作和相關(guān)路由算法；然后，給出算法建模過程和詳細描述；接著，進行仿真實驗，給出結(jié)果和相關(guān)分析；最后，給出結(jié)論。

2 相關(guān)工作

2.1 無線傳感器路由

路由的選擇是無線傳感網(wǎng)絡(luò)的基礎(chǔ)。根據(jù)無線傳感網(wǎng)絡(luò)自身的特點而進行的路由優(yōu)化通常需要針對以下幾點：（1）尋找路由中距離最短的傳輸路徑；（2）均衡、調(diào)節(jié)節(jié)點負載，延長網(wǎng)絡(luò)壽命；（3）使節(jié)點能及時了解網(wǎng)絡(luò)的動態(tài)變化；（4）即使一條傳輸線路中斷，節(jié)點仍然可以將信息傳輸?shù)侥康墓?jié)點。為了提高能量受限的無線傳感網(wǎng)絡(luò)的生存周期來實現(xiàn)網(wǎng)絡(luò)的均衡負載，通常把負載調(diào)整到不同的路徑或者節(jié)點，這樣能量消耗在各節(jié)點中得到平衡。通常，路由算法既要使傳輸所消耗的能量最小，又要盡可能避開那些剩余能量較少的節(jié)點，從而延長其壽命，達到最大化網(wǎng)絡(luò)生存時間的目的?？偟膩砜?，無線傳感網(wǎng)絡(luò)的路由算法主要可以分為以下兩類。

3 基于Q學(xué)習(xí)的能量負載均衡路由

當(dāng)前的節(jié)能路由模型很少把降低能耗和負載均衡很好的綜合起來考慮，并且解決問題的思路相對比較片面，往往需要通過計算整條路徑上的消耗值來實現(xiàn)路由的選擇。為了解決當(dāng)前路由模型的不足即實現(xiàn)最小化能量消耗的同時也考慮均衡節(jié)點的負載，本文提出一種基于Q學(xué)習(xí)的能量負載均衡的路由算法（Q-learning based energy-efficient load-balancing routing，Q-E2LBR）。Q-E2LBR算法利用強化學(xué)習(xí)的思想建模，充分考慮多跳和殘余能量來達到最小化整體能量開銷和最大化網(wǎng)絡(luò)的生存周期。Q-E2LBR算法使數(shù)據(jù)包沿一個接近最優(yōu)的路徑轉(zhuǎn)發(fā)到Sink節(jié)點并使用一個節(jié)點不斷地記錄它相鄰節(jié)點的Q值且能夠在獲得包的時候立即更新它，當(dāng)前節(jié)點的Q值在其相鄰節(jié)點的副本中評估，由于無需反饋數(shù)據(jù)包，減少了數(shù)據(jù)通信量并延長了網(wǎng)絡(luò)的生命周期。

3.1 模型和算法描述

無線傳感網(wǎng)中每個傳感器節(jié)點都具有一定的計算能力和存儲能力，將這些特點考慮進來，就可以得到與之前的算法不同的方法。在本文所提出的算法中，無線傳感網(wǎng)絡(luò)中的每一個傳感器節(jié)點都被視為一個agent，這樣整個無線傳感網(wǎng)絡(luò)就可以建模成一個多agent系統(tǒng)；每個agent在其鄰居節(jié)點中選擇不同的節(jié)點，作為下一跳節(jié)點，從而構(gòu)造出最優(yōu)路徑。通過不斷地取樣和學(xué)習(xí)，Q值將會最終收斂到一個穩(wěn)定的值。將整個無線傳感器網(wǎng)絡(luò)作為一個多agent系統(tǒng)。為了找到最優(yōu)路徑，每一個agent選擇一個最優(yōu)的鄰接節(jié)作為下一個路由目標(biāo)。

無線傳感器網(wǎng)絡(luò)可以被描述為多個agent的強化學(xué)習(xí)問題。在某種意義上來說，學(xué)習(xí)網(wǎng)絡(luò)路由的最優(yōu)控制可以被視為和其他agent迭代并行的學(xué)習(xí)一個情節(jié)的任務(wù)。假設(shè)有多個節(jié)點的無線傳感器網(wǎng)絡(luò)隨機部署在一個特定的區(qū)域具有以下特點：（1）所有傳感器有能量限制；（2）任何傳感器和接收器之間需要通過一跳或者多跳通信；（3）傳感器的發(fā)射功率保持穩(wěn)定；（4）傳感器可以獲得自身的信息和相鄰節(jié)點的信息。

3.2 模型設(shè)計

強化學(xué)習(xí)算法需要對狀態(tài)、動作和獎賞函數(shù)進行建模。接下來介紹算法各元素的建模過程。

在無線傳感器網(wǎng)絡(luò)中，狀態(tài)是指某個節(jié)點ni的自身信息及其所有鄰接節(jié)點的信息。一個無線傳感器網(wǎng)絡(luò)由多個節(jié)點所構(gòu)成，其網(wǎng)絡(luò)狀態(tài) 是所有節(jié)點狀態(tài)的集合。在t時刻，無線傳感器網(wǎng)絡(luò)處于狀態(tài)S，則傳感器節(jié)點ni選擇動作 ，表示其選擇節(jié)點nj作為信息接收點，傳輸路徑為節(jié)點ni直接連接到節(jié)點nj的信道。由于強化學(xué)習(xí)方法采用Q值評估狀態(tài)-動作，所以此時選擇最高的Q值所對應(yīng)的動作。

本文提出的Q-E2LBR算法在能量消耗最小化的同時均衡網(wǎng)絡(luò)節(jié)點的負載均衡。因此在設(shè)計獎賞函數(shù)時，需要考慮在路徑REt的剩余能量，從源節(jié)點到目標(biāo)節(jié)點的跳數(shù)H以及在節(jié)點ni和節(jié)點nj之間傳輸所耗費的能量 。一個節(jié)點獲得一個立即獎賞并轉(zhuǎn)發(fā)一些數(shù)據(jù)包之后，對于剩余能量的值、能量消耗和必要的Q值進行編碼，使得在其數(shù)據(jù)包到達目標(biāo)節(jié)點后得到一個額外的目標(biāo)獎勵。

3.3 算法描述

在學(xué)習(xí)階段，Sink節(jié)點在特定的時間內(nèi)傳播啟動數(shù)據(jù)包并在其中封裝了能量信息和跳計數(shù)，初始化Q值為0；然后，每個節(jié)點從相鄰的節(jié)點得到學(xué)習(xí)信息，包括了相鄰節(jié)點的Q值、無線傳感網(wǎng)絡(luò)中的跳數(shù)、節(jié)點能量消耗情況；接著，以滿足Boltzmann分布的概率選擇動作；隨后，將跳數(shù)信息、獎賞信息和剩余能量信息存入模型中并在模型中進行動作值函數(shù)的迭代更新；Sink節(jié)點周期性地向鄰居節(jié)點發(fā)送學(xué)習(xí)消息使得每個節(jié)點可以轉(zhuǎn)發(fā)接收到的學(xué)習(xí)消息并且更新模型；最后，Sink節(jié)點周期性地向鄰居節(jié)點發(fā)送學(xué)習(xí)消息，各鄰居節(jié)點不斷地向下一個節(jié)點發(fā)送學(xué)習(xí)消息的同時各節(jié)點不斷更新內(nèi)部模型，通過不斷的迭代，評估值就逐步接近收斂。具體如算法1所示。

算法1 基于Q學(xué)習(xí)的能量負載均衡的路由算法（Q-learning based energy-efficient load-balancing routing，Q-E2LBR）

輸入：能量信息E

輸出：路由路徑R

1： 初始化：Q←0，路由R←null，跳數(shù)hop←0，RE←0

2： for all 節(jié)點

3： for節(jié)點 i 的所有相鄰節(jié)點

4： 節(jié)點i 從相鄰節(jié)點j獲得的Q值

5： 計算得到節(jié)點i到下一Sink節(jié)點的跳數(shù)hop（i）

6： 計算從節(jié)點i的開始的總跳數(shù)H

7： 計算跳數(shù)關(guān)于節(jié)點i能量的消耗

8： 計算獎賞函數(shù)

9： 采取動作a，觀察a和s

10：

11：

12： for節(jié)點 i 的所有相鄰節(jié)點

13： 計算節(jié)點i選擇節(jié)點j的作為下一個發(fā)送節(jié)點的概率

14： end for

15： 選擇pi，j最大的節(jié)點j作為下一個發(fā)送節(jié)點

16： 更新能量E←E - Eh

17： if 節(jié)點j加入后不會有環(huán)

18： 將節(jié)點j加入到路由R中

19： end if

20： end for

21： return R

本文的算法在傳統(tǒng)算法的基礎(chǔ)上綜合考慮了跳數(shù)、節(jié)點能量消耗等情況，由于傳統(tǒng)的考慮能量的算法仍需要計算能量值，因此，本文的算法并沒有過多的增加計算量，計算復(fù)雜度沒有明顯增加。

4 仿真實驗與結(jié)果

本文使用NS2網(wǎng)絡(luò)[15]評估算法。模擬環(huán)境是一個長寬都為100米的矩形區(qū)域，且存在100個傳感器節(jié)點被隨機部署在這個區(qū)域中。傳感器的最大通信距離是15米，每個節(jié)點最初的能量均服從均勻分布區(qū)間[6000，10000]。平均實驗結(jié)果從100次模擬的不同拓撲結(jié)構(gòu)中獲得。

在無線傳感器網(wǎng)絡(luò)中，GT算法是一種效果比較好的經(jīng)典算法[16]，因此本文實驗從3個方面將Q-E2LBR算法和GT算法進行比較：節(jié)點的生存數(shù)，剩余能量分布和節(jié)點和傳輸成功率。

圖1顯示了在5分鐘內(nèi)Q-E2LBR算法和GT算法的存活下來的節(jié)點。Q-E2LBR算法存活的節(jié)點數(shù)量明顯多于GT算法并且隨時間的推移差距越來越大。圖1的結(jié)果說明在節(jié)點生存數(shù)方面，Q-E2LBR算法優(yōu)于GT算法。從圖1還可以看出，Q-E2LBR算法在給定的300秒時間內(nèi)的節(jié)點存活量高于GT算法，因此可以分析得出，Q-E2LBR算法所需額外的計算能量在各節(jié)點所能提供的計算能量的范圍之內(nèi)。

圖2給出了5分鐘內(nèi)Q-E2LBR算法和GT算法運行了一段時間后的結(jié)果。Q-E2LBR算法的能量傳播比GT算法在整個網(wǎng)絡(luò)過程中要更加均勻，這表明了在Q-E2LBR算法中路徑選擇更加合適。Q-E2LBR算法從節(jié)點的剩余能量的改變中選擇了路由路徑。盡管GT算法也考慮了能量的均勻性，但其能量流失速度高于Q-E2LBR算法。由于無線傳感器網(wǎng)絡(luò)中，節(jié)點的計算量越大，其存活時間越短，圖2的結(jié)果說明在剩余能量分布方面，Q-E2LBR算法好于GT算法。從圖2還可以看出，Q-E2LBR算法在給定的300秒時間內(nèi)的節(jié)點剩余能量高于GT算法，因此可以分析得出，Q-E2LBR算法優(yōu)化了網(wǎng)絡(luò)所節(jié)省的節(jié)點所需的計算能量，大于其所需要增加的計算量所需的能量。

圖3展示了Q-E2LBR算法和GT算法成功傳輸率情況。在最初30秒內(nèi)，Q-E2LBR算法傳播的成功率低于GT算法。主要原因在于Q-E2LBR算法使用了強化學(xué)習(xí)的“試錯”機制，在最初的階段，Q-E2LBR算法會有意識的嘗試“試錯式”的學(xué)習(xí)并在很短的時間內(nèi)算法學(xué)習(xí)到足夠的經(jīng)驗之后出現(xiàn)性能的一次較大提高。Q-E2LBR算法有5次傳輸質(zhì)量的提高，前3次質(zhì)量提高出現(xiàn)在100秒內(nèi)，并且提高幅度較大，后2次的質(zhì)量提高耗時較長，并且提高幅度不大，這說明Q-E2LBR算法在傳輸質(zhì)量這一指標(biāo)上能很快的向最優(yōu)值收斂后慢慢逼近。同時，從圖3中也可以看出，在給定的300秒時間內(nèi)，Q-E2LBR算法傳輸?shù)牧亢虶T算法相當(dāng)，因此可以看出，Q-E2LBR算法并沒有過多的增加計算量。整體而言，Q-E2LBR算法優(yōu)于GT算法。

4 結(jié) 論

無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點的能耗問題不統(tǒng)一導(dǎo)致節(jié)點在關(guān)鍵路徑中的Sink節(jié)點和其他節(jié)點過早死亡而導(dǎo)致了網(wǎng)絡(luò)的生命周期縮短。本文提出了一種高效節(jié)能、負載平衡的路由算法Q-E2LBR，通過Q學(xué)習(xí)計算行動狀態(tài)值函數(shù)，并通過Boltzmann分布計算行動的概率。經(jīng)過充分考慮剩余能量、能量消耗和跳數(shù)等因素后，Q-E2LBR算法能夠平衡能量消耗并延長網(wǎng)絡(luò)生命周期。模擬實驗表明，Q-E2LBR算法可以在均勻地分布網(wǎng)絡(luò)流量，改善網(wǎng)絡(luò)生命周期的同時保證有較高的傳輸成功率。

參考文獻

[1] 程紅舉， 黃行波， XIONG Naixue. 不可靠通信環(huán)境下無線傳感器網(wǎng)絡(luò)最小能耗廣播算法[J]. 軟件學(xué)報， 2014（5）：1101-1112.

[2] 韓凱州， 馬福昌. 無線傳感器網(wǎng)絡(luò)中多Sink節(jié)點位置部署研究[J]. 傳感器與微系統(tǒng)， 2014， 33（3）：37-39.

[3] Jiang H， Sun Y， Sun R， et al. Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks， 2013， 9（2）：264-273.

[4] Ileri O， Mau S C， Mandayam N B. Pricing for enabling forwarding in self-configuring ad hoc networks[J]. IEEE Journal on Selected Areas in Communications， 2005， 23（1）：151-162.

[5] 李響， 孫華志. 基于能量感知的無線傳感器網(wǎng)絡(luò)路由算法[J]. 計算機科學(xué)， 2016， 43（6）：291-294.

[6] 賈杰， 張桂園， 陳劍，等. 無線傳感器網(wǎng)絡(luò)中基于潛在博弈的分布式節(jié)點定位[J]. 電子學(xué)報， 2014， 42（9）：1724-1730.

[7] 董國勇， 彭力， 吳凡，等. 一種采用蟻群優(yōu)化的WSN能量均衡非均勻分簇路由算法[J]. 小型微型計算機系統(tǒng)， 2015， 36（7）：1565-1568.

[8] Chandane M M， Bhirud S G， Bonde S V. Energy Optimization in Wireless Sensor Network[M]// Mobile Communication and Power Engineering. Springer Berlin Heidelberg， 2013：321-331.

[9] 朱斐， 許志鵬， 劉全，等. 基于可中斷Option的在線分層強化學(xué)習(xí)方法[J]. 通信學(xué)報， 2016， 37（6）：65-74.

[10] Auer B P， Cesabianchi N， Sutton P F， et al. Reinforcement learning， an introduction[J]. Trabajos Y Comunicaciones， 2010：114-135.

[11] Lo B F， Akyildiz I F. Reinforcement learning for cooperative sensing gain in cognitive radio ad hoc networks[J]. Wireless Networks， 2012， 19（6）：1237-1250.

[12] Russell B， Littman M L， Trappe W. Integrating machine learning in ad hoc， routing： A wireless adaptive routing protocol[J]. International Journal of Communication Systems， 2011， 24（7）：950-966.

[13] Oddi G， Pietrabissa A， Liberati F. Energy balancing in multi-hop Wireless Sensor Networks： an approach based on reinforcement learning[C]// Nasa/esa Conference on Adaptive Hardware and Systems. 2014：262-269.

[14] 孫彥清， 彭艦， 劉唐，等. 基于動態(tài)分區(qū)的無線傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議[J]. 通信學(xué)報， 2014（1）：198-206.

[15] 張小慶， 李春林， 張恒喜. 無線傳感器網(wǎng)絡(luò)的NS2擴展與仿真機制研究[J]. 計算機科學(xué)， 2011， 38（8）：117-120.

[16] Kulkarni R V， Forster A， Venayagamoorthy G K. Computational Intelligence in Wireless Sensor Networks： A Survey[J]. IEEE Communications Surveys & Tutorials， 2011， 13（1）：68-96.