基于Q學習的多Sink節點無線傳感網路由機制研究*

周淑俐，章 韻，陳 志，2，3，* ，扈羅全，岳文靜

(1.南京郵電大學計算機學院，南京 210003; 2.南京大學計算機軟件新技術國家重點實驗室，南京 210093; 3.江蘇省無線傳感網高技術研究重點實驗室，南京 210003; 4.寬帶無線通信與傳感網技術教育部重點實驗室，南京 210003; 5.蘇州出入境檢驗檢疫局 江蘇蘇州 ，215104)

無線傳感網節點一般能量供應、計算和通信能力有限，在部署節點和設計各種協議時要考慮有效利用各種資源［1］。在無線傳感網中，傳感器節點采集環境變量并將它們傳送給Sink節點(網關節點或匯聚節點)，Sink節點通過無線方式接收各傳感器節點的數據并以有線或無線的方式將數據傳送給最終用戶。無線傳感網在許多領域都得到了很好的應用，但在傳統的單Sink傳感網中存在許多問題，比如靠近Sink節點或者關鍵路徑上的節點能量消耗過快，會引起節點的能量消耗不均衡;單Sink節點的失效會引起整個無線傳感網的通信中斷，當傳感網的規模不斷增加，節點數目不斷擴充，靠近Sink節點的傳感節點比其他節點消耗的能量更快，因為他們需要傳遞大量的消息，因此延長整個傳感網的壽命成了一個至關重要的問題。針對單Sink傳感網路由中存在的缺點，本文研究了多Sink傳感網的路由協議。多Sink節點傳感網特別適應于大規模的傳感網，多Sink節點會減少傳感節點到Sink節點的平均距離，減少相應的跳數，能更加均衡地消耗能量。本文在研究了多Sink傳感網路由協議的基礎上提出了一種具有一定的智能學習和適應能力的路由機制，應用增強學習［2－6］來達到尋求在多Sink傳感網中節點使用壽命最長、能量消耗均衡的最優路徑的目的。

本文介紹Q學習算法的路由選擇機制，通過實例分析說明Q學習路由機制對于延長節點壽命的作用。Q算法工作時只需利用各個節點的能量狀態信息，不增加網絡通信量，均衡了節點的能量消耗，延長了網絡的使用壽命。

1 相關工作

多Sink無線傳感網路由協議的研究目前還處于起步階段，相比單Sink路由協議具有更大的優勢:能夠避免單Sink節點失效時造成的整個傳感網的通信中斷、減輕Sink節點附近能量消耗不均衡的壓力、可在不同Sink節點間采用不同的路由算法通過不同路徑傳送數據、能夠根據不同用戶的需求控制好網絡中的數據流(圖像、聲音、視頻數據流)等。多Sink節點傳感網中，路由可以有不同的選擇，數據能夠沿不同路徑傳輸。Pietro Ciciriello［7］提出周期性的消耗適應路由協議PAMR，設想每個數據源節點到相應的Sink節點具有相互獨立的樹狀結構，從而建立源節點到相應Sink節點的路徑，該協議借鑒了多商品流網絡設計問題來解決傳感器網絡設計高效性、分散性問題，但是該協議適合于數據量較少的應用場合，而且算法過于復雜，主要解決了多源到多Sink的傳感網的分散性問題，當網絡規模較大，而且數據量比較多的情況不太適用;Meng Min提出PBR路由協議［8］，基于能量級別傳送數據，能量級別定義為節點在當前所剩能量，能夠向鄰節點傳輸數據的次數，路徑能量級別定義為一個節點到目標Sink節點整個路徑的最小能耗。該協議解決了能量均衡消耗的問題，延長了網絡的壽命，但是它適合于網絡拓撲比較簡單且Sink節點固定的情況;Chen Yue-quan 提出了 MRMS［9］多Sink節點路由協議，針對傳輸路徑選擇、高能效的動態分簇維持以及路徑切換問題，提出了一種新的基于鄰節點間距離到相應Sink的跳數以及節點剩余能量信息的路徑開銷度量算法，該協議主要應用于大規模分簇傳感網中，在傳感網的規模不大且不分層的情況算法有點復雜，不太實用。由此可見以前的很多多Sink節點傳感網路由協議都是從某一個角度來研究多Sink路由涉及的問題，考慮得更多的是節點的剩余能量，沒有很好地解決Sink節點間協調問題，以及能量的均衡消耗，或者是算法過于復雜造成能量開銷較大。它們考慮因素不全面或者計算復雜度過高，沒有考慮節點失效或者移動時的路徑選擇，而Q學習方法適合于任何規模的傳感器網絡，算法不太復雜，考慮的因素較全，如節點的剩余能量、跳數、距離等，有效的均衡了節點的能量消耗，延長了網絡的使用壽命。

2 Q學習算法

在無線傳感網中，節點在尋求最優路徑時，每個Agent都要有初始的Q值。通過信息交互基于增強學習機制尋找下一個Agent，在Q值更新過程中是基于以下方法的:

這里，γ為延遲回報與立即回報的相對比例因子(0≤γ≤1)，α(0≤α≤1)為學習因子。不同無線傳感網絡可能具有不同的資源，調控α將使Q評估值更新方法收斂。當α=1時，為確定性回報情形下的規則。此時上式變為:

第i個Agent在時間t采取的動作是確定將數據發送給哪個鄰居Agent，所得的回報就來自該鄰居Agent，一般不同的Agent具有不同的回報值，Agent在發送信息時是選擇具有最大回報值的鄰居Agent發送。從數據源節點到Sink節點能通過不斷的迭代產生具有最大Q評估值的路徑，該路徑即是最優路徑。

3 基于Q學習的多Sink網路由機制

多Sink無線傳感網路由考慮的是如何把采集到的數據根據能量有效的原則傳送到最佳的Sink節點。多Sink路由協議研究還處于起步階段，目前研究的路由協議大多存在考慮因素不全面，如未考慮關鍵路徑上節點能量消耗過快，路由算法過于復雜、節點移動或失效等，基于Q學習的路由機制能比較有效地解決能量消耗不均衡的問題。下面利用Q學習方法機制來實現能量感知路由協議，從而實現路由選擇［12－13］。

假定學習因子γ=1，為了方便討論只考慮確定性的情況，即α=1的情形。Agent綜合考慮路徑上節點的剩余能量和節點間能量消耗、跳數，每次選擇較優的Agent來傳送數據，并在每次的選擇后根據獲得的回報值選擇下一個較優的Agent。這樣從源節點到每個Sink節點都能通過不斷的迭代找到一條最佳的路徑，然后通過比較不同Sink節點的Q值，Q值高的Sink節點即為應選擇的Sink節點。學習過程如下:

(1)匯聚節點Sinkk(在這里1≤k≤3)以一定的周期向鄰居Agent廣播學習評估消息，啟動路徑建立過程。學習評估消息中包含Agent的回報值、Q評估值及能量信息，回報值的初始值設為0。

(2)Agenti收到鄰居Agentj發送的學習消息時，相對發送該消息的Agentj，只有當自己距離源節點更近而距Sinkk更遠的情況下，才需進行學習訓練，否則放棄學習。其中相關定義如下:

①定義一個D集合來存放本周期內已學習過的Agent以免出現路由環路現象;

②在WSN無線通信模型中，能量的消耗主要是進行數據傳輸。發送lbit數據包到距離為d的接收方的能量消耗為Ei，j。

在WSNs中，跳數對于節點的能量消耗也是有很大的影響的。跳數關于節點能量消耗的公式:Eh=ehop(i)/H，其中 hop(i)表示下一跳 Agentj到 Sinkk的跳數，Agenti到Sinkk的總跳數為H。

在本文中，Ei，j假定已知，故只要考慮跳數對節點能量消耗的影響即可，即只計算Eh=ehop(i)/H即可。

③Sinkk周期性地不斷向鄰居節點發送學習消息，各個鄰節點不斷地向下一個節點發送學習消息，這樣從各個Sink節點到源節點的Q評估值就逐步的迭代出來。源節點通過比較到不同路徑上的Q值，選擇Q值最大的作為通信的下一個節點把數據發送出去，從而最終把源節點的數據傳送到Sink節點，最后通過Sink節點把數據發送到計算機處理系統。該Q學習機制中，節點間通信的每一步選擇都綜合考慮了節點的通信能力、跳數、剩余能量，能從中選擇最能均衡能量、節省能量、延長節點壽命的路徑選擇路由，因而具有一定的實用價值和現實意義。

4 實例分析

假設網絡拓撲如圖1所示，用有向圖G(V，E)來表示，V代表傳感網中的各個Agent節點，V=(源節點，V1，V2，…，V9，Sink1，Sink2，Sink3)，E 代表著相鄰Agent間可通信的一條鏈路e。每個節點的剩余能量標注在每個節點的旁邊，Rj表示Agent j的剩余能量。為方便計算，我們假設鏈路e上的值表示兩節點間數據傳送所消耗的能量值(跳數因素對節點能量消耗不包含在內，另外考慮)。比如源節點和V2之間的數據傳輸的能量消耗是2，另外還要考慮跳數對節點能量的影響。為了進行性能比較，增加了多Sink傳感網中的最小能量消耗路由算法的能量消耗分析。

圖1 節點拓撲能量示意圖

基于最小能量消耗路由算法:

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。

根據該算法，我們選擇源－V2－Sink3作為傳送數據的路由。數據傳送的次數為20/3=6。

下面具體分析多Sink傳感網中基于Q學習算法的路由選擇機制。

Agent不必知道網絡的拓撲結構，只須獲得每個節點的Q值和到達下個節點的回報值，就能通過不斷地迭代找到最優路徑。通過Sink節點周期性的向源節點發送學習訓練消息更新節點的Q值表，更新規則為式(2)，Sink節點的剩余能量始終保持在40，Q的初始值設為40。

先考慮第一個周期T=1。表1所示為T=1時源節點到各個Sink節點路徑上的Q值。

表1 建立路由的Q表項＜T=1＞

π*=maxaQ(s，a)。根據Q學習算法應該選擇Q值最大的作為目標傳送的Sink節點。故應該選擇路徑為:源－V4－V6－V7－Sink3。若一直沿該路徑發送數據，傳送的次數為10/1=10。與最小能量消耗路由算法相比，數據傳送的次數增多了，網絡的壽命得到了延長。該實例只是分析了一個周期的路由選擇。隨著Agent繼續進行數據傳送，各Agent節點的能量會發生變化，這個時候源節點又會根據路由算法尋找新的路由。對于增強學習算法而言，當第二周期開始尋找路徑時，節點的剩余能量為節點原來的能量減去節點間通信消耗的能量。確定了各節點的能量后，就可以根據Q算法重新尋找最優路徑。如此循環往復，節點每次都能找到一條達到Sink節點的最優路徑。

第二周期的Q評估值的計算是在第一周期基礎上進行的，這時節點的剩余能量為第一周期節點剩余能量減去第一周期發送信息消耗的能量，即源、V4、V6、V7的節點能量有變化，其余節點能量不變。

表2 建立路由的Q表項＜T=2＞

表2表明第二周期內源－V4－V6－V7－Sink3的Q評估值仍然是最大的，故第二周期選擇的路徑沒有變。

為了比較兩個算法對傳感網網絡使用壽命的影響，需要定義一種和數據收集相關的度量標準。實例采用協作壽命來進行度量。協作壽命定義為從傳感器網絡開始工作時起到第一個傳感器節點失效時所經過的傳送數據的輪次。圖2所示是兩種算法在不同Sink節點數目時協作壽命。橫軸表示Sink節點數目，縱軸表示傳感器的協作壽命。

圖2 兩種算法生命周期比較

從圖2可以看出，在單Sink節點時采用兩種算法的傳感器網絡壽命一樣，因為單Sink節點所形成的路由路徑是唯一確定的。隨著Sink節點數目的增加傳感網的壽命有顯著的提高，因為隨著Sink節點數量的增加，每個傳感器節點到達Sink節點的平均距離就會減少，那么傳送數據所消耗的能量就會減少，從而網絡壽命要增加。另外，由于采用Q學習方法的路由機制使數據始終沿著能量消耗代價最小的路徑進行數據傳輸，在一定程度上避免了使用剩余能量少的節點轉發數據，而最小能量消耗路由路徑始終選擇的是能量消耗最少的節點發送數據，根本沒有考慮到節點的剩余能量。

Q學習算法具有衡量各節點的能量的作用，這是因為該算法具有周期性和即時性，且不以路徑上的節點能量消耗少作為唯一擇路標準，而是綜合考慮了Agent節點能量消耗、節點剩余能量值、跳數、距離等，因而相對而言考慮較為全面，能發掘出更合適的路徑出來。

5 結束語

本文研究基于Q學習的多Sink無線傳感網路由機制。該機制綜合網絡節點的剩余能量和節點間消耗能量值以及跳數、距離，通過不斷迭代找到到達各Sink節點的最優路徑。Sink節點周期性的向源節點發出學習訓練消息，各節點根據自己當時所處的狀態不斷的學習訓練，使Q值表在不斷的更新，不斷地選擇最優的路徑，因而每次傳送數據都能很好的平衡能量。該機制還能防止由于節點故障導致的路徑失效。通過實例分析，我們看出該機制相比于最小能量消耗路由算法大大延長了網絡的生命周期，并且隨著Sink節點數目的增加，Q學習方法的優勢性越來越明顯。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京;清華大學出版社，2005.1－57.

［2］姚怡，覃華，蘇一丹.基于Q-learning的自適應容錯路由算法的研究［J］.計算機工程與應用，2006(10):123－125.

［3］薛麗華，殷萇茗.多智能體協作學習方法的研究［D］:［碩士學位論文］.長沙:長沙理工大學，2008.

［4］褚建華，李大字.Q-learning強化學習算法改進及其應用研究［D］:［碩士學位論文］.北京:北京化工大學，2009.

［5］Anna Egorova-Forster，Amy L Murphy.Exploiting Reinforcement Learning for Multiple Sink Routing in WSN［C］//2007 IEEE International Conference on Mobile Ad hoc and Sensor Systems(MASS 2007)，8 October－11 October 2007:1－3.

［6］Ping Wang，Ting Wang.Adaptive Routing for Sensor Networks using Reinforcement Learning［C］//2006 The Sixth IEEE International Conference on Computer and Information Technology(CIT 2006)，September 2006:219－225.

［7］Pietro Ciciriello，Luca Mottola，Gian Pietro Picco.Efficient Routing from Multiple Sources to Multiple Sinks in Wireless Sensor Networks［J］.Computer Science，2007，4373(10):34－50.

［8］Min Meng，Xiaoling Wu，Hui Xu，et al.Energy Efficient Routing in Multiple Sink Sensor Networks［C］//2007 the Fifth International Conferenceon computerScience and Applications，Berlin:Springer.26－29 August 2007:561－566.

［9］Chen Yue-quan，Chane，Han Song.Energy Efficient Multipath Routing in Large Scale Sensor Networks with Multiple Sink Nodes［C］//Cao J，W Neidl，M Xu，des.Proc of the 6th International Workshop on Advanced Parallel Processing Techniques，Berlin:Springer.2005:390－399.

［10］Tom M Mitchell著，曾華軍，張銀奎，等譯.機器學習［M］.北京:機械工業出版社，2003.263－280.

［11］陳志，王汝傳，孫力娟.一種無線傳感器網絡的多Agent系統模型［J］.電子學報，2007.35(2):240－243.

［12］章韻，王靜玉，陳志.基于Q學習的無線傳感器網絡自組織方法研究［J］.傳感技術學報，2010.23(11):1623－1626.

［13］汪瓊，張鋒.無線傳感器網絡中的節點協作算法研究［J］.傳感技術學報，2006.19(2):481－485.