一種基于Q學習的無線傳感網絡路由方法

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

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

關鍵詞：無線傳感器網絡 ；Q學習；路由；能量負載均衡

中圖分類號：TP311.5 文獻標識碼：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 引 言

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

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

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

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

2 相關工作

2.1 無線傳感器路由

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

3 基于Q學習的能量負載均衡路由

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

3.1 模型和算法描述

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

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

3.2 模型設計

強化學習算法需要對狀態、動作和獎賞函數進行建模。接下來介紹算法各元素的建模過程。

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

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

3.3 算法描述

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

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

輸入：能量信息E

輸出：路由路徑R

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

2： for all 節點

3： for節點 i 的所有相鄰節點

4： 節點i 從相鄰節點j獲得的Q值

5： 計算得到節點i到下一Sink節點的跳數hop（i）

6： 計算從節點i的開始的總跳數H

7： 計算跳數關于節點i能量的消耗

8： 計算獎賞函數

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

10：

11：

12： for節點 i 的所有相鄰節點

13： 計算節點i選擇節點j的作為下一個發送節點的概率

14： end for

15： 選擇pi，j最大的節點j作為下一個發送節點

16： 更新能量E←E - Eh

17： if 節點j加入后不會有環

18： 將節點j加入到路由R中

19： end if

20： end for

21： return R

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

4 仿真實驗與結果

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

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

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

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

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

4 結 論

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

參考文獻

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

[2] 韓凱州， 馬福昌. 無線傳感器網絡中多Sink節點位置部署研究[J]. 傳感器與微系統， 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] 李響， 孫華志. 基于能量感知的無線傳感器網絡路由算法[J]. 計算機科學， 2016， 43（6）：291-294.

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

[7] 董國勇， 彭力， 吳凡，等. 一種采用蟻群優化的WSN能量均衡非均勻分簇路由算法[J]. 小型微型計算機系統， 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的在線分層強化學習方法[J]. 通信學報， 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] 孫彥清， 彭艦， 劉唐，等. 基于動態分區的無線傳感器網絡非均勻成簇路由協議[J]. 通信學報， 2014（1）：198-206.

[15] 張小慶， 李春林， 張恒喜. 無線傳感器網絡的NS2擴展與仿真機制研究[J]. 計算機科學， 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.