基于Q學習的無線傳感網絡自愈算法

卞 輝，范新南，巫 鵬，顧麗萍，李威龍，鄭慶元

（1.河海大學 計算機與信息學院，江蘇 常州 213022；2.江蘇鑫源煙草薄片有限公司 江蘇 南京 223002）

基于Q學習的無線傳感網絡自愈算法

卞 輝1，范新南1，巫 鵬1，顧麗萍1，李威龍1，鄭慶元2

（1.河海大學 計算機與信息學院，江蘇 常州 213022；2.江蘇鑫源煙草薄片有限公司 江蘇 南京 223002）

無線傳感網絡存在關鍵區域節點能量消耗過快，節點能量供應有限以及通信鏈路擁塞等問題，容易造成節點故障和路由破壞。為減小上述問題對網絡傳輸造成的影響，提出一種基于Q學習的無線傳感網絡自愈算法，通過引入Q學習的反饋機制，動態感知網絡的狀態信息，當故障發生時，自適應地選擇恢復路徑，保證數據實時順利傳輸。仿真結果表明，該算法降低了錯誤選擇故障或擁塞路徑的概率，在故障感知、故障恢復和延長網絡壽命等方面，表現出了良好的性能。

無線傳感網絡；Q學習；自愈算法；故障恢復

無線傳感器網絡（Wireless Sensor Network，WSN）是由具有感知、處理和無線通信能力的傳感器節點通過自組織方式形成的網絡[1]，傳感器節點通過采集環境變量并將它們傳送給匯聚節點（也稱目標節點或Sink節點）。相對于有線網絡，傳統的單匯聚節點無線傳感網絡存在諸多問題。比如傳感器節點的電池能量供應與通信傳輸距離有限；單匯聚節點附近和關鍵路徑上節點能量消耗過快；單匯聚節點失效將導致整個網絡通信中斷無法進行重路由等。因此延長無線傳感網絡的壽命和對故障鏈路進行及時恢復成為至關重要的問題，而自愈作為一種智能化的故障恢復技術，其研究也將成為一種趨勢。

自愈通常是指網絡在發生故障的情況下，不需要人工干預，能很快地、自發地恢復受影響的傳輸路徑[2-3]。目前，無線傳感網絡的自愈技術研究還處于起步階段，主要集中在前期的故障檢測，對后續故障恢復研究的文獻并不多見。故障檢測旨在感知并且定位故障傳感器節點，其關注的重點主要是能耗和精度，主要技術有接收信號強度指示、基于到達時間、基于到達時間差和基于到達角度等方法[4-5]。故障恢復則是將故障路徑上的數據傳輸切換到另一條可承載這些數據傳輸的健康路徑上，減少由于故障對數據傳輸所造成的影響，其涉及的關鍵技術主要是重路由[6-7]。重路由對于新路徑的建立依賴于故障信息、網絡路由的策略、預定義設置以及網絡當前的狀態信息，因此其收斂時間得不到保證，導致故障恢復時間不能滿足無線傳感網絡實時有效傳輸的要求。

為克服自愈機制中重路由收斂時間慢和對故障信息檢測要求高的特點，本文提出了一種基于Q學習的無線傳感網絡自愈算法。該算法通過應用Q學習的反饋機制，將無線傳感網絡節點和路徑的狀態信息融入Q學習的反饋獎賞函數中，使得該自愈算法可以動態感知可能出現的網絡故障并自適應地選擇恢復路徑。最后進行的仿真實驗結果表明該算法能有效延長無線傳感網絡的使用壽命，并在故障感知和故障恢復方面具有一定的優勢。

1 基于Q學習的WSN自愈算法

1.1 Q學習

Q學習是一種與模型無關的強化學習算法，通過不斷“試錯”（trial and error）與環境進行交互來改善策略[8]。 Agent在其環境中執行某個動作時，環境都會給出一個反饋（獎賞或懲罰），Agent為從環境反饋中得到最大獎賞或最小懲罰而不斷改變動作，從而最終得到適合環境的最優行為。

文中提出的算法將Q學習引入無線傳感網絡的故障恢復決策中，將每個傳感器節點抽象成具有一定感知能力的Agent，自愈算法的路由選擇過程可以看成是一個馬爾科夫過程 MDP[9]，其迭代時采用狀態－動作對 Q（st，at）。 令狀態集S={s1，s2，…，sn，Sink1，Sink2，Sink3}表示無線傳感網絡中所有傳感器節點的集合， A（i）={a1，a2，…，an}表示是第 i個 Agent可用的動作集（0＜i＜n，n 為最大節點數）。Agent在狀態 st執行動作 at使得狀態變為 st+1，收到獎賞函數 r（i）。Q（st，at）的大小決定了通過行為at到達下一狀態st+1的傾向，節點Agent根據以下公式進行Q值更新[8]：

式（1）中，α∈（0，1）是學習速率，γ∈（0，1） 為折扣系數。為了得到節點的最優Q值，Agent需要不斷嘗試每個狀態動作對，本文應用Boltzmann動作選擇策略[10]，動作a被選取的概率函數為：

由式（2）可以看出，行為的選擇取決于該狀態－行為對的Q（s，a）函數和參數 τ，參數 τ是一個正的參數，稱為退火溫度參數，用來控制搜索率。大的退火參數可以使各個行為有著近似相等的被選擇概率，小的退火溫度參數使得較大的Q值函數有較大的被選擇概率。

1.2 改進的Q學習獎懲函數

傳統的Q學習獎賞函數在定義時只考慮單一因素的約束，例如跳數最少或者路徑最短，這樣帶來的問題是不能動態感知節點的能量變化。為了更加均衡的消耗能量，我們選擇下一跳中通信能量與剩余能量之比（P能耗比）最小的鄰節點進行路由；同時，本文加入網絡質量的Qos參數，選擇其中的時延（delay）和丟包率（P丟包率）作為自愈技術恢復連接實時性和有效性的參數。將這些約束參數融入Q學習的獎賞函數中。當節點i通過動作選擇策略到達下一節點時，定義收到的立即反饋函數為：

式（3）中 w1、w2和w3為權系數，其中丟包率與節點的剩余能量呈指數關系。WSN中，有些數據業務傳輸實時性要求高，有些數據業務傳輸要求能耗少，調整權系數的大小可以響應不同業務數據傳輸的需求，獎賞函數越大，說明向該節點路由的“趨勢”就越強。

1.3 算法流程

Step1路徑建立過程：在傳輸數據之前，源節點不斷向鄰居節點廣播學習消息，各個鄰節點不斷地向下一個鄰節點發送學習消息直到抵達匯聚節點。學習消息中記錄節點的獎賞值、Q評估值、傳輸延遲以及能量信息，考慮到這些網絡狀態的特征信息可以人為定義，那么可以把其定義為一個數值，這樣廣播學習消息傳送需要的能量可以忽略不計。

Substep1匯聚節點將收到的網絡狀態信息反饋給源節點，源節點根據Q學習公式（1）記錄并更新各個節點的Q值，這樣從源節點到匯聚節點間各節點的Q值就逐步迭代出來，建立Q表。

Substep2源節點根據Q表定制路徑傳輸路徑的優先級順序表格，選擇節點最大Q值所對應的動作建立最優傳輸路徑。

Step2業務傳輸過程：源節點按照最優路徑進行數據傳輸，數據在傳輸過程中記錄所經過節點的能耗和時延信息。數據到達匯聚節點后，將記錄的路徑節點信息進行整合并反饋給源節點。源節點根據公式（1）和公式（3）更新Q表，從而對下一次傳輸的路徑優先級順序進行更新。

Step4故障恢復過程：在傳輸時選擇的最優路徑出現故障節點或者發生路徑擁塞時，源節點依據路徑優先級順序選擇次優的路徑作為數據傳輸的恢復連接；如果優先級次優的傳輸路徑也無法進行有效傳輸，那么按優先級順序選擇下一個通信鏈路進行恢復連接，以此類推。

2 仿真與實驗分析

2.1 網絡模型

本文將提出的基于Q學習的無線傳感網絡自愈算法應用于多匯聚節點的無線傳感網絡[11]，網絡模型如圖1所示。

圖1 WSN網絡拓撲示意圖Fig.1 Network topology of WSN

圖1中，為方便計算將每個傳感器節點的剩余能量標示在節點的旁邊，用Ri表示；同時假設鏈路上的值為兩節點間傳輸所需要消耗的能量，比如源節點和V2節點之間傳輸的能量消耗為2。

2.2 建立動態路由表

文中用Visual Studio 2010對該算法進行仿真。通過基于Q學習的無線傳感網絡自愈算法，在第一個周期我們得到15條路徑，依據傳感器節點Q值大小建立路徑傳輸的優先級表格，仿真參數與結果如表1所示。

表1 路徑傳輸參數以及優先級順序Tab.1 Parameters of path transmission and Priority order

查詢優先級表格可知，源節點在第一周期依據優先級表格選擇“1-4-6-7-Sink3”作為最優路徑傳輸；假設數據傳輸過程中，V6節點發送故障或者發生擁塞，那么源節點將自適應地選擇Q值次優的鏈路進行恢復連接，即以1-4-3-Sink3作為恢復連接。

2.3 實驗分析

需要特別說明的是，相對于傳統以故障檢測為前提的故障恢復模式[12]，本文提出的算法根據Q學習的反饋機制，在感知故障的同時進行重路由傳輸，并不需要對故障進行精確的定位，因此缺少同類的自愈機制進行比較。在仿真中，本文將采用靜態路由中的最小能量消耗路由算法作為自愈機制中重路由的比較算法進行性能分析。

2.3.1 網絡使用壽命

我們增加對最小能量消耗路由算法的性能分析，根據網絡拓撲圖2，在傳輸過程中路徑能量的傳輸消耗為：

Cost（源->Sink1）=cost（源->V5）+cost（V5-Sink1）=5+2=7；

Cost（源->Sink2）=cost（源->v4）+cost（V4->V6）+cost（V6->V9）+cost（V9->Sink2）=1+1+3+1=6；

Cost（源->Sink3）=cost（源->V2）+cost（V2->Sink3）=2+3=5。

根據該算法，我們選擇“源-2-Sink3”作為該算法傳輸數據的最優路由。由于節點V2的剩余能量限制，數據傳輸的次數為。先考慮第一個周期T=1，基于Q學習的自愈算法傳輸最優路徑為“源-4-6-7-Sink3”，若一直沿該路徑發送數據，數據傳輸的次數為10/1=10。相比最小能量消耗路由算法，傳輸的次數增加了，延長了節點的使用壽命。該實例只是分析一個周期的路由結果，隨著Agent繼續進行數據傳輸，節點的剩余能量將發生變化，本文算法反饋給下一周期傳感器節點計算得到的Q值也將自適應變化。為了更直觀地比較兩種算法對無線傳感網絡壽命的影響，我們觀察從無線傳感網絡開始工作直至第一個無線傳感器節點失效所經過的傳輸次數。圖2所示顯示兩種算法在不同匯聚節點數目時的傳輸輪次。

圖2 兩種算法網絡使用壽命Fig.2 The network operation life of two algorithms

由圖2可以看出，當匯聚節點唯一時，兩種算法的使用壽命相同，這是因為單匯聚節點無線傳感網絡的最優路徑是唯一的。隨著匯聚節點的增加，每個傳感器節點到達匯聚節點的平均距離逐漸減少，則傳輸所消耗的能量也相應減少，從而延長了網絡的使用壽命。本文算法在源節點選擇路徑時，根據上一周期傳輸結束時網絡的狀態信息更新節點的Q值，一定程度上避免了使用剩余能量較少的傳感器節點進行數據傳輸，因此網絡的能量消耗更加均衡。而最小能量消耗路由算法只根據靜態路由表進行路由，缺少對路徑剩余能量和傳輸消耗的感知能力，導致各路徑的能量消耗不均衡，網絡資源利用率偏低。

2.3.2 故障恢復

文中提出的自愈算法，在每次數據傳輸之后，匯聚節點與源節點之間通過反饋機制來感知網絡當前的狀態，因此，本文算法具備故障感知的能力。令:

φ值越小說明自愈算法感知故障的能力越強，反之則越弱。靜態路由算法沒有引入反饋機制，缺少對網絡實時狀態的感知能力。仿真結果如圖3所示。其中，AF業務代表有效性要求高的數據傳輸，BF業務代表實時性要求高的數據傳輸。可以明顯看出本文算法故障感知能力更強。

在傳輸過程中，當數據傳輸失敗即選擇了故障路徑時，源節點會按照路徑優先級重新選擇路徑進行恢復連接。如果重新選擇的路徑不能滿足數據傳輸的要求或者仍然選擇了故障路徑，則認為傳輸恢復失敗，反之認為數據傳輸恢復成功。因此，傳輸恢復失敗率可以表示為：

圖3 兩種算法的故障感知性能Fig.3 Performance of two algorithms in fault-aware

仿真結果如圖4所示，當單匯聚節點無線傳感網絡的匯聚節點失效或故障時，網絡無法進行重路由，兩種算法的恢復失敗率是相同的；隨著匯聚節點個數的增加，無線傳感網絡的恢復連接有更多的路徑選擇，因此恢復失敗率迅速下降。同時，本文算法加入Q學習的反饋機制，具備感知故障的能力，降低了選擇發生故障和擁塞路徑的概率，使得故障恢復率顯著降低。

圖4 兩種算法的恢復失敗率Fig.4 Fault recovery rate of two algorithms

3 結 論

文中提出的基于Q學習的無線傳感網絡自愈算法，加入了Q學習的反饋機制，不僅優化了數據傳輸時的路由選擇和節點能量消耗，還可以動態地感知網絡狀態信息的變化和可能發生故障的鏈路.當網絡出現故障時，本文算法可以自適應地選擇次優路徑進行恢復傳輸，一定程度上緩解了傳統自愈機制對故障檢測技術依賴過高的問題。仿真結果表明，該算法有效地延長了網絡壽命，提高了無線傳感網絡自愈機制的智能性與實時性，在故障感知和故障恢復方面具有一定的優勢。

[1]孫利民，李建中，陳渝，等．無線傳感器網絡[M]．北京：清華大學出版社，2005.

[2]Salaha A，Ahmed E，Osameh M.Network protection codes:Providing self-healing in autonomic networks using network coding[J].Computer Networks，2012:99-111.

[3]Jorgr L，Gomes T．Survey of recovery schemes in MPLS networks[C]//2006 International Conference on Dependability of Computer Systems，Szklarska Poreba，Poland，2006．

[4]RaoA，RatnasamyS，PapadimitrouC．Geographicroutingwithout location information [C]//Proceedings of ACM MOBICOM 2003，2003：96-108.

[5]Doherty L，Pister K S J，Elghaoui L.Convex position estimation in wireless sensor networks[C]//INFOCOM2001．Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，IEEE，2001，3：1655-1663.

[6]Grerin R，William D，Orda A．QoS routing mechanisms and 0SPF extensions[C]//1997 Global Telecommunications Conference，Phoenix，1997．

[7]Ke Y，Copeland G A．Scalability of routing advertisement for QoS routing in an IP network with guaranteed QoS[C]//2000 Global Telecommunications Conference，IEEE，2000:605-610．

[8]章韻，王靜玉，陳志．基于Q學習的無線傳感器網絡自組織方法研究[J]．傳感技術學報，2010，23（11）：1623-1626．

ZHANG Yun，WANG Jing-yu，CHEN Zhi.A self-organizing method based on Q-learning for wireless sensor network[J].Journal of Transduction Technology，2010，23（11）:1623-1626.

[9]陳志，王汝傳，孫力娟．一種無線傳感器網絡的Agent系統模型[J]．電子學報，2007，35（2）：240-243．

CHEN Zhi，WANG Ru-chuan，SUN Li-juan.An agent system model for wireless sensor network[J].Chinese Journal of Electronics，2007，35（2）:240-243.

[10]Sutton R S，Barto A G．Reinforcement learning：an introduction[M].IEEE Transactions on neural networks，1998:1054．

[11]CHUANG Shun-yu，CHEN Chien，JIANG Chang-jie.Minimumdelay energy-efficient source to multisink routing in wireless sensor networks[J].Journal of Systems and Software，2012:2459-2469．

[12]劉一田，孔震，李萌.Web應用中故障檢測機制的研究與改進[J].陜西電力，2012（11）：66-69.

LIU Yi-tian,KONG Zhen,LI Meng. Research and improvementoffailure detection mechanism forWeb applications[J].Shaanxi Electric Power，2012（11）：66-69.

A self-healing algorithm based on Q-learning for wireless sensor network

BIAN Hui1， FAN Xin-nan1， WU Peng1， GU Li-ping1， LI Wei-long1， ZHENG Qing-yuan2
（1.Computer and Information College， Hohai University， Changzhou 213022， China；2.Jiangsu Xinyuan Tobacco Sheet LTD， Nanjing 223002， China）

Wireless Sensor Network has some disadvantages，such as excessive energy consumption of nodes on the key path ，limited energy supply of nodes，and communication link congestion.These problems will cause the fault of nodes and damage of routing.To reduce the influence on network transmission，a self-healing algorithm based on Q-learning is proposed for wireless sensor network.In this algorithm，a feed back mechanism of Q-learning is introduced，to perceive the status of network dynamically and select a recovery routing automatically，which can ensure the data transmission is successful.The experimental results show that the proposed algorithm can reduce the probability of selecting the failure and congestion path.The proposed algorithm has some good performances in fault-aware， fault recovery， and extending network life.

wireless sensor network；Q-learning；self-healing algorithm；fault recovery

TP393

A

1674－6236（2013）04-0044-04

2012-10-22稿件編號201210142

卞 輝（1986—），男，江蘇蘇州人，碩士。研究方向：物聯網信息安全。