基于Q學習的多基站分簇拓撲控制算法*

閻新芳，馮　巖，王曉曉

（鄭州大學信息工程學院，鄭州450001）

基于Q學習的多基站分簇拓撲控制算法*

閻新芳*，馮巖，王曉曉

（鄭州大學信息工程學院，鄭州450001）

為了解決無線傳感器網絡中單基站附近出現的“能量空洞”和網絡時延過高等問題，引入多基站分簇拓撲控制算法。算法根據不同的場景來選擇基站數目，結合圖論和定向擴散中梯度的思想對網絡進行分簇并運用Q學習算法對簇頭節點進行周期性的學習訓練，比較到達不同基站的不同路徑上的Q值進行最優路徑的選擇。通過仿真分析表明，該算法相對于單基站分簇算法可以有效延長網絡的生命周期。

無線傳感器網絡；分簇拓撲控制；多基站；Q學習

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.04.019

無線傳感器網絡［1］WSNs（Wireless Sensor Networks）是由大量的傳感器節點部署在監測區域內，通過節點間的相互通信所組成的多跳網絡來感知周圍環境的各種信息。由于無線傳感網網絡節點一次性播撒后，節點能量不可再生，因此降低網絡能量消耗、延長網絡生存期成為傳感網路由協議的首要設計目標［2-3］。目前無線傳感器網絡核心的路由協議是分簇路由協議，而作為分簇路由協議的基礎的多級簇樹拓撲結構由于其能量高效和易于維護擴展等特點被廣泛研究和應用［4-7］。

其中基于梯度的分簇拓撲控制算法［4］ETBG （Energy-Aware Topology ProtocolBased on Gradient）根據節點的通信半徑把網絡建成一個梯度場，對同梯度等級的節點進行分簇。但該算法中節點競選簇頭的能力僅考慮能量和距離，生成簇樹的過程僅考慮單個簇頭節點的權值，沒有綜合考慮各方面的因素，未能找到最優成樹路徑。而且在大規模的無線傳感器網絡中，單基站的ETBG算法由于靠近基站的節點承擔大量的數據轉發任務而造成過多的能量消耗，從而出現“能量空洞”的問題，嚴重的縮短了網絡的生命周期。而章等人提出了Q學習算法［8-11］的路由選擇機制，使數據始終沿著能量消耗代價最小的路徑進行數據傳輸，在一定程度上避免了使用剩余能量少的節點轉發數據，但是該算法適用于平面路由，在大規模網絡中的分層路由中并不適用。

本文在ETBG算法和Q學習算法的基礎上，提出了基于Q學習的多基站分簇拓撲控制算法（CTQL-MB）。該算法首先根據不同的場景確定相應的基站數目，然后利用OWA算子多屬性決策的方法［12］將節點的能量、距離、節點間的相互作用等因素融合為一個屬性值來決定節點競選簇頭的能力，利用定向擴散中的梯度思想將網絡劃分為一個不均勻的梯度圖并結合圖論中獨立集的概念對網絡進行分簇，最后運用Q學習算法對簇頭節點進行周期性的學習訓練，比較到達不同基站的不同路徑上的Q值，選擇整條路徑上Q值最大的路徑為最優路徑。

1　基于Q學習的單基站分簇算法

1.1Q學習

Q-learning是強化學習的一種常用算法。強化學習系統接受環境狀態的輸入s，根據內部的推理機制，系統輸出相應的行為動作a。環境在系統動作作用a下，變遷到新的狀態s′。系統接受環境新狀態的輸入，同時得到環境對于系統的瞬時獎懲反饋r。對于強化學習系統來講，其目標是學習一個行為策略π:S→A，使系統選擇的動作能夠獲得環境獎賞的累計值最大。

Q值的更新公式如式（1）所示:

式中:γ為折扣因子；r（i）是回報函數［5］，具體定義如下:

式中:node（i）.w是收到學習消息的任意節點i的權值；node（j）.w是指發送學習消息的節點j的權值；node（j）.cost（i）是指發送學習消息的節點j到收到消息的節點i的路徑能量消耗。這樣就可以把節點的能量、距離、鄰居節點數目以及兩節點間的鏈路通信耗能全部考慮進去，更能反映出網絡的節點動態，回報函數越大，說明該節點路由的“趨勢”就越強。在該算法中假定γ=1以加快學習速度。系統產生該動作的趨勢主要決定于環境的獎賞值，獎賞值如果為正則趨勢會越來越強。換言之，系統要使得（1）式最大化。

1.2單基站算法性能分析

采用文獻［5］中的算法進行仿真。為了對Q學習算法的性能進行評估，本文首先對該算法在單基站的情況下和ETBG算法進行比較。定義從算法開始運行到第一個節點死亡之間的時間為網絡生存期，網絡生存期同樣可以以數據采集總輪數表示。仿真的參數設置為的范圍內200個節點，在二十個不同的場景下進行仿真，然后取其平均值，可得不同通信半徑下兩種算法的生存期對比圖，如圖1所示。

圖1　不同通信半徑下的生存期對比圖

可以看到，當R大于40時，在ETBG算法中生命周期會出現明顯的下降，這是因為隨著R增大，梯度上限增大，鄰居節點數目增多，使得簇的個數減少，簇頭之間距離增大，導致簇頭能量消耗更大，數據傳輸的輪數就會明顯減少。而引入Q學習算法之后，對每個節點進行周期性的學習訓練，根據每條路徑上的Q值選擇最佳的路徑，就解決了ETBG算法生成簇樹過程中未能找到最佳路徑造成的能量在傳輸過程損耗過大的問題，故其生命周期下降速度較ETBG算法更為平緩，R越大CTQL算法的優勢就體現的越明顯。

CTQL算法仍還存在一些問題，如簇樹過高會造成網絡時延更長，網絡能量不均衡會導致部分節點過早死亡等，在大規模的分層路由中并不適用。本文在CTQL算法的基礎上，提出基于Q學習的多基站分簇拓撲控制（CTQL-MB）算法。

2　基于Q學習的多基站分簇算法

多基站的策略將使簇樹更矮，網絡的魯棒性和擴展性更強，能有效解決CTQL算法中時延過高、能量不均衡的問題，使得生命周期得到有效延長。基站的能量容易補充，多個基站不僅可以根據不同的場景分布在不同位置，也可以在必要的情況進行移動，以照顧能量損耗大的節點，同時多個基站之間也可以進行直接的信息交互。

基站位置選擇的原則是盡量以最小的梯度覆蓋整個網絡，從而減少由于遠距離傳輸時延過大，以及部分節點轉發過多引起耗能過大導致過早死亡的問題。

算法總體包括以下幾個過程:構建唯一梯度值、簇的確定、建立簇樹。

2.1構建唯一梯度值

假設網絡中有n（n=1，2，3，…，n為整數）個基站，分別為BS1，BS2，…，BSn。首先以基站BSn（n= 1，2，3，…）為中心，以節點的通信半徑mR（m=1，2，3，…，D/m，D/m為整數）為半徑發送梯度劃分消息。任意節點的初始唯一梯度值L=0。節點在收到第一個梯度劃分消息后將其置為自己的唯一梯度值，當節點繼續收到其他的梯度化分消息時，將所收到的梯度值與當前的梯度值比較，并按以下規則處理:①如果當前梯度值與所收到的梯度值不同，則將唯一梯度值更新為小的梯度值。②如果當前梯度值與所收到的梯度值相同，則計算該節點到這兩個梯度值所對應的基站的距離d to BSk（k∈n），然后選擇距離基站距離最小的所對應的梯度值作為該節點的唯一梯度值。

2.2簇的確定

在確定各個節點的唯一梯度值后節點間進行第一次信息交互，以R為功率半徑向其鄰居節點廣播當前狀態消息，其中包括節點ID、當前剩余能量、唯一梯度值L、狀態status。每個節點將得到的鄰居信息保存在自己的鄰居集中，包括鄰居節點的狀態信息并計算本節點的鄰居節點數目。節點根據自己鄰居集中的信息，運用OWA多屬性決策方法［5］確定自己的權值。

各個節點將自己鄰居中唯一梯度值相同節點構成同梯度等級集合，然后利用圖論中獨立集的概念將同一梯度等級內的節點進行比較，如果其權值最大，則宣布自己成為簇頭節點，具體方法見文獻［5］。

簇頭確定后，網絡中的非簇頭節點按照ETBG算法［4］的策略加入不同的簇，從而完成網絡的分簇。

2.3建立簇樹

分簇階段完成后，基站BSn（n=1，2，3，…）周期性地向其鄰居節點發送學習消息learnBSn（n=1，2，3，…），啟動路徑建立。學習消息中記錄了節點的Q值、回報函數以及節點的能量信息和權值，各個節點的初始Q值為0。鄰居節點繼續向下一梯度的鄰居簇頭節點發送學習消息直到網絡中所有簇頭節點均進行學習訓練。任意節點如果首次收到學習消息則建立Q表儲存學習消息中的信息，而收到學習消息的節點只有當到相應基站的距離大于發送消息的節點時才進行學習訓練并按照規則1～規則4處理，否則放棄學習，避免形成回路。

規則1如果簇頭節點收到來自鄰居的簇成員節點的學習消息，根據式（2）來計算節點的回報函數，再根據式（1）更新節點Q值，并儲存在自己的Q表中，繼續轉發消息，等待所有基站的學習任務進行完后執行規則4。

規則2如果簇成員節點收到簇頭節點的學習消息，根據式（2）計算回報函數，再根據式（1）來更新節點的Q值，并儲存在自己的Q表中，繼續向下在兩跳范圍內轉發該學習消息，等待所有基站的學習任務都進行完則進入規則4。

規則3如果簇成員節點收到非簇頭節點的學習消息，根據式（2）計算回報函數，再根據式（1）更新Q值，并儲存并繼續向下一跳范圍內轉發該學習消息，等待所有基站的學習任務都進行完則進入規則4。

規則4在各個基站到該節點的所有路徑的Q值逐步迭代出來后，選出該節點Q表中BSnQ（n=1，2，3，…）的最大值所對應的節點作為自己的父親節點，如果該父親節點為簇成員節點則其該簇成員節點聲明自己為網關節點。

整個網絡的簇頭節點都遍歷后，算法結束。每個節點都建立到達基站的最優的傳輸路徑。在該算法中，多基站解決了“能量空洞”和時延問題，生成簇樹的過程中節點間通信的每一步選擇都綜合考慮了節點的通信能力、跳數、剩余能量，從中選擇到達各個基站最能均衡能量、節省能量、延長節點壽命的路徑選擇路由，因而針對大規模的無線傳感器網絡具有一定的實用價值和現實意義。

2.4特例分析

特例:假設在一個的區域內隨機拋灑50個傳感器節點，設定兩個基站位置分別為（100，0），（100，200）。采用文獻［4］所示能量模型，各個參數的設定如下:網絡中所有節點的初始能量為0.5 J，通信半徑為50 m，每接收一位消息耗能50 nJ，每發送一位消息傳輸1 m距離耗能0.1 nJ。消息包固定長度為128 bit，基站初始Q值為50。假定節點位置不變且相互間通信正常，不考慮重傳問題并且節點間不存在單向鏈路。如圖2所示，為運行該算法后的簇樹圖，其中“方塊”代表簇頭，“菱形”代表網關，其余為普通節點。

圖2中可以看出基站BS1，BS2均發送一個學習消息，其鄰居節點進行轉發。其中基站BS2的鄰居中有簇頭節點37，該節點在進行學習訓練后繼續想起鄰居簇頭轉發學習消息，其鄰居節點中的簇頭節點按照規則①進行更新，并繼續向下轉發，非簇頭節點按照規則②、規則③、規則④進行更新；基站BS1的鄰居節點中無簇頭節點在，則節點22作為網關節點繼續轉發學習消息，如果作為網關節點連接簇樹，則退出其所屬的簇，直接與基站通信。

圖2　算法運行后生成的簇樹圖

例如簇頭節點17的可能路徑及各個路徑的Q值如表1所示:

表1　節點17的Q表

可以看到，其中BS1-22-1-17這條路徑上的Q值最大，則選擇該路徑傳輸數據。

3　算法性能分析

對算法的性能進行評估，把該算法和單基站的Q學習算法進行比較，查看基站個數對網絡生命周期的影響。在仿真的參數設置為200 m×200 m的區域里隨機拋灑200個節點，設定兩基站時基站的位置分別是（100，0）（100，200），三基站時基站的位置分別是（0，0）（100，200）（200，0），檢測整個網絡的生命周期在二十次不同的場景下進行仿真，然后取其平均值，可得不同通信半徑下不同基站個數下網絡生命周期的對比圖的如圖3所示。

圖3　不同基站個數在不同通信半徑下的生存期對比圖

從圖3可以看到，當R=30時單基站的生命周期最短，兩基站的生命周期最長；當R=50時雙基站和三基站情況下生命周期無明顯差別，但均比單基站的生命周期長。

理論上基站越多，網絡能量消耗越小。而由于本論文中仿真參數選擇的區域較小，三個基站與兩個基站相比，每個節點的學習任務更重，計算所消耗的能量更多，反而使生命周期減小。

總體上，隨著節點通信半徑的增加，在網絡的生存周期內，數據傳輸的輪數在減小。這是因為隨著R增大，梯度的上限增大，鄰居節點的數目就會增多節點間交互信息的能耗必然增加，且形成簇數也會減少，同時簇數減少還會造成簇成員數增加，簇頭能量消耗更大。簇頭之間距離增大導致信息交互所消耗的能量也越大，從而數據傳輸的輪數就會減少。

4　結論

針對單基站CTQL分簇拓撲控制算法中存在的“能量空洞”以及網絡能量不均衡，網絡時延過高，生成簇樹的路徑不優化的問題，提出了CTQL-MB算法。該算法引入了多個基站，在生成簇樹的過程中通過在簇頭間運行Q-learning算法，綜合考慮節點的剩余能量、路徑通信消耗等因素尋找簇頭節點到達哪個基站才是最優路徑，優化了數據傳輸時的路徑選擇，節省了整個網絡的能量消耗。仿真結果表明，CTQL-MB算法相比較CTQL算法有效地延長了網絡的生命周期。

［1］ Tubaishat M，Madria S.Sensor Networks:An Overview［J］.IEEE Potentials，2003，22（2）:20-23.

［2］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Network［J］.Wireless Communications，2002，1（4）:660-670.

［3］ Manjeshwar A，Agrawal D P.TEEN:A Routing Qrotocol for Enhanced Efficiency in Wireless Sensor Networks［C］//IEEE International Prroceedings of 15th Parallel and Distributed Processing Symposium.IEEE Conference Proceedings，2001:2009-2015.

［4］ 閻新芳，朱玉芳，安娜.無線傳感器網絡中一種分級簇的優化算法［J］.傳感技術學報，2009，22（3）:401-406.

［5］ 閻新芳，王曉曉，馮巖.基于Q學習的無線傳感網分簇拓撲控制算法［J］.鄭州大學學報，2015，36（2）:85-88.

［6］ Yan Xinfang，Zhang Yongkun，Tang Hailing.An ETBG Optimization Algorithm Based on Analytic Hierarchy Process in WSN［C］// Proceedings of ICCSEE'2013:2013.3 The 2nd International Conference on Computer Science and Electronics Engineering.China，2013:1687-1690.

［7］ 何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協議的設計［J］.傳感技術學報，2009，22（10）:1510-1514.

［8］ Stephen S，Thiel M.A Q-Learning Strategy for LTE Mobility Load Balancing［C］//Andreas Personal Indoor and Mobile Radio Communications（PIMRC）IEEE24thInternationalSymposium 2013:2154-2158.

［9］ Xie Ya，Huang Zhonghua.Study on Statistics Based Q-Learning Algorithm for Multi-Agent System［C］//Intelligent Systems Design and Engineering Applications，2013 Fourth International Conference on DOI:10.1109/ISDEA.2013.541 Publication Year:2013: 595-600.

［10］章韻，王靜玉，陳志.基于Q學習的無線傳感器網絡自組織方法研究［J］.傳感器學報，2012，23（11）:1623-1626.

［11］蘇彬庭，方禾，許力.基于Q-Learning的無線傳感器網絡生命周期平衡路由［J］.信息網絡安全，2015（4）:74-77.

［12］吳堅.基于OWA算子理論的混合型多屬性群決策研究［D］.合肥:合肥工業大學，2008.

閻新芳（1958-），女，教授，博士，碩士生導師，主要從事無線傳感網等方面研究，iexfyan@zzu.edu.cn；

馮巖（1990-），男，碩士生，主要研究無線傳感網絡路由算法，120628416@ qq.com。

Clustering Topology Control for Multiple Base Stations in WSNs with Q-Learning*

YAN Xinfang*，FENG Yan，WANG Xiaoxiao
（School of Information Engineering，Zhengzhou University，Zhengzhou 450001，China）

This paper presents a multiple base stations clustering topology control algorithm to solve the issue of“energy hole”and high network delay near a single base station in wireless sensor networks（WSNs）.The number of base stations is determined according to different scenarios.Our algorithm uses a method of graph theory and the gradient of directional diffusion to clustering.To achieve the clustering topology control，our method exploits Q-learning method，incrementally learning at each node's sufficient network knowledge to choose the best path to base stations. Evaluation of the resulting our algorithm demonstrates its ability to significantly increase the lifetime of network in comparison to the single base station clustering algorithm.

wireless sensor networks；clustering topology control；multiple base stations；Q-learning

TP393

A

1004-1699（2016）04-0578-05

項目來源:河南省科技廳基礎與前沿研究計劃項目（152300410023）

2015-10-18修改日期:2016-01-18