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－h(huán)op 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

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

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

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

1 系統(tǒng)模型

1.1 網(wǎng)絡模型的假設

考慮傳感器節(jié)點隨機地部署在監(jiān)測區(qū)域內，首先對傳感器節(jié)點和網(wǎng)絡模型進行假定:

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

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

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

1.2 引入圖論原理對網(wǎng)絡進行描述

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

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

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

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

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

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

2 系統(tǒng)設計

2.1 待選簇頭節(jié)點集的選取

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

2.2 待選簇頭節(jié)點集的路徑規(guī)劃問題

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

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

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

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

2.3 普通節(jié)點到簇頭節(jié)點的路由問題

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

2.4 待選簇頭節(jié)點衡量值的設定

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

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

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

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

2.5 MSRDG算法的具體實現(xiàn)過程:

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

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

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

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

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

3 仿真與分析

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

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

圖1 Sink節(jié)點在不同移動速度下簇頭節(jié)點個數(shù)對比

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

圖2 節(jié)點數(shù)目從100增加到400時的性能

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

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

4 結論

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

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

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

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

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

［5］郜帥，張宏科.時延受限傳感器網(wǎng)絡移動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］汪林云，劉文軍.無線傳感器網(wǎng)絡中帶有移動匯點的能量高效的數(shù)據(jù)收集協(xié)議［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路徑規(guī)劃［J］.傳感技術學報，2011，24(4):609－613.

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

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

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

WSN數(shù)據(jù)收集中移動Sink的路徑規(guī)劃和簇頭節(jié)點選取問題的綜合研究

惠曉威*，劉彥每

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

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

無線傳感器網(wǎng)絡;簇頭節(jié)點;移動Sink;路徑規(guī)劃;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