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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

(1)無(wú)線傳感器網(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)時(shí)，(vi，vj)?E。

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

(3)待選簇頭節(jié)點(diǎn)集U=(u1，u2…uu)，其中U?V，通過(guò)迭代計(jì)算，得到簇頭節(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算法的目的是找到一條訪問(wèn)到簇頭節(jié)點(diǎn)集中每一個(gè)節(jié)點(diǎn)的最短遍歷路徑F(F＜L)，且使每一個(gè)普通節(jié)點(diǎn)到達(dá)路徑F的路由向量最小。

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

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

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

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

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

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

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

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

2.3 普通節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的路由問(wè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ù)這一過(guò)程，直到數(shù)據(jù)包到達(dá)簇頭節(jié)點(diǎn)。每個(gè)普通節(jié)點(diǎn)的初始跳數(shù)設(shè)為0，當(dāng)傳播到一個(gè)傳感器節(jié)點(diǎn)時(shí)，由該節(jié)點(diǎn)將跳數(shù)值加1，到達(dá)簇頭節(jié)點(diǎn)時(shí)，跳數(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è)定

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

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

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

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

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

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

(1)移動(dòng)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)計(jì)算待選簇頭節(jié)點(diǎn)集中每個(gè)節(jié)點(diǎn)的衡量值以及利用蟻群算法得到最短遍歷路徑長(zhǎng)度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仿真工具對(duì)MSRDG算法的性能進(jìn)行評(píng)價(jià)。選擇簇頭節(jié)點(diǎn)個(gè)數(shù)、網(wǎng)絡(luò)傳輸總跳數(shù)和網(wǎng)絡(luò)壽命(網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)能量耗盡時(shí)，網(wǎng)絡(luò)已經(jīng)運(yùn)行的輪數(shù))作為算法評(píng)估指標(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ò)允許的最大時(shí)延為20 min，移動(dòng)Sink以速度m(0.5，1.5)勻速移動(dòng)，則可得L的取值范圍為600 m～1 800 m。

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

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

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

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

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

圖3 移動(dòng)Sink的路徑長(zhǎng)度從800m增加到1600m時(shí)的性能

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

惠曉威*，劉彥每

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

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

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