Com prehensive Study on the Problem of Mobile Sink Path Planning and the Cluster Head Node Selecting in WSN Data Collection

HUIXiaowei，LIU Yanmei

(School of Electronic and Information Engineering，Liaoning Technical University，Huludao Liaoning，125105，China)

Com prehensive Study on the Problem of Mobile Sink Path Planning and the Cluster Head Node Selecting in WSN Data Collection

HUIXiaowei*，LIU Yanmei

(School of Electronic and Information Engineering，Liaoning Technical University，Huludao Liaoning，125105，China)

For large－scale wireless sensor networks viamulti－hop transmission for data collection，and cause for the energy hole problem，this paper presents amobile Sink based rendevous data gethering(MSRDG)algorithm.The algorithm is based on graph theory tomeet the conditions of delay.Considering the common nodes to the cluster head node routing and mobile Sink traversing path selection problem，a mobile trajectory is composed through a cluster head nodes asmuch as possible.Through the NS－2 simulation software to evaluate performance of the algorithm，results show that the proposed algorithm can reducemultiple hops of the data transfer and the energy consumption of wireless sensor network node，and prolong the life of the network.

WSN;rendevous;mobile Sink;path planning;MSRDG algorithm

無線傳感器網絡(WSNS)作為物聯網的底層技術近年來備受研究者的關注［1－2］。WSN由安置在監測區域中的計算、存儲和能量都有限的傳感器節點構成，節點將采集的數據以無線多跳的通信方式傳輸給匯聚節點(Sink)。由于靠近Sink的節點要轉發大量的數據容易導致節點過早耗盡能量而失效，即能量空洞現象，降低網絡的存活時間。因此，如何有效均衡利用有限能量資源延長網絡壽命［3］是WSNS的一個關鍵問題。

近來的研究表明，在WSN中運用移動Sink進行數據收集［4－5］，數據的多跳傳輸可以大幅度減少，由于Sink的移動其周圍的節點也在不斷變化，均衡了節點能量的消耗，防止能量空洞現象的產生。由于Sink節點可以和網內節點以單跳模式進行通信，在一定程度上避免了消息丟失情況的發生。文獻［6］讓移動Sink沿著固定軌道勻速運行并從相遇的傳感器節點收集數據，從而靜止節點可預測移動Sink的到達時間并在喚醒和睡眠狀態之間高效轉換，進而節省能耗。但由于軌道固定，靠近軌道的節點也會過早耗盡能量。文獻［7－8］提出了一種基于分區的調度算法PBS(Partition Based Scheduling Algorithm)來調度Sink移動以確保每一個分區內的傳感器節點緩沖區不會溢出。不過不適用規模較大的網絡。文獻［9－10］提出了基于標簽覆蓋的算法尋找能覆蓋所有節點傳輸范圍且長度最短的路徑。缺點是時延較大。文獻［11］在已取得的技術基礎之上，提出一種基于移動匯點的數據收集協議(EEMS)，首先利用分簇技術生成通訊半徑相等的簇，由剩余能量相對充足的節點構成簇首，形成通訊骨干網。之后對骨干網采用一種適合資源有限的無線網絡的分布式MST算法獲得其最小生成樹，再借助解決TSP問題的思想，構建一條路徑最短的移動軌跡。此方法有效緩解了熱點問題的發生。但此方法把移動路徑規劃和簇頭節點選取問題分開考慮，且沒有考慮普通節點到簇頭節點的路由問題。如果在規模較大的網絡，移動路徑過長，不能達到時延性要求;如果增大分簇半徑R雖可以減小移動路徑，但網絡總跳數隨之增加，開銷加大，不能達到最優的效果。

綜合利用分簇思想和移動匯點技術，本文針對規模較大且具有時延容忍特性的無線傳感器網絡提出一種基于移動Sink的簇頭節點數據收集MSRDG (Mobile Sink based Rendevous Data Gethering)算法，該算法聯合考慮了簇頭節點的選取、普通節點到簇頭節點的路由和移動Sink路徑的啟發式算法。算法首先選出最小連通支配集節點作為待選簇頭節點，根據待選簇頭節點和時延性要求下的軌跡長度L，通過本算法和借助解決TSP問題的思想獲得最優的簇頭節點集和Sink的移動軌跡。該算法在保證數據時延性要求的條件下，有效的選取盡可能多的簇頭節點，減少了傳感器節點到匯聚節點的數據傳輸，從而達到節省能量并延長網絡壽命的目的。移動軌跡上Sink節點和簇頭節點以單跳方式通信，避免了信道競爭和沖突。

1 系統模型

1.1 網絡模型的假設

考慮傳感器節點隨機地部署在監測區域內，首先對傳感器節點和網絡模型進行假定:

(1)傳感器節點布設后不能移動，具有相同的通信半徑R，周期性的產生監測信息，初始能量相同，計算和存儲功能都有限，已知自己的地理位置信息。

(2)移動Sink節點具有可控制的移動性。其能量、計算能力、存儲容量和傳輸距離等不受限制。

(3)Sink節點和簇頭節點在通信范圍內進行數據傳輸，信息具有完整性且傳輸時允許有一定的時延T。

1.2 引入圖論原理對網絡進行描述

本文應用圖論對無線傳感器網絡進行描述。在不考慮空間差異的情況下，可以將無線傳感器網絡的節點抽象成圖的頂點，把網絡節點之間的通信關系抽象成圖中頂點與頂點之間的連邊。

(1)無線傳感器網絡拓撲圖G=(V，E)，其中，V代表WSN各節點的位置，E是邊的集合，代表WSN的拓撲，當且僅當傳感器節點vi和vj在彼此的通信范圍內時，(vi，vj)?E。

(2)當系統可容忍的最大延遲時間為T時，移動Sink的最大遍歷路徑長度為L=m·T其中m為Sink的移動速度。

(3)待選簇頭節點集U=(u1，u2…uu)，其中U?V，通過迭代計算，得到簇頭節點集S=(v'0，v'1，…，v's)其中S?U。

(4)普通節點到離自己最近的簇頭節點的最短路由的跳數為h(v，v')其中v?V，v'?S。

(5)MSRDG算法的目的是找到一條訪問到簇頭節點集中每一個節點的最短遍歷路徑F(F＜L)，且使每一個普通節點到達路徑F的路由向量最小。

2 系統設計

2.1 待選簇頭節點集的選取

用圖論中的最小連通支配集［12］S作為待選簇頭節點集。其中S滿足S中的節點是相互連通的且個數最少，同時余下的節點與其中的節點至少有一個是相鄰的條件。

2.2 待選簇頭節點集的路徑規劃問題

當待選簇頭節點確定后，Sink節點的移動路徑問題可看作是旅行貨商TSP(Traveling Salesman Problem)問題。通常選用蟻群算法［13］解決此類問題。本文蟻群算法中螞蟻選擇下一個位置的概率公式如(1):

ij距離，nij為到節點j后能收集到信息的節點個數;σ是信息素啟發因子，ζ為期望啟發式因子;allowedk為第k只螞蟻下一步允許訪問的節點位置即S減去Sink已經訪問過的節點。信息量調整方式采用

其中ρ表示信息揮發系數，Δτij(t)為本次循環路徑(i，j)上的信息素增量。信息素更新原則為:

其中Q表示信息素強度，在一定程度上影響算法的收斂速度，Lk為第k只螞蟻在本次循環中所走路徑的總長度。上述螞蟻群所尋的路徑即為移動Sink所走的最優路徑。

2.3 普通節點到簇頭節點的路由問題

本文中所有傳感器節點位置是已知且是均勻分布的，普通節點到離自己最近的簇頭節點的路由算法采用貪婪轉發模式的GPSR［14］(Greedy Perimeter Stateless Routing for Wireless Networks)路由算法。普通節點發送的數據包中封裝離自己最近的簇頭節點的位置信息，選擇鄰居節點中距離簇頭節點最近的節點作為下一跳路由轉發節點，后面接收到數據包的節點不斷重復這一過程，直到數據包到達簇頭節點。每個普通節點的初始跳數設為0，當傳播到一個傳感器節點時，由該節點將跳數值加1，到達簇頭節點時，跳數值為普通節點到達簇頭節點的跳數。所有普通節點到達離自己最近的簇頭節點的跳數之和為該網絡的傳輸總跳數。

2.4 待選簇頭節點衡量值的設定

移動Sink節點在遍歷路徑長度為L的限定下，訪問的節點越多則普通節點到簇頭節點的路由代價越小，所以要使簇頭節點盡可能多。

選定待選簇頭節點后，還需要根據每個待選簇頭節點對結果影響程度移除部分對結果影響較小的待選簇頭節點，以確保在限定的最大遍歷長度L的條件下目標函數是最優的。當移除待選簇頭節點集中的某個節點時，必然使得以此節點為簇頭的普通節點要尋求其他離它路徑最短的待選節點作為新的簇頭節點，以便使數據通過最短路徑傳輸到最近的簇頭節點存儲，并等待移動Sink的訪問。

綜合考慮簇頭節點的選取、遍歷路徑規劃以及普通節點到簇頭節點路由，對待選簇頭節點的衡量值做如下定義，如式(4):

其中U為選出的待選簇頭節點集，x為其中的一個節點，w(x)代表節點x的衡量值，TSP(U)為遍歷待選簇頭節點集的最短路徑長度，h(v，u)表示舍棄節點x后整個網絡中從普通節點到待選簇頭節點的傳輸總跳數，T(x)為節點x的剩余能量，α和β兩個參數分別反映舍棄x后新增加的路由跳數和x節點的剩余能量在簇頭選擇過程中的相對重要性，α +β=1。在上式中，分子表示當從待選簇頭節點集中移除x這個節點后，剩余節點的能量一定時，整個網絡新增加的普通節點到簇頭節點的路由代價，而分母表示除x這個節點后能節省的遍歷路徑長度。所以w(x)的值越小，表明x節點的移除不但使得普通節點到簇頭節點的路由代價增加不大，而且使得移動Sink的遍歷路徑相比移除x節點前更短，也就是說節點x的移除能以盡可能少的路由代價盡快達到遍歷路徑長度L的限制，因此，每次應當選取衡量值最小的節點移除。

2.5 MSRDG算法的具體實現過程:

算法的輸入為時延性限制的移動軌跡長度條件L、傳感器節點的位置信息P和傳感器通信半徑R，最終輸出為簇頭節點集以及對簇頭節點集的遍歷路徑F。

(1)移動Sink節點根據輸入的傳感器節點位置和通信半徑R，生成網絡拓撲圖G(V，E);

(2)使用最小連通支配集算法得到G(V，E)的最小聯通支配集作為待選簇頭節點集S;

(3)計算待選簇頭節點集中每個節點的衡量值以及利用蟻群算法得到最短遍歷路徑長度l';

(4)判斷是否l'≤L，如果是退出循環，如果不是則找到待選簇頭節點集中衡量值最小的節點并舍棄該節點，回到步驟(3)進入下一次循環直至退出循環。

3 仿真與分析

本節采用NS－2仿真工具對MSRDG算法的性能進行評價。選擇簇頭節點個數、網絡傳輸總跳數和網絡壽命(網絡中第一個節點能量耗盡時，網絡已經運行的輪數)作為算法評估指標。在仿真實驗中涉及的參數取值為:ρ=0.1，σ=1，ζ=2，Q=1，α =0.8。WSNS節點隨機分布在400 m×400 m的區域內，傳感器節點數量的變化區域為(100，400)，通信半徑為50 m，網絡允許的最大時延為20 min，移動Sink以速度m(0.5，1.5)勻速移動，則可得L的取值范圍為600 m～1 800 m。

將本算法與文獻［11］中同樣引入移動匯點的EEMS協議進行比較。仿真結果如圖所示，圖1給出了在不同的節點個數和移動速度的情況下，采用MSRDG算法得到的簇頭節點個數，可以看出簇頭的節點個數隨著節點個數的增多稍有增加，顯示了傳感器網絡的可擴展性。同時隨著移動速度的增加獲得的簇頭節點個數也增加。

圖1 Sink節點在不同移動速度下簇頭節點個數對比

圖2 中，當節點數目從100增加到400時，圖2(a)中，兩種算法的傳輸總跳數都隨節點數目增加而增加。MSRDG算法的傳輸總跳數總是小于EEMS算法，且節點數目越多，MSRDG算法相比EEMS算法的優勢越明顯。圖2(b)中，可以看到，隨著節點數目增加，兩種算法的網絡壽命都隨之降低，且MSRDG算法的網絡壽命要長于EEMS算法，但差距是逐漸縮小的。

圖2 節點數目從100增加到400時的性能

從圖3中可以看出，當移動Sink的路徑長度從800 m增加到1 600 m時，圖3(a)中，兩種算法總傳輸跳數均呈現遞減的趨勢，且在1 200 m以前，傳輸總跳數減少較快，而1 200后減少趨勢變慢且兩種算法的差距變小，這是因為移動Sink遍歷路徑長度越長，則傳輸總跳數就會越少，而MSRDG算法的優勢難以顯現。圖3(b)中，隨著移動Sink的路徑長度L的增加，兩種算法的網絡壽命都隨之延長，且MSRDG算法的網絡壽命平均比EEMS算法的網絡壽命長5輪左右。

圖3 移動Sink的路徑長度從800m增加到1600m時的性能

4 結論

本文針對規模較大、數據簡單且允許有一定時延的無線傳感器網絡，提出了一種基于移動Sink的無線傳感器網絡數據收集節能算法MSRDG。仿真結果表明，MSRDG算法能在保證時延性的條件下盡可能多的有效地選取出簇頭節點，以盡可能地減少網絡的傳輸跳數，從而能夠節省網絡能耗并延長網絡壽命。同時Sink節點與軌道上的簇頭節點以單跳的方式進行數據傳輸，提高了通信質量且具有網絡可擴展性。

［1］史永彬，葉湘濱，劉培亮.無線傳感器網絡技術研究現狀［J］.國外電子測量技術，2005(11):19－23.

［2］陳靖，吳景東.基于ZigBee協議的無線傳感器網絡技術的分析和應用［J］.工業控制計算機.2010(11):30－32.

［3］李虹.無線傳感器網絡中節能相關若干關鍵問題研究［D］.中國科學技術大學，2007.

［4］張蕾，張堃.無線傳感器網絡中一種基于移動Sink的數據收集算法［J］.傳感技術學報，2012，25(5):673－677.

［5］郜帥，張宏科.時延受限傳感器網絡移動Sink路徑選擇方法研究［J］.電子學報，2011(4):742－747.

［6］Chakrabarti Arnab，Sabharwal Ashutosh，Aazhang Behnaam.Using Predictable Observer Mobility for Power Efficient Design of Sensor Networks［J］.Information Processing in Sensor Networks，Apr.2003:129－145.

［7］Yaoyao Gu，Doruk Bozdag.Partitioning Based Mobile Element Scheduling in Wireless Sensor Networks［C］//Proc.Second Annual IEEE Conference on Sensor and AD HOC Communications and Networks，2005:386－395.

［8］Yaoyao Gu，Bozdag D，Ekici E.Mobile Element Based Differentiated Message Delivery in Wireless Sensor Networks［J］.International Symposium on a World of Wireless，Mobile and Multimedia Networks，2006:83－92.

［9］Sugihara R，Gupta R K.Scheduling under Location and Time Constraints for Data Collection in Sensor Networks［C］//Proceedings of the 28th IEEE Real－Time Systems Symposium(RTSS)Work in Progress Session，2007:9－11.

［10］Sugihara R，Gupta R K.Improving the Data Delivery Latency in Sensor Networks with Controlled Mobility［C］//Proceedings of the 4th IEEE International Conference on Distributed Computing in Sensor Systems(DCOSS)，Volume 5067 of LNCS，2008:386－399.

［11］汪林云，劉文軍.無線傳感器網絡中帶有移動匯點的能量高效的數據收集協議［J］.傳感技術學報，2012，25(5):678－682.

［12］Wu J，Li H.On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks［C］//Proc of the Third InternationalWorkshop on Discrete Algorithms and Methods for Mobile Computing and Communications，1999:7－14.

［13］王佳.WSN中基于改進蟻群算法的移動Agent路徑規劃［J］.傳感技術學報，2011，24(4):609－613.

［14］王麗娟，梁海濤，秦建敏，等.貪婪周邊無狀態路由轉發算法GPSR的分析及改進［J］.太原理工大學學報，2012，43(5): 587－590.

惠曉威(1958－)，男，遼寧省沈陽市人，滿族，教授，碩士，研究方向為現代通信、圖像識別、信息處理;

劉彥每(1989－)，女，北京人，漢族，碩士研究生，主要研究方向現代通信、圖像識別、信息處理。

WSN數據收集中移動Sink的路徑規劃和簇頭節點選取問題的綜合研究

惠曉威*，劉彥每

(遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島125105)

針對較大規模的無線傳感器網絡通過多跳傳輸進行數據收集而引起的能量空洞問題，提出了一種基于移動Sink的簇頭節點數據收集算法(MSRDG)，該算法基于圖論原理，在滿足時延性的條件下，綜合考慮了普通節點到簇頭節點路由和移動Sink遍歷路經選取的問題，構建了一條通過的簇頭節點盡可能多的移動軌跡。通過NS－2仿真軟件對算法的性能進行評估，結果顯示出該算法能減少數據的多跳傳輸，降低無線傳感器網絡節點的能量消耗，延長網絡壽命。

無線傳感器網絡;簇頭節點;移動Sink;路徑規劃;MSRDG算法

TN925.9.3;TP212

A

1004－1699(2014)01－0118－05

2013－10－09修改日期:2013－12－09

C:6150P

10.3969/j.issn.1004－1699.2014.01.022