無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中帶有移動(dòng)匯點(diǎn)的能量高效的數(shù)據(jù)收集協(xié)議*

汪林云，劉文軍

(1.溫州大學(xué)城市學(xué)院，浙江 溫州325035;2.同濟(jì)大學(xué)電子與信息工程學(xué)院，上海201804;3.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州215006)

近年來(lái)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)已成為軍事、健康護(hù)理、智能家居、目標(biāo)追蹤、環(huán)境監(jiān)測(cè)和預(yù)報(bào)等眾多應(yīng)用領(lǐng)域吸引人的技術(shù)。針對(duì)傳感器網(wǎng)絡(luò)特點(diǎn)，設(shè)計(jì)和部署一個(gè)成功的網(wǎng)絡(luò)需要考慮包括部署機(jī)制、能量保存、動(dòng)態(tài)環(huán)境下的路由在內(nèi)的眾多細(xì)節(jié)問(wèn)題。特別地，能量效率已成為WSN協(xié)議設(shè)計(jì)最基本的問(wèn)題之一。現(xiàn)存平衡能量消耗的解決方案，如部署優(yōu)化［1］，拓?fù)淇刂疲?］，數(shù)據(jù)匯聚［3］等，大多采用多跳路由中繼數(shù)據(jù)。多跳路由的缺點(diǎn)是容易導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)，特別是匯點(diǎn)附近的節(jié)點(diǎn)，因轉(zhuǎn)發(fā)其他網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)快速耗光能量。

由于傳感器網(wǎng)絡(luò)在資源上受限的固有特征，分簇算法產(chǎn)生的層次型拓?fù)渚哂泻芏鄡?yōu)點(diǎn)，如可以減少通信負(fù)載、降低節(jié)點(diǎn)能耗、平衡負(fù)載、延長(zhǎng)網(wǎng)絡(luò)壽命和增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性等，因此，分簇算法在大規(guī)模無(wú)線(xiàn)傳感網(wǎng)絡(luò)的使用非常普遍［4－5］。

最近的研究表明，在網(wǎng)絡(luò)中引入移動(dòng)元素(ME)可以顯著提高能量效率、連通性和可靠性［6－9］。WSN固有的多對(duì)一通信模式使得距離匯點(diǎn)近的節(jié)點(diǎn)負(fù)載比其他節(jié)點(diǎn)更重，容易遭受過(guò)早的能量耗盡。移動(dòng)匯點(diǎn)(MS)可以有效解決該問(wèn)題，它們?cè)诰W(wǎng)內(nèi)移動(dòng)可以使節(jié)點(diǎn)能量消耗更加均衡。此外，由于匯點(diǎn)可以和網(wǎng)內(nèi)節(jié)點(diǎn)以單跳模式進(jìn)行通信，不僅減少了信道的競(jìng)爭(zhēng)和沖突，提高了通信質(zhì)量，也在一定程度上避免了消息丟失情況的發(fā)生。

1 現(xiàn)存相關(guān)算法分析

在傳感器網(wǎng)絡(luò)中引入移動(dòng)匯點(diǎn)且其狀態(tài)可控時(shí)，可以通過(guò)合理選擇移動(dòng)匯點(diǎn)的運(yùn)動(dòng)軌跡來(lái)減少數(shù)據(jù)收集延遲，提高系統(tǒng)工作效率。不難得出結(jié)論，移動(dòng)匯點(diǎn)和普通數(shù)據(jù)收集節(jié)點(diǎn)之間直接接觸的數(shù)據(jù)收集問(wèn)題可以等價(jià)于NP完全的旅行售貨商問(wèn)題(TSP)。Nesamony等人［10］將匯點(diǎn)旅行問(wèn)題形式化為T(mén)SP的變體，稱(chēng)為具有鄰域關(guān)系的旅行售貨商問(wèn)題(TSPN)，匯點(diǎn)需要訪(fǎng)問(wèn)每個(gè)節(jié)點(diǎn)的鄰域恰好一次。移動(dòng)匯點(diǎn)逐步到達(dá)每個(gè)節(jié)點(diǎn)的通信范圍內(nèi)，從而可以充分地接受到來(lái)自傳感節(jié)點(diǎn)上的感測(cè)數(shù)據(jù)。

網(wǎng)絡(luò)輔助的導(dǎo)航(NAN)問(wèn)題［11］旨在尋找一個(gè)MS的移動(dòng)軌道使得所有節(jié)點(diǎn)以單跳方式可達(dá)。可以通過(guò)創(chuàng)建一個(gè)稱(chēng)為導(dǎo)航代理(NA)的邏輯覆蓋拓?fù)溥_(dá)到該目標(biāo)。如果定義一個(gè)跳限因子k，使得數(shù)據(jù)可以在k跳內(nèi)被轉(zhuǎn)發(fā)則NAN進(jìn)一步擴(kuò)展為網(wǎng)絡(luò)輔助的數(shù)據(jù)收集(NADC)問(wèn)題［12］。易見(jiàn)當(dāng) k=1 NADC問(wèn)題對(duì)應(yīng) NAN問(wèn)題。類(lèi)似地，TRACK［13］采用支配集CDS構(gòu)建骨干網(wǎng)，對(duì)構(gòu)建的骨干網(wǎng)采用一種分布式算法產(chǎn)生一棵最小生成樹(shù)MST［14］，在MST的基礎(chǔ)上將每條邊看作兩條邊，尋找一條哈密頓圈HC作為移動(dòng)匯點(diǎn)的軌跡。該機(jī)制的缺點(diǎn)是生成的軌跡仍然較長(zhǎng)，仍可能導(dǎo)致數(shù)據(jù)溢出等問(wèn)題的發(fā)生。

綜合利用分簇和移動(dòng)匯點(diǎn)技術(shù)，本文提出一種能量高效的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議。協(xié)議首先依靠分簇機(jī)制生成通信骨干網(wǎng)，對(duì)骨干網(wǎng)采用一種適合資源有限的無(wú)線(xiàn)網(wǎng)絡(luò)的分布式MST算法獲得其最小生成樹(shù)，在此基礎(chǔ)上借助解決TSP問(wèn)題的思想，構(gòu)建一條路徑最短的MS移動(dòng)軌跡。該運(yùn)動(dòng)軌跡上MS和每個(gè)簇以單跳方式通信，增強(qiáng)了通信信道質(zhì)量，解決了熱點(diǎn)等問(wèn)題的發(fā)生。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

考慮由N個(gè)傳感器節(jié)點(diǎn)均一地部署在廣闊區(qū)域(如方形)上進(jìn)行連續(xù)的環(huán)境監(jiān)測(cè)應(yīng)用環(huán)境。為了研究問(wèn)題的方便，首先對(duì)傳感器節(jié)點(diǎn)和潛在網(wǎng)絡(luò)模型進(jìn)行假定:

(1)節(jié)點(diǎn)周期性監(jiān)測(cè)環(huán)境數(shù)據(jù)，計(jì)算和存儲(chǔ)功能有限，節(jié)點(diǎn)對(duì)地理位置信息不敏感，可以工作在休眠和喚醒模式以節(jié)省能量;

(2)移動(dòng)匯點(diǎn)MS以不確定性模式在網(wǎng)絡(luò)內(nèi)以一定速率移動(dòng)，其能量和計(jì)算能力不受限制;

(3)MS和骨干節(jié)點(diǎn)在通信范圍內(nèi)進(jìn)行數(shù)據(jù)傳輸，不發(fā)生數(shù)據(jù)丟失情況;

(4)網(wǎng)絡(luò)為同構(gòu)的分層網(wǎng)絡(luò)模型，通信鏈路是對(duì)稱(chēng)的，通信范圍內(nèi)的節(jié)點(diǎn)和MS單跳通信，全網(wǎng)單跳通信;

(5)假定存在某種數(shù)據(jù)匯聚機(jī)制以節(jié)省網(wǎng)內(nèi)節(jié)點(diǎn)能量。

對(duì)通信能量損耗的評(píng)估使用一種簡(jiǎn)化的模型［15］。依據(jù)發(fā)送器和接收器之間距離的不同，使用自由空間(d2功率損耗)和多徑衰落(d4功率損耗)通道模型。在距離d上傳輸l位的包所花費(fèi)能量的計(jì)算公式為:

其中，Eelec表示節(jié)點(diǎn)發(fā)射電路的損耗。若傳輸距離小于閾值d0，則功率放大損耗采用自由空間模型，否則采用多路徑衰減模型。εfs，εmp分別為這兩種模型功率放大所需的能量。接收消息花費(fèi)的能量計(jì)算公式為:

2.2 問(wèn)題和需求

一般地，一個(gè)好的分簇模式應(yīng)滿(mǎn)足以下需求:

(1)采用算法復(fù)雜度可接受的分布式分簇機(jī)制，即算法時(shí)間和消息復(fù)雜度是高效的，分簇效果盡可能均勻以平衡能量的消耗;

(2)分簇算法執(zhí)行的結(jié)果使得每個(gè)節(jié)點(diǎn)要么是簇首，要么是普通成員節(jié)點(diǎn)。

基于分簇的骨干網(wǎng)形成后，簇首間的通信可以抽象為帶權(quán)圖G(V，E，c)。一條邊e=(u，v)存在當(dāng)且僅當(dāng)u在v的傳輸范圍且v的剩余能量可以負(fù)擔(dān)所需通信費(fèi)用。頂點(diǎn)集V代表簇首集，邊集E代表通信鏈路集，對(duì)每條邊e∈E有通信代價(jià)c(e)＞0。

給定一個(gè)簡(jiǎn)單連通無(wú)向圖G，圖G的生成樹(shù)T是一棵連接所有頂點(diǎn)子圖的樹(shù)。一棵最小生成樹(shù)(MST)或最小帶權(quán)生成樹(shù)是一棵生成樹(shù)T使得∑(u，v)∈Td(u，v)最小，此處 d(u，v)是邊(u，v)的長(zhǎng)度，定義為u和v兩點(diǎn)之間的歐氏距離。簇首的MST是連接所有簇首且邊的通信代價(jià)之和最小的一棵樹(shù)。

SE通過(guò)一條確定的路徑逐次訪(fǎng)問(wèn)每個(gè)節(jié)點(diǎn)來(lái)遍歷整個(gè)網(wǎng)絡(luò)。一個(gè)圈被稱(chēng)為哈密頓的，如果V中的每個(gè)頂點(diǎn)恰好訪(fǎng)問(wèn)一次。已知旅行售貨商問(wèn)題(TSP)的目標(biāo)是尋找最小費(fèi)用的哈密頓圈HC(Hamiltonian Cycle)。該問(wèn)題是NP完全的，無(wú)法尋找多項(xiàng)式時(shí)間算法解決一般性的TSP問(wèn)題?？紤]放松條件為允許多次訪(fǎng)問(wèn)相同頂點(diǎn)。借助該抽象模型原問(wèn)題轉(zhuǎn)化成尋找滿(mǎn)足如下目標(biāo)的最優(yōu)移動(dòng)軌跡:

(1)MS移動(dòng)通過(guò)所有簇首，以單跳方式進(jìn)行通信。特別地，MS可根據(jù)需要僅通過(guò)部分核心簇首，簇首間以有限跳數(shù)進(jìn)行多跳方式通信;

(2)MS移動(dòng)軌跡構(gòu)建算法是分布式且高效的，構(gòu)建的移動(dòng)軌跡盡可能短，以防止數(shù)據(jù)溢出現(xiàn)象的發(fā)生。

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

數(shù)據(jù)收集協(xié)議主要分為基于分簇的骨干網(wǎng)構(gòu)建和MS移動(dòng)性軌跡確定兩個(gè)階段。對(duì)骨干網(wǎng)的構(gòu)建，采用一個(gè)消息復(fù)雜度為O(n)的分布式分簇算法。對(duì)MS的移動(dòng)軌跡確定采用一種最初用于解決TSP問(wèn)題的常量近似因子1.5的改進(jìn)的分布式算法。

3.1 分布式分簇機(jī)制

網(wǎng)絡(luò)部署階段，基站(BS)以某種功率水平向網(wǎng)內(nèi)所有節(jié)點(diǎn)廣播HELLO_MES消息。收到消息后每個(gè)節(jié)點(diǎn)檢驗(yàn)自身是否是候選簇首。每個(gè)候選簇首基于收到的信號(hào)強(qiáng)度計(jì)算其到BS的近似距離，然后執(zhí)行分布式簇首競(jìng)選算法，該算法的主要思想由Chen等人提出用于解決非均勻分簇問(wèn)題［4］，簇首競(jìng)選主要基于候選簇首的剩余能量，簇的半徑為常量R，該參數(shù)可基于特定需要進(jìn)行調(diào)整。

(1)分簇前BS以某種概率隨機(jī)選擇預(yù)定義數(shù)量的候選簇首來(lái)競(jìng)爭(zhēng)最終的簇。為了節(jié)省能量，非候選簇首保持休眠狀態(tài)直至簇首選擇階段結(jié)束為止。

(2)每個(gè)候選簇首廣播一條包含了半徑和剩余能量的簇首競(jìng)選消息COMPETE_CH。每個(gè)控制消息的廣播半徑是Rmax=2R，所以候選簇首ci可以聽(tīng)到來(lái)自于相鄰簇首集合ci·SCH的所有消息。構(gòu)建SCH結(jié)束后，每個(gè)候選簇首檢驗(yàn)其SCH并確定是否可以作為簇首。如果構(gòu)建的SCH為空，則候選簇首立刻變?yōu)樽罱K簇首。一旦ci發(fā)現(xiàn)其剩余能量高于SCH中的有的節(jié)點(diǎn)，它將贏得競(jìng)選。如果cj屬于ci·SCH且ci收到來(lái)自于cj的FINAL_CH消息，則ci放棄競(jìng)選過(guò)程。

(3)所有的最終簇首確定后，BS記錄它們關(guān)于剩余能量、標(biāo)識(shí)ID、距離等相關(guān)信息，用于后續(xù)階段(移動(dòng)路徑選擇)。之前休眠的節(jié)點(diǎn)被喚醒，每個(gè)節(jié)點(diǎn)基于收到的信號(hào)強(qiáng)度加入最近的簇并通過(guò)發(fā)送JOIN_CLU消息通知簇首。簇首建立一個(gè)TDMA時(shí)序并傳輸給簇內(nèi)節(jié)點(diǎn)。簇內(nèi)節(jié)點(diǎn)收到該TDMA時(shí)序后，分簇階段完成。

在分簇算法的執(zhí)行過(guò)程中，每個(gè)候選簇首發(fā)送一個(gè)COMPETE_CH消息。如果該節(jié)點(diǎn)變?yōu)榇厥讋t廣播一個(gè)FINAL_CH消息來(lái)聲明其贏得競(jìng)選或者廣播一條QUIT_ELECT消息予以退出。每個(gè)簇首廣播一條CH_ADV消息，而每個(gè)普通節(jié)點(diǎn)則廣播一條JOIN_CLU消息?；谝陨戏治觯總€(gè)節(jié)點(diǎn)的消息復(fù)雜度為O(1)。分簇階段中，總的消息開(kāi)銷(xiāo)為2M+Nc+N－Nc=O(N)，此處N為網(wǎng)絡(luò)規(guī)模，M為候選簇首數(shù)，Nc是最終簇首數(shù)。

網(wǎng)絡(luò)中的任意節(jié)點(diǎn)存在三種狀態(tài):RegularNode，CandidateCH和FinalCH。對(duì)任意的候選簇首ci如果它沒(méi)有任何相鄰節(jié)點(diǎn)，則ci立刻變?yōu)樽罱K簇首。否則ci要么變?yōu)樽罱K簇首要么變?yōu)槠胀ü?jié)點(diǎn)，不存在其他情況。因而，分簇算法執(zhí)行后，每個(gè)節(jié)點(diǎn)要么是簇首要么是普通節(jié)點(diǎn)。每個(gè)普通節(jié)點(diǎn)屬于一個(gè)簇，且在每個(gè)競(jìng)選范圍內(nèi)僅存在一個(gè)簇首。

3.2 構(gòu)建MS行動(dòng)軌跡

MS移動(dòng)軌跡的構(gòu)建首先需要在骨干網(wǎng)基礎(chǔ)上生成MST。本文采用由Khan等人提出的稱(chēng)為最近鄰居樹(shù)(NNT)的分布式算法生成，記為 NNT_MST［16］。所有節(jié)點(diǎn)具有唯一的構(gòu)成有序集的ID，每個(gè)頂點(diǎn)v獨(dú)立執(zhí)行如下過(guò)程:選擇唯一的等級(jí)v.rank，連接到最近的節(jié)點(diǎn) w 使得 w.rank＞v.rank，即添加一條邊(w，v)到NNT中。相對(duì)于消息最優(yōu)的GHS算法，該算法產(chǎn)生的MST所消耗的能量顯著降低。

在不考慮移動(dòng)匯點(diǎn)MS移動(dòng)速度、網(wǎng)絡(luò)不穩(wěn)定性等因素對(duì)數(shù)據(jù)傳輸?shù)挠绊懀琈S的移動(dòng)性可以?xún)H通過(guò)其移動(dòng)軌跡進(jìn)行刻畫(huà)，如果在MST中將地理位置靠近的奇數(shù)度頂點(diǎn)相連使其構(gòu)成偶數(shù)度，則生成的HC長(zhǎng)度明顯縮短。獲得MS移動(dòng)軌跡具體過(guò)程如下:

(1)變量初始化，令 G=(V，E)，V=VCH，E=EMST+EREG，即圖G的頂點(diǎn)集由簇首節(jié)點(diǎn)構(gòu)成，邊集由MST中的邊EMST和簇首間存在通信鏈路的所有邊EREG構(gòu)成;令S為最小生成樹(shù)T中奇數(shù)度頂點(diǎn)集合。

(2)對(duì)S中的每個(gè)頂點(diǎn)v，如果其度為奇數(shù)，則在EREG中尋找一條最小代價(jià)邊，使v和通過(guò)該邊相連的另一端頂點(diǎn)w都構(gòu)成偶數(shù)度頂點(diǎn)，并將該邊添加到T中。該步驟執(zhí)行的結(jié)果是形成圖G的生成子圖G'，該圖包括了所有簇首頂點(diǎn)且每個(gè)頂點(diǎn)都具有偶數(shù)度。

(3)MS從圖G'中的任意頂點(diǎn)開(kāi)始訪(fǎng)問(wèn)網(wǎng)絡(luò)，在移動(dòng)過(guò)程中MS記錄它所經(jīng)過(guò)的簇首相關(guān)信息(位置、節(jié)點(diǎn)鄰居和已訪(fǎng)問(wèn)的鄰居等)。若節(jié)點(diǎn)有多個(gè)鄰居，則隨機(jī)挑選一個(gè)進(jìn)行訪(fǎng)問(wèn)，并使用布爾變量對(duì)訪(fǎng)問(wèn)過(guò)的邊進(jìn)行標(biāo)記;若節(jié)點(diǎn)的所有鄰居均訪(fǎng)問(wèn)完畢，則返回到最近的奇數(shù)度頂點(diǎn)。重復(fù)以上過(guò)程，直至網(wǎng)絡(luò)中所有的節(jié)點(diǎn)訪(fǎng)問(wèn)完畢，返回到出發(fā)點(diǎn)。

圖1(a)顯示了利用分布式分簇算法生成的12個(gè)簇，每個(gè)簇內(nèi)包含一個(gè)簇首節(jié)點(diǎn)。利用分布式最小生成樹(shù)算法生成MST如實(shí)線(xiàn)所示，虛線(xiàn)表示簇首之間存在通信鏈路。圖1(b)圖示了移動(dòng)匯點(diǎn)的移動(dòng)軌跡。初始時(shí)MS從節(jié)點(diǎn)v1出發(fā)，然后依次選擇鄰居 v2，v3，v4，v5，在節(jié)點(diǎn) v5處，(v3，v5)不是生成樹(shù)的邊，但二者存在通信鏈路，且兩個(gè)節(jié)點(diǎn)的鄰居數(shù)均為奇數(shù)，因此v5選擇v3作為鄰居。類(lèi)似的情況存在于v9和v10，v8和v11之間。當(dāng)MS行走到節(jié)點(diǎn)v6處，網(wǎng)絡(luò)中距離v6最近的奇數(shù)鄰居節(jié)點(diǎn)為v1，此時(shí)，MS從v6返回到初始點(diǎn)v1，完成對(duì)整個(gè)網(wǎng)絡(luò)骨干節(jié)點(diǎn)的訪(fǎng)問(wèn)，移動(dòng)過(guò)程中MS以一跳方式收集網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息。MS可以在一次移動(dòng)后獲得網(wǎng)絡(luò)的整體信息，從而可以借助這些信息對(duì)整個(gè)系統(tǒng)進(jìn)行全局優(yōu)化。

圖1

4 系統(tǒng)仿真

本節(jié)采用MATLAB對(duì)協(xié)議進(jìn)行仿真。選擇分簇個(gè)數(shù)、匯點(diǎn)路徑長(zhǎng)度(跳數(shù))和網(wǎng)絡(luò)壽命3個(gè)指標(biāo)評(píng)估算法性能。將本協(xié)議記為EEMS，與同樣引入移動(dòng)匯點(diǎn)的TRACK協(xié)議進(jìn)行比較。實(shí)驗(yàn)場(chǎng)景為節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的正方形區(qū)域內(nèi)，節(jié)點(diǎn)數(shù)N取50～400。實(shí)驗(yàn)仿真結(jié)果如圖2～圖4所示。

圖2 不同節(jié)點(diǎn)密度和通信半徑下分簇個(gè)數(shù)對(duì)比

圖2給出了在不同的網(wǎng)絡(luò)節(jié)點(diǎn)密度和分簇半徑R情況下，采用分布式分簇算法得到的簇個(gè)數(shù)，可以看出簇的個(gè)數(shù)隨著節(jié)點(diǎn)密度的增大稍有增加，顯示了網(wǎng)絡(luò)的可擴(kuò)展性良好;另一方面，在不同的通信半徑下簇的規(guī)模相應(yīng)增加，表明分簇半徑越小獲得的簇個(gè)數(shù)越多，骨干網(wǎng)節(jié)點(diǎn)數(shù)目也就越多。

圖3 通信半徑固定(R=20 m)分簇個(gè)數(shù)與路長(zhǎng)關(guān)系

圖3給出了移動(dòng)匯點(diǎn)MS路徑長(zhǎng)度、跳數(shù)和簇個(gè)數(shù)之間的關(guān)系，同時(shí)給出了TRACK協(xié)議在相同的骨干節(jié)點(diǎn)數(shù)目情況下的路長(zhǎng)，通過(guò)對(duì)比可以看出本協(xié)議獲得的路長(zhǎng)和跳數(shù)都明顯變短。將網(wǎng)絡(luò)壽命定義為網(wǎng)絡(luò)開(kāi)始工作到網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)耗光能量的時(shí)間段。統(tǒng)一通信半徑為20 m，以L(fǎng)EACH協(xié)議在50個(gè)節(jié)點(diǎn)情況下的網(wǎng)絡(luò)壽命為基準(zhǔn)1，圖4給出了本協(xié)議、LEACH協(xié)議和TRACK協(xié)議網(wǎng)絡(luò)壽命對(duì)比關(guān)系，從圖中可以看出隨著節(jié)點(diǎn)數(shù)目的增多網(wǎng)絡(luò)壽命都呈現(xiàn)了一定的增長(zhǎng)。采用移動(dòng)匯點(diǎn)機(jī)制的TRACK協(xié)議和EEMS協(xié)議相對(duì)LEACH協(xié)議網(wǎng)絡(luò)壽命具有顯著增長(zhǎng)，驗(yàn)證了移動(dòng)匯點(diǎn)的引入對(duì)網(wǎng)絡(luò)壽命具有非常顯著的改善作用。同TRACK協(xié)議相比EEMS通過(guò)使用更加高效的MST生成算法、構(gòu)建更短的匯點(diǎn)移動(dòng)軌跡等機(jī)制使得傳感器網(wǎng)絡(luò)壽命有了進(jìn)一步的提升。

圖4 通信半徑固定(R=20 m)節(jié)點(diǎn)密度與網(wǎng)絡(luò)壽命的關(guān)系

5 結(jié)束語(yǔ)

綜合利用分簇、移動(dòng)匯點(diǎn)技術(shù)，提出一種能量高效的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議。通過(guò)分布式分簇機(jī)制生成網(wǎng)絡(luò)通信的骨干網(wǎng)，有利于大規(guī)模無(wú)線(xiàn)網(wǎng)絡(luò)的可擴(kuò)展性和穩(wěn)定性。對(duì)骨干網(wǎng)節(jié)點(diǎn)采用一種適合資源受限的無(wú)線(xiàn)網(wǎng)絡(luò)的分布式MST算法生成骨干網(wǎng)節(jié)點(diǎn)的最小生成樹(shù)，并在此基礎(chǔ)上借助解決TSP問(wèn)題的思想構(gòu)建移動(dòng)匯點(diǎn)的移動(dòng)軌跡。在該移動(dòng)軌跡上MS和每個(gè)簇以單跳方式通信，有效避免了信道競(jìng)爭(zhēng)和沖突，提高了通信質(zhì)量，緩解了熱點(diǎn)問(wèn)題的發(fā)生。

［1］ Lian J，Naik K，Agnew G.Data Capacity Improvement of Wireless Sensor Networks Using Non-Uniform Sensor Distribution［J］.Int’l J.Distributed Sensor Networks，2006，2(2):121－145.

［2］ Ammari H M，Das S K.Promoting Heterogeneity，Mobility and Energy-Aware Voronoi Diagram in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(7):995－1008.

［3］ Zhang H，Shen H.Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(10):1526－1539.

［4］ Chen G，Li C F，Ye M，et al.An Unequal Cluster-Based Routing Strategy in Wireless Sensor Networks［J］.Wireless Networks，2009，15(2):193－207.

［5］ 章?lián)u韻，宋汝蕓，陳搖志，等.基于簇頭選擇的移動(dòng)傳感網(wǎng)拓?fù)淇刂扑惴ㄑ芯浚跩］.傳感技術(shù)學(xué)報(bào)，2011，24(11):1602－1606.

［6］ Di Francesco M，Das S K，Anastasi G.Data Collection in Wireless Sensor Networks with Mobile Elements:A Survey［J］.ACM Transactions on Sensor Networks，2011，8(1):1－34.

［7］ Basagni S，Carosi A，Melachrinoudis E，et al.Controlled Sink Mobility for Prolonging Wireless Sensor Networks Lifetime［J］.ACM Wireless Networks，2008，14(6):831－858.

［8］ Wang W，Srinivasan V，Chua K C.Using Mobile Relays to Prolong the Lifetime of Wireless Sensor Networks［C］//Proc.of ACM MobiCom，2005:270－283.

［9］ Luo J，Hubaux J P.Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks［C］//Proc.of IEEE Infocom，vol.3，2005:1735－1746.

［10］ Nesamony S，Vairamuthu M K，Orlowska M E.On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network［C］//Proc.of the 4th International Conference on Networked Sensing Systems(INSS)，2007:61－64.

［11］ Rao J，Biswas S.Joint Routing and Navigation Protocols for Data Harvesting in Sensor Networks［C］//Proc.of the 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems(MASS)，2008:143－152.

［12］ Rao J，Biswas S.Network Assisted Sink Navigation for Distributed Data Gathering:Stability and Delay-Energy Trade-Offs［J］.Computer Communications，2010，33(2):160－175.

［13］ Srinivasan AWu J.TRACK:A Novel Connected Dominating Set based Sink Mobility Model for WSNs［C］//Proc.ICCCN 2008:664－671.

［14］ Gallager R G，Humblet P A，Spira P M.A Distributed Algorithm for Minimum-Weight Spanning Trees［J］.ACM Transactions on Programming Languages and Systems，1983，5(1):66－77.

［15］ Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks Communication:Clustering and Aggregation［J］.Ad-Hoc Networks Journal，2004，2(1):45－63.

［16］ Khan M，Pandurangan G，Anil Kumar V S.Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks［J］.IEEE Transations on Parallel and Distributed Systems，2009，20(1):124－139.