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

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

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

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型的假設(shè)

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

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

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

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

1.2 引入圖論原理對網(wǎng)絡(luò)進(jìn)行描述

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

(1)無線傳感器網(wǎng)絡(luò)拓?fù)鋱DG=(V，E)，其中，V代表WSN各節(jié)點(diǎn)的位置，E是邊的集合，代表WSN的拓?fù)?，?dāng)且僅當(dāng)傳感器節(jié)點(diǎn)vi和vj在彼此的通信范圍內(nèi)時，(vi，vj)?E。

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

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

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

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

2 系統(tǒng)設(shè)計

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

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

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

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

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

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

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

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

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

2.4 待選簇頭節(jié)點(diǎn)衡量值的設(shè)定

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

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

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

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

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

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

(1)移動Sink節(jié)點(diǎn)根據(jù)輸入的傳感器節(jié)點(diǎn)位置和通信半徑R，生成網(wǎng)絡(luò)拓?fù)鋱DG(V，E);

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

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

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

3 仿真與分析

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

［5］郜帥，張宏科.時延受限傳感器網(wǎng)絡(luò)移動Sink路徑選擇方法研究［J］.電子學(xué)報，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)絡(luò)中帶有移動匯點(diǎn)的能量高效的數(shù)據(jù)收集協(xié)議［J］.傳感技術(shù)學(xué)報，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中基于改進(jìn)蟻群算法的移動Agent路徑規(guī)劃［J］.傳感技術(shù)學(xué)報，2011，24(4):609－613.

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

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

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

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

惠曉威*，劉彥每

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

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

無線傳感器網(wǎng)絡(luò);簇頭節(jié)點(diǎn);移動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