苗春雨,戴國勇,陳宇錚,陳慶章

(1.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310014;2.浙江師范大學(xué)行知學(xué)院,浙江 金華 321004)

?

能耗均衡的移動傳感器節(jié)點(diǎn)派遣算法*

苗春雨1,2,戴國勇1,陳宇錚1,陳慶章2*

(1.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310014;2.浙江師范大學(xué)行知學(xué)院,浙江 金華 321004)

在混合無線傳感器網(wǎng)絡(luò)中,移動傳感器節(jié)點(diǎn)最耗能的操作是移動,如何減少移動傳感器節(jié)點(diǎn)的移動距離同時能讓其完成任務(wù)是一個富有挑戰(zhàn)性的研究課題。本文提出了一個移動傳感器節(jié)點(diǎn)的派遣算法,旨在均衡各個移動傳感器節(jié)點(diǎn)的移動負(fù)載,并且能按優(yōu)先級響應(yīng)事件地點(diǎn),適用于任意數(shù)量的移動傳感器節(jié)點(diǎn)和事件地點(diǎn)的情況。當(dāng)移動傳感器節(jié)點(diǎn)數(shù)量大于事件地點(diǎn)數(shù)量時,將其轉(zhuǎn)化為一個帶權(quán)完全二分圖上的最大匹配問題。當(dāng)事件地點(diǎn)數(shù)量大于移動傳感器節(jié)點(diǎn)的數(shù)量時,本文提出的算法先將事件地點(diǎn)聚類分簇,然后派遣移動傳感器節(jié)點(diǎn)到各個簇中分別完成訪問任務(wù)。為了減少傳感器節(jié)點(diǎn)之間的消息傳輸量,本文在集中式算法的基礎(chǔ)上又提出了一個分布式算法。仿真實驗結(jié)果表明本文提出的分布式算法能有效降低傳感器節(jié)點(diǎn)之間的消息傳輸量,算法能夠使得整個混合無線傳感器網(wǎng)絡(luò)的生存壽命延長20%左右。

無線傳感器網(wǎng)絡(luò);移動傳感器節(jié)點(diǎn)派遣;負(fù)載均衡;最大匹配

我們稱一個由靜態(tài)傳感器節(jié)點(diǎn)和移動傳感器節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)為混合無線傳感器網(wǎng)絡(luò)[1]。移動傳感器節(jié)點(diǎn)需要在靜態(tài)傳感器節(jié)點(diǎn)偵測到環(huán)境事件發(fā)生時向目標(biāo)區(qū)域移動以做更深入的調(diào)查,也需要在靜態(tài)傳感器節(jié)點(diǎn)發(fā)生故障使得監(jiān)測區(qū)域出現(xiàn)覆蓋空洞時向空洞處移動來填補(bǔ)網(wǎng)絡(luò)空洞[2-3]。因此,在混合無線傳感器網(wǎng)絡(luò)中,一個重要的課題是規(guī)劃若干移動節(jié)點(diǎn)對若干指定事件地點(diǎn)的派遣問題(調(diào)度問題)。無論是靜態(tài)節(jié)點(diǎn)還是移動節(jié)點(diǎn)一般均采用電池供電,所以減少節(jié)點(diǎn)能量的消耗,延長無線傳感器網(wǎng)絡(luò)的使用壽命也是一個值得研究的問題[4]。一般來說,對于一個移動傳感器節(jié)點(diǎn),其用于移動的能量消耗是所有能量消耗的主要部分,遠(yuǎn)大于其用于收集信息、處理信息及網(wǎng)絡(luò)通信等帶來的能耗[5]。當(dāng)網(wǎng)絡(luò)中一些靜態(tài)傳感器節(jié)點(diǎn)偵測到事件時,處理中心能夠獲知事件發(fā)生地點(diǎn)的所有相關(guān)信息,然后移動傳感器節(jié)點(diǎn)會被派遣到各個事件發(fā)生地點(diǎn)以完成時一步的調(diào)查。在這個移動過程中,會消耗大量能量。本文針對這一問題,首先提出了一種集中式的移動節(jié)點(diǎn)派遣算法,在盡量減少移動傳感器節(jié)點(diǎn)移動總能耗的同時保證移動節(jié)點(diǎn)間的能耗均衡;在此基礎(chǔ)上設(shè)計了一種分布式的移動節(jié)點(diǎn)派遣算法,降低了節(jié)點(diǎn)間的通信數(shù)據(jù)量。最后通過仿真驗證了算法的有效性和實用性。本文的主要貢獻(xiàn)在于(1)在移動傳感器節(jié)點(diǎn)派遣算法設(shè)計中保證移動節(jié)點(diǎn)總能耗較少的同時考慮了節(jié)點(diǎn)的能耗均衡(2)提出的方法適用于無障礙物情況下任意的移動節(jié)點(diǎn)數(shù)量和事件地點(diǎn)數(shù)量關(guān)系(3)提出了集中式和分布式2種移動節(jié)點(diǎn)派遣算法,適應(yīng)不同的應(yīng)用場景。

本文其他部分結(jié)構(gòu)如下:第2小節(jié)對移動傳感器節(jié)點(diǎn)調(diào)度與派遣的相關(guān)工作進(jìn)行了簡要的介紹和總結(jié);第3小節(jié)給出移動傳感器節(jié)點(diǎn)派遣問題的數(shù)學(xué)模型;第4小節(jié)對集中式的能耗均衡節(jié)點(diǎn)派遣算法進(jìn)行詳細(xì)介紹;分布式的派遣算法在第5小節(jié)給出;仿真實驗和實驗結(jié)果的討論在第6小節(jié)進(jìn)行;第7小節(jié)總結(jié)全文并指出未來的研究方向。

1 相關(guān)工作

當(dāng)前有大量針對混合無線傳感器網(wǎng)絡(luò)或移動無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度的研究[6],文獻(xiàn)[7]中提出了一種利用移動信標(biāo)進(jìn)行節(jié)點(diǎn)定位的方法,移動信標(biāo)向最大覆蓋且未被定位節(jié)點(diǎn)區(qū)域移動,主要工作針對移動節(jié)點(diǎn)的路徑規(guī)劃。文獻(xiàn)[8]提出了一種基于虛擬力的混合無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署的方法,這個研究在靜態(tài)傳感器節(jié)點(diǎn)和移動傳感器節(jié)點(diǎn)之間建立了一個虛擬勢場,利用這個虛擬勢場所產(chǎn)生的虛擬力來控制移動傳感器節(jié)點(diǎn)的運(yùn)動,使移動傳感器能自適應(yīng)的調(diào)整自己的位置,完成網(wǎng)絡(luò)部署。文獻(xiàn)[9]中采用移動傳感器節(jié)點(diǎn)來修復(fù)無線傳感器網(wǎng)絡(luò)運(yùn)行中產(chǎn)生的覆蓋空洞。這些研究的側(cè)重點(diǎn)主要是如何調(diào)度移動節(jié)點(diǎn)完成網(wǎng)絡(luò)部署或網(wǎng)絡(luò)空洞的修補(bǔ),與移動節(jié)點(diǎn)派遣問題存在較大差別。

對混合移動傳感器網(wǎng)絡(luò)中的移動節(jié)點(diǎn)派遣問題的相關(guān)研究并不是很多,機(jī)器人的任務(wù)分配問題與本文的研究內(nèi)容近似。Akkaya[10]等人利用stable marriage算法解決移動機(jī)器人事件處理派遣問題,使得機(jī)器人的總移動距離最短,但沒有考慮能耗問題。文獻(xiàn)[11]在考慮能耗均衡的前提下,提出集中式的機(jī)器人-事件匹配算法(PMD)及指派算法(SQD)。一方面,無線傳感器網(wǎng)絡(luò)中并不總是存在能夠完成集中式運(yùn)算的設(shè)備;另一方面,算法不適用于移動節(jié)點(diǎn)數(shù)量小于待處理事件數(shù)量的情況。Verma[12]等人的研究主要針對單一事件的移動機(jī)器人選擇和路徑設(shè)計及導(dǎo)航問題,雖然考慮到了能耗問題,但不適用于事件數(shù)量多于機(jī)器人數(shù)量時的派遣問題。針對上述問題,本文設(shè)計的算法適用于任意的移動傳感器節(jié)點(diǎn)數(shù)量和事件地點(diǎn)數(shù)量的關(guān)系,且在降低總的移動能耗同時,保證節(jié)點(diǎn)間的能耗均衡,并且給出了集中式和分布式的2種算法。

2 移動傳感器節(jié)點(diǎn)派遣問題的數(shù)學(xué)模型

我們考慮一個由靜態(tài)傳感器節(jié)點(diǎn)和移動傳感器節(jié)點(diǎn)組成的混合無線傳感器網(wǎng)絡(luò)。每個傳感器都知道它們自己的位置(可以通過GPS或者其他定位技術(shù)來實現(xiàn)。靜態(tài)傳感器節(jié)點(diǎn)的密度足夠大,使得它們能構(gòu)成一個覆蓋整個傳感區(qū)域的連通的網(wǎng)絡(luò)。它們可以持續(xù)地監(jiān)控環(huán)境中的一些感興趣的信息。n個移動傳感器S={s1,s2,…,sn}被隨機(jī)部署在感知區(qū)域中,當(dāng)靜態(tài)傳感器節(jié)點(diǎn)檢測到事件發(fā)生時,移動傳感器節(jié)點(diǎn)就會被派遣到這些事件地點(diǎn)去做進(jìn)一步檢測。

在移動傳感器節(jié)點(diǎn)派遣問題中,假設(shè)有一個事件地點(diǎn)的集合L={l1,l2,…,lm},每一個事件地點(diǎn)均需一個移動傳感器節(jié)點(diǎn)來訪問。我們允許m和n可以有任意的大小關(guān)系。問題的目標(biāo)就是計算每一個移動傳感器節(jié)點(diǎn)si的派遣計劃SCHsi,使得L中的每一個地點(diǎn)都會且只會被一個移動傳感器節(jié)點(diǎn)訪問一次,且優(yōu)先級高的事件地點(diǎn)會被優(yōu)先訪問到。每一個派遣計劃SCHsi都被表示為一個事件地點(diǎn)的序列,第j個待訪問的事件地點(diǎn)表示為SCHsi[j]。令ei是si的當(dāng)前能量,c(SCHsi)是si要完成派遣計劃所需要的能量,則

c(SCHsi)=Δmove×(d(si,SCHsi[1])+

其中Δmove是移動傳感器移動單位距離所需要的能量,d(si,SCHsi[1])是si的當(dāng)前位置到SCHsi[1]的歐幾里得距離,d(SCHsi[j],SCHsi[j+1])是SCHsi[j]到SCHsi[j+1]的歐幾里得距離。顯然地,派遣計劃必須要滿足ei≥c(SCHsi)。

出于算法性能上的原因,我們?yōu)橐苿觽鞲衅鞴?jié)點(diǎn)派遣問題定義2個目標(biāo)函數(shù)。第1個目標(biāo)函數(shù)是最小化移動傳感器節(jié)點(diǎn)花費(fèi)的總能量,也就是

(1)

第2個目標(biāo)函數(shù)是最大化傳感器移動以后剩余的總能量,也就是

(2)

為了均衡移動傳感器的能量消耗,我們在每一輪為移動傳感器計算派遣計劃時也會同時考慮移動傳感器消耗的能量和剩余的能量的標(biāo)準(zhǔn)差。具體來說,移動傳感器的能量消耗的標(biāo)準(zhǔn)差是:

(3)

移動傳感器的剩余能量的標(biāo)準(zhǔn)差是:

(4)

其中cavg和eavg分別是移動傳感器總消耗能量和總剩余能量的平均值。為了均衡移動傳感器的負(fù)載,我們還需要在計算派遣計劃時根據(jù)采用式(1)還是式(2)作為目標(biāo)函數(shù)而分別最小化式(3)或式(4)。

上述的建模方式不只考慮到了單輪的移動傳感器節(jié)點(diǎn)派遣問題,而是在全局的角度來考慮移動傳感器節(jié)點(diǎn)的派遣調(diào)度。大體上來說就是,我們要計算許多輪的派遣計劃,其中每一輪都要派遣移動傳感器節(jié)點(diǎn)到該輪中檢測到的事件地點(diǎn),算法的整體目標(biāo)是盡可能地延長移動傳感器節(jié)點(diǎn)所能工作的輪數(shù)。每一輪的時間長度取決于用戶實際的實時性要求。由于未來可能會發(fā)生的事件地點(diǎn)無法被事先預(yù)測,所以本研究中只考慮如何優(yōu)化單輪的派遣計劃使得算法達(dá)到上述的目標(biāo)。

3 移動傳感器節(jié)點(diǎn)集中式派遣算法設(shè)計

本章我們提出一個解決移動傳感器節(jié)點(diǎn)派遣問題的集中式的算法CentralLBSD(Centralized Load Balanced Sensor Dispatch Algorithm),這個算法使用一個中心服務(wù)器收集一輪派遣過程中事件地點(diǎn)的集合L和移動傳感器節(jié)點(diǎn)的集合S的信息。算法首先對所有事件地點(diǎn)按照事件優(yōu)先級排序,然后對于每一個相同優(yōu)先級的事件地點(diǎn)集合,算法依次派遣移動傳感器節(jié)點(diǎn)來訪問這些事件地點(diǎn)。為了保證優(yōu)先級低的事件地點(diǎn)不至于一直不被訪問到,每一輪結(jié)束以后,該輪中沒有來得及訪問的事件地點(diǎn)優(yōu)先級會增大,使得它們在下一輪算法運(yùn)行過程中能被優(yōu)先處理。接下來我們討論在某一種優(yōu)先級下的移動傳感器節(jié)點(diǎn)派遣算法的設(shè)計。為了減少傳感器節(jié)點(diǎn)之間的消息傳輸量,我們在下一章又接著提出了一個分布式的解決方案。方便起見,下文中均用|S|表示移動傳感器節(jié)點(diǎn)的數(shù)量,|L|表示待處理的事件地點(diǎn)數(shù)量。

3.1 |S|≥|L|情況下移動傳感器節(jié)點(diǎn)派遣算法設(shè)計

當(dāng)|S|≥|L|時,對于每一個移動傳感器節(jié)點(diǎn)si∈S,我們先計算si移動到每一個事件地點(diǎn)lj∈L所消耗的能量c(si,lj)。我們定義消耗的能量函數(shù)為c(si,lj)=Δmove×d(si,lj).然后構(gòu)造一個帶權(quán)的完全二分圖G=(S∪L,S×L),二分圖G的點(diǎn)集包含了所有的移動傳感器節(jié)點(diǎn)和所有的事件地點(diǎn),對于每一個si∈S和lj∈L,在G里都有一條邊(si,lj)。(si,lj)的權(quán)值定義為:

w(si,lj)=c(si,lj)

(5)

若采用式(5)作為目標(biāo)函數(shù),或者

(6)

若采用式(6)作為目標(biāo)函數(shù),其中emax是一個不小于maxsi∈s{esi}的大數(shù)。為了簡便,我們就令emax=maxsi∈S{esi}。不難看出,目標(biāo)函數(shù)式(5)和式(6)都可以被看成是為了最小化整個匹配的權(quán)值。在圖論中,一個匹配P是一個邊的集合,其中任意兩條邊都沒有公共頂點(diǎn)。在移動傳感器節(jié)點(diǎn)派遣問題中,我們的目標(biāo)就是找到G上的一個匹配P,使得①P里的匹配數(shù)最大,②P中所有邊的權(quán)值和盡可能小,③P的邊權(quán)值的標(biāo)準(zhǔn)差盡可能小。

為了找到匹配P,我們先給每一個si關(guān)聯(lián)一個優(yōu)先列表Plist(si),優(yōu)先列表中包含了所有的lj∈L,且按照權(quán)值w(si,lj)遞增排序。當(dāng)邊權(quán)值相同時,事件地點(diǎn)編號小的排在前面。類似的,對于每一個lj,我們也關(guān)聯(lián)一個優(yōu)先列表Plist(lj),列表中包含了所有的si∈S,按照權(quán)值w(si,lj)遞增排序。移動傳感器節(jié)點(diǎn)與事件地點(diǎn)進(jìn)行匹配時,按列表項從上到下進(jìn)行。

為了減小匹配P的標(biāo)準(zhǔn)差,我們給每一個事件地點(diǎn)lj∈L引入一個界Blj來限制lj可以匹配到的候選移動傳感器節(jié)點(diǎn)。當(dāng)為事件地點(diǎn)lj找匹配的時候,算法只考慮滿足w(si,lj)≤Blj的移動傳感器節(jié)點(diǎn)si。

為了找到匹配P,我們首先初始化每一個界Blj為每一個事件地點(diǎn)可以匹配到的邊的最小值中的平均值,也就是:

(7)

這樣對于每一個事件地點(diǎn)lj∈L,我們試著找到一個移動傳感器節(jié)點(diǎn)si∈Plist(lj)跟來lj匹配,使得w(si,lj)最小并且w(si,lj)≤Blj。如果我們找不到這樣的si,那么我們就要持續(xù)不斷地增大界Blj,界Blj每次增大ΔB,直到事件地點(diǎn)lj能找到一個可用的移動傳感器節(jié)點(diǎn)為止。我們稱ΔB為遞增等級,為了在迭代次數(shù)與每次匹配所得結(jié)果的規(guī)模間取得平衡,遞增等級ΔB的確定公式如下:

(8)

其中δ是遞增等級ΔB的調(diào)整系數(shù)。根據(jù)實驗結(jié)果δ的值為2.0較好,因篇幅有限,不具體展開說明。

當(dāng)一個還未匹配的事件地點(diǎn)lj擴(kuò)大它的界Blj時,就會有更多的候選移動傳感器節(jié)點(diǎn)出現(xiàn)在它的優(yōu)先列表Plist(lj)中。如果此時Plist(lj)中第1個還未訪問的候選移動傳感器節(jié)點(diǎn)si也是還未匹配的狀態(tài),那么就把(si,lj)加入到匹配中。如果移動傳感器節(jié)點(diǎn)si已經(jīng)被跟另一個事件地點(diǎn)lo匹配了,那么根據(jù)lj的界Blj和lo的界Blo,我們就能確定si到底應(yīng)該跟哪個事件地點(diǎn)相匹配。我們稱這是一次lj與lo之間的競爭。當(dāng)以下某一種情況成立時,si就會跟lj相匹配,此時我們就稱lj贏得了競爭。

①Blj>Blo。界的增大會使匹配到一條權(quán)值過高的邊的概率提高,如果lj不和si匹配的話,為了找到可以匹配的移動傳感器節(jié)點(diǎn),lj就必須增大它的界Blj,為了避免Blj擴(kuò)大得太大,所以我們就匹配si和lj。

②Blj=Blo并且lj在si的優(yōu)先列表里出現(xiàn)在lo的前面。由于lj和lo的界相同,si可以任意選擇一個事件地點(diǎn)相匹配,所以si可以選擇一個距離最近的事件地點(diǎn)。由于si到lj的距離比到lo的距離要小,所以我們匹配si和lj來減小總的匹配值。

③Blj=Blo并且si是Plist(lj)里的最后一個候選移動傳感器節(jié)點(diǎn),但不是Plist(lo)里的最后一個候選移動傳感器節(jié)點(diǎn)。因為事件地點(diǎn)lj已經(jīng)不能再從Plist(lj)中挑選其他的候選移動傳感器節(jié)點(diǎn),所以此時si應(yīng)該要跟lj匹配。

圖1 事件地點(diǎn)聚類的例子

一旦移動傳感器節(jié)點(diǎn)si與事件地點(diǎn)lj匹配以后,匹配P中的二元對(si,lo)就應(yīng)該被新的二元對(si,lj)替換,lo要去找其他的移動傳感器節(jié)點(diǎn)來與之相匹配。lo將會與其他的事件地點(diǎn)來競爭移動傳感器節(jié)點(diǎn)。

3.2 |S|<|L|情況下移動傳感器節(jié)點(diǎn)派遣算法設(shè)計

4 移動傳感器節(jié)點(diǎn)分布式派遣算法設(shè)計

在移動傳感器節(jié)點(diǎn)集中式派遣算法中,需要Sink節(jié)點(diǎn)收集移動傳感器節(jié)點(diǎn)和事件地點(diǎn)的信息,這會導(dǎo)致傳感器節(jié)點(diǎn)之間大量的消息傳遞,會使傳感器節(jié)點(diǎn)的能耗增大,縮短整個無線傳感器網(wǎng)絡(luò)的生存壽命。為解決這一問題,我們提出一個移動傳感器節(jié)點(diǎn)分布式派遣算法,算法是基于網(wǎng)格的架構(gòu)[16-17],每個網(wǎng)格頭會收集移動傳感器節(jié)點(diǎn)和事件地點(diǎn)的信息,然后在局部運(yùn)行集中式派遣算法。因此,計算復(fù)雜度和消息的傳輸量都會大大地減少。

為了減少傳感器之間的消息傳輸量,我們要解決2個主要問題。一個是事件地點(diǎn)和移動傳感器節(jié)點(diǎn)之間要如何高效地交換信息使得它們能知道彼此的信息。第2個是當(dāng)事件地點(diǎn)尋找到附近的移動傳感器節(jié)點(diǎn)以后,如何與其他的事件地點(diǎn)競爭這些移動傳感器節(jié)點(diǎn)。為了解決上述的2個問題,我們采用基于網(wǎng)格的技術(shù)來實現(xiàn)。

為了減少消息的傳輸量,我們設(shè)計了一個基于網(wǎng)格結(jié)構(gòu)的分布式移動傳感器節(jié)點(diǎn)派遣算法,我們把這個算法稱為DistLBSD(Distributed Load Balanced Sensor Dispatch Algorithm)算法。在分布式派遣算法中,目標(biāo)感知區(qū)域被分割成一個個的網(wǎng)格,每一個網(wǎng)格是大小為α×α的正方形,如圖2所示。對于每一個網(wǎng)格,我們選舉一個靜態(tài)傳感器節(jié)點(diǎn)作為網(wǎng)格頭來收集這個網(wǎng)格中的信息,要收集的信息包括網(wǎng)格中移動傳感器節(jié)點(diǎn)的數(shù)量和位置信息以及事件地點(diǎn)的數(shù)量和位置信息。移動傳感器節(jié)點(diǎn)會報告它們的位置和剩余的能量給它們所在網(wǎng)格的網(wǎng)格頭。當(dāng)靜態(tài)傳感器節(jié)點(diǎn)監(jiān)測到事件發(fā)生時,它們也會通知它們所在網(wǎng)格的網(wǎng)格頭有事件發(fā)生,我們稱有事件發(fā)生的網(wǎng)格為事件網(wǎng)格。我們假設(shè)網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)都是時間同步的,時間被分割成許多輪,每一輪又進(jìn)一步被分成3個階段。

DistLBSD算法共有3個階段。算法的第1個階段是信息收集階段,在這個階段中每個網(wǎng)格頭會收集自己所屬的網(wǎng)格中的事件地點(diǎn)的信息和移動傳感器節(jié)點(diǎn)的信息。收集完信息后,網(wǎng)格頭會廣播自己網(wǎng)格中存在的移動傳感器節(jié)點(diǎn)的信息,相鄰的網(wǎng)格頭將能夠知道附近網(wǎng)格頭中的信息。算法的第2個階段是競爭階段,在這個階段,事件網(wǎng)格的網(wǎng)格頭會競爭附近可用的移動傳感器節(jié)點(diǎn),網(wǎng)格頭會向附近可用的移動傳感器節(jié)點(diǎn)發(fā)送INV(INVitation)消息,移動傳感器節(jié)點(diǎn)接著會根據(jù)收集到的信息計算派遣計劃。算法最后一個階段是派遣階段,在這個階段移動傳感器節(jié)點(diǎn)會按照計算得到的派遣計劃訪問所有的事件地點(diǎn)。3個階段的具體時間要根據(jù)具體的環(huán)境情況來定。

每一個事件網(wǎng)格的網(wǎng)格頭維護(hù)了一個優(yōu)先列表,這個優(yōu)先列表中包含所有的移動傳感器節(jié)點(diǎn),移動傳感器節(jié)點(diǎn)按照它們消耗的能量排序。出于競爭的目的,每一個網(wǎng)格頭同時維護(hù)一個界,它們會向附近的移動傳感器節(jié)點(diǎn)發(fā)送一個攜帶有界的INV信息來競爭移動傳感器節(jié)點(diǎn)。同時,每一個移動傳感器節(jié)點(diǎn)會維護(hù)一個派遣序列SCHsi來記錄它要訪問的事件網(wǎng)格,SCHsi是一個有最大長度限制的列表,如果SCHsi的長度已經(jīng)達(dá)到最大的話,那么這個移動傳感器節(jié)點(diǎn)將不會再繼續(xù)訪問其他的事件網(wǎng)格。當(dāng)一個移動傳感器節(jié)點(diǎn)si接收到一個邀請消息(INV)時,它并不會馬上對這個消息進(jìn)行回復(fù),而是在接下來的一小段時間內(nèi)繼續(xù)收集更多的INV消息,這個過程會持續(xù)Δt的時間,這個時間可以是幾次數(shù)據(jù)包傳遞的往返時間。接下來,移動傳感器節(jié)點(diǎn)si會查看收到的邀請消息,根據(jù)事件網(wǎng)格的界來決定競爭優(yōu)勝者,把它們記錄在派遣序列SCHsi中并給每一個競爭優(yōu)勝者回復(fù)一個確認(rèn)消息。對于競爭失敗的網(wǎng)格,si會回復(fù)一個拒絕消息,拒絕消息中包含有si的派遣序列SCHsi還能記錄的事件網(wǎng)格數(shù)。事件網(wǎng)格的網(wǎng)格頭將會從自己的優(yōu)先列表中移除那些派遣序列已經(jīng)滿的移動傳感器節(jié)點(diǎn),并試著邀請其他的移動傳感器節(jié)點(diǎn)直到它們收到了來自移動傳感器節(jié)點(diǎn)的確認(rèn)消息或者該輪中所有的移動傳感器節(jié)點(diǎn)都已經(jīng)無法再接受邀請。

4.1 基于網(wǎng)格的消息交換機(jī)制

為了減少網(wǎng)格頭在搜索其他網(wǎng)格里的可用的移動傳感器時的消息傳輸量,我們提出了一種修改的grid-quorum[18]方法。具體地說是,每個網(wǎng)格頭會發(fā)送廣播(ADV)消息給同一列上的其他網(wǎng)格,廣播消息中包含了網(wǎng)格中的移動傳感器的數(shù)量。通過這種方式,每個網(wǎng)格頭將會知道同一列上的所有網(wǎng)格中的移動傳感器信息。當(dāng)一個網(wǎng)格頭想要搜索其他網(wǎng)格中的可用的移動傳感器時,它會發(fā)送一個請求(REQ)消息給同一行上的其他網(wǎng)格頭。明顯地,由于網(wǎng)格的結(jié)構(gòu),必定存在一個網(wǎng)格頭會同時接收到ADV和REQ消息。

圖2 DistLBSD算法工作的例子

為了進(jìn)一步減少在搜索可用移動傳感器時的消息傳輸量,我們引入搜索長度來限制被搜索的網(wǎng)格數(shù)量。每個REQ消息帶有2個參數(shù)β和Mgrid,其中β是搜索長度,Mgrid記錄了已經(jīng)找到的可用移動傳感器的數(shù)量。由于負(fù)載均衡的特性,我們想盡可能多地獲得可用的移動傳感器。在確定的搜索長度里,所有可用的移動傳感器而不是最近的一個會被參與到調(diào)度中來。初始的時候,每個REQ消息里β>0,Mgrid=0.當(dāng)接受到REQ消息時,網(wǎng)格頭會給Mgrid增加該網(wǎng)格所在列上的所有可用移動傳感器的數(shù)量,因為通過ADV消息,它能知道同一列上所有其他網(wǎng)格的信息。如果β>1,網(wǎng)格頭會把β減1,然后把REQ消息向同一行里的下一個網(wǎng)格傳遞。然而,當(dāng)β=1且Mgrid的值還是零時,意味著還沒有找到可用的移動傳感器,此時網(wǎng)格頭還會繼續(xù)發(fā)送β=1的REQ消息給下一個網(wǎng)格直到至少找到一個可用移動傳感器為止。圖2演示了一個例子,其中在初始REQ消息里β=1。當(dāng)接受到REQ消息時,(0,2)里的網(wǎng)格頭把Mgrid的值增加了1,把β的值減少了1。由于β的值減少到了零,REQ消息不會再向左邊傳播了。當(dāng)(2,2)的網(wǎng)格頭收到REQ消息時,它發(fā)現(xiàn)β=1,Mgrid=0,此時(2,2)會繼續(xù)把該REQ消息傳遞給(3,2)來搜索移動傳感器。通過引入搜索長度,DistLBSD不但能減少消息的復(fù)雜度而且能減少來自網(wǎng)格頭的對移動傳感器的競爭。一旦網(wǎng)格頭收集到了移動傳感器和事件的信息,它就能在局部執(zhí)行CentralLBSD算法。

4.2 事件網(wǎng)格競爭移動傳感器節(jié)點(diǎn)的算法

事件網(wǎng)格競爭移動傳感器節(jié)點(diǎn)有3個步驟:

Step 1:每一個事件網(wǎng)格gj首先計算每一個移動傳感器節(jié)點(diǎn)si訪問這個網(wǎng)格的移動代價。移動代價定義為w(si,gj)=d(si,rj)+φ(Lj),其中rj是事件網(wǎng)格gj的中心點(diǎn),Lj是gj中的事件地點(diǎn)的集合。接著,gj把所有可用的移動傳感器節(jié)點(diǎn)放入到一個優(yōu)先列表Plist(gj)中并按移動代價遞增排序。如果一個移動傳感器節(jié)點(diǎn)的剩余能力不足以訪問完gj,那么這個移動傳感器節(jié)點(diǎn)就會從gj的優(yōu)先列表中移除。如果gj的優(yōu)先列表為空,那么gj將不會參加到這一輪的競爭中,但gj可能會參與到未來的競爭當(dāng)中。

Step 2:每一個事件網(wǎng)格gj維護(hù)一個網(wǎng)格優(yōu)先級pj和一個界Bj。初始時,pj是網(wǎng)格中所有事件的優(yōu)先級的平均值,Bj=w(si,gj),其中si是gj的優(yōu)先列表Plist(gj)中的第β個移動傳感器節(jié)點(diǎn)。Plist(gj)中的每一個移動傳感器節(jié)點(diǎn)初始時都是未被請求狀態(tài)的,當(dāng)在當(dāng)前迭代中向某一個移動傳感器節(jié)點(diǎn)發(fā)送一個INV邀請消息時,這個移動傳感器節(jié)點(diǎn)就會標(biāo)記為已請求狀態(tài)。一個移動傳感器節(jié)點(diǎn)si被作為候選者當(dāng)前僅當(dāng)si在Plist(gj)中,且si是未被請求狀態(tài)并且w(si,gj)≤Bj。

Step 3:每一個事件網(wǎng)格gj選擇優(yōu)先列表Plist(gj)中的第1個候選移動傳感器節(jié)點(diǎn)si,向si發(fā)送一個邀請消息INV(gj,pj,w(si,gj),Bj,cj,n),其中cj是Plist(gj)中滿足約束w(si,gj)≤Bj的候選移動傳感器節(jié)點(diǎn)的個數(shù),n是gj在信息收集階段中收集到的可用移動傳感器節(jié)點(diǎn)的總數(shù)量。接著gj等待si的響應(yīng)。如果gj收到了移動傳感器節(jié)點(diǎn)si發(fā)送的確認(rèn)消息的話,則算法終止,gj將會被si所訪問。否則的話,gj應(yīng)該會收到si發(fā)送的拒絕消息,這個拒絕消息中包含si的派遣序列的剩余容量。如果si的派遣序列的剩余容量為零,則gj從它的優(yōu)先列表Plist(gj)中移除si,否則,gj將si標(biāo)記為已請求狀態(tài),并且下面3種情況的其中之一將會被執(zhí)行:

①如果gj在當(dāng)前界Bj下還有候選移動傳感器節(jié)點(diǎn),則重復(fù)步驟3。

②如果gj在當(dāng)前界Bj下沒有候選移動傳感器節(jié)點(diǎn)且Plist(gj)中還有未被請求的移動傳感器節(jié)點(diǎn),則gj增大它的界Bj使得Bj=w(sk,gj),其中sk是當(dāng)前Plist(gj)中的第β個未被請求的移動傳感器節(jié)點(diǎn),重復(fù)步驟3。

③gj已經(jīng)遍歷到Plist(gj)的末尾。如果此時Plist(gj)為空,則算法結(jié)束,該輪中g(shù)j沒有找到移動傳感器節(jié)點(diǎn)來訪問它;若Plist(gj)不為空,則把Plist(gj)中的所有移動傳感器標(biāo)記為未被請求狀態(tài),把網(wǎng)格優(yōu)先級pj的值增加1,重設(shè)Bj=w(si,gj),使得si是Plist(gj)中的第β個未被請求的移動傳感器節(jié)點(diǎn),重復(fù)步驟3。

當(dāng)gj邀請失敗完P(guān)list(gj)中所有的移動傳感器節(jié)點(diǎn)時,情況(3)就發(fā)生了。此時,gj就進(jìn)入了下一輪迭代,重新遍歷一遍Plist(gj)來尋找仍有剩余容量的移動傳感器節(jié)點(diǎn)。在接下來的敘述中,我們會發(fā)現(xiàn)網(wǎng)格優(yōu)先級pj會幫助gj贏得競爭。

4.3 移動傳感器節(jié)點(diǎn)接收競爭的條件

為了解決算法的第3個問題,每一個移動傳感器節(jié)點(diǎn)si維護(hù)一個派遣序列SCHsi來記錄它需要訪問的事件網(wǎng)格。SCHsi的容量設(shè)置為|m/n|,其中m是事件網(wǎng)格的數(shù)量,n是移動傳感器節(jié)點(diǎn)的數(shù)量,m可以在信息收集階段來獲知,n可以從收到的INV消息中獲得,初始時SCHsi為空。一個移動傳感器節(jié)點(diǎn)從不同的INV邀請消息中獲得的n的值有可能不一樣(差異不會太大),我們選取最大的n值來計算。移動傳感器節(jié)點(diǎn)每隔一段Δt的時間就處理一次上個時間段內(nèi)收到的INV邀請消息。對于所有有相同的網(wǎng)格優(yōu)先級值的INV邀請消息,只有一個事件網(wǎng)格會被移動傳感器節(jié)點(diǎn)接收,其他的事件網(wǎng)格都會被拒絕。如果移動傳感器節(jié)點(diǎn)si沒有剩余容量,那么它會發(fā)送一個拒絕消息表面它已經(jīng)沒有剩余容量了。否則的話,所有請求的事件網(wǎng)格中具有相同網(wǎng)格優(yōu)先級的事件網(wǎng)格會競爭SCHsi中的一個位置。具體來說,對于2個邀請消息INV(gj,pj,w(si,gj),Bj,cj,n)和INV(gk,pk=pj,w(si,gk),Bk,ck,n),當(dāng)前僅當(dāng)以下一種條件成立時gj贏得競爭:(1)Bj>Bk;(2)Bj=Bk并且w(si,gj)1。這些條件跟本文第3章中提出的集中式移動傳感器節(jié)點(diǎn)派遣算法的競爭條件類似。接著,移動傳感器節(jié)點(diǎn)si就會分別發(fā)送確認(rèn)消息或者拒絕消息給發(fā)出INV邀請消息的事件網(wǎng)格,并更新自己的派遣序列SCHsi和剩余容量。

4.4 基于TSP的移動傳感器節(jié)點(diǎn)派遣計劃計算方法

最后,我們來討論如何計算每一個移動傳感器節(jié)點(diǎn)的派遣計劃,使得它能以一種節(jié)能的方法來遍歷整個SCHsi序列。我們提出了一個求解兩次TSP問題的方法。每一個移動傳感器節(jié)點(diǎn)si先對派遣序列SCHsi做第1次TSP求解,在第1次求解TSP問題時,我們把派遣序列SCHsi中的每一個事件網(wǎng)格當(dāng)做一個點(diǎn)處理,這個點(diǎn)可以是一個事件網(wǎng)格中所有事件地點(diǎn)的中心點(diǎn)。接著,移動傳感器節(jié)點(diǎn)si對派遣序列SCHsi中的每一個事件網(wǎng)格再分別做一次TSP問題的求解,用于訪問這個事件網(wǎng)格中所有的事件地點(diǎn)。最后,我們合并兩次TSP問題的解,構(gòu)成一個最終的派遣計劃。由于已經(jīng)有許多求解TSP問題的啟發(fā)式算法存在,所以本文就不具體展開求解TSP問題的過程。

5 仿真實驗與分析

為了驗證算法的正確性和設(shè)計合理性,本章使用MATLAB軟件對算法進(jìn)行仿真,主要是通過本文提出引入負(fù)載均衡的2種算法與單輪最優(yōu)算法做比較,從不同角度來論證本文提出的算法的有效性。

5.1 仿真實驗設(shè)計

實驗建立在一個450 m×300 m的矩形感知區(qū)域,在這個感知區(qū)域里等概率地隨機(jī)部署400個靜態(tài)傳感器節(jié)點(diǎn)和50個移動傳感器節(jié)點(diǎn)。根據(jù)文獻(xiàn)[19]的研究結(jié)果,設(shè)定每一個移動傳感器節(jié)點(diǎn)初始時有3960 J(焦耳)的能量,移動時消耗的單位能量是8.27 J/m。靜態(tài)傳感器節(jié)點(diǎn)和移動傳感器節(jié)點(diǎn)的通信半徑分別是150 m和80 m,這樣所有的傳感器能構(gòu)成一個連通的網(wǎng)絡(luò)。

5.2 仿真結(jié)果與分析

我們先來考察不同算法的系統(tǒng)生命期。我們使用50個移動傳感器節(jié)點(diǎn)來一輪一輪的訪問事件地點(diǎn)。在每一輪中,隨機(jī)選擇10～15個靜態(tài)傳感器節(jié)點(diǎn)作為事件地點(diǎn)。我們主要觀察每一輪中存活的移動傳感器節(jié)點(diǎn)的百分比。當(dāng)存活移動傳感器節(jié)點(diǎn)的數(shù)量少于事件地點(diǎn)時,就采用我們提出的聚類算法先對事件地點(diǎn)分組。系統(tǒng)的生存壽命被定義為存活移動傳感器節(jié)點(diǎn)百分比降低為0時經(jīng)過的輪數(shù)。圖3展示了式(1)和式(2)分別作為目標(biāo)函數(shù)優(yōu)化時的系統(tǒng)生存壽命,式(1)作為目標(biāo)函數(shù)時,算法優(yōu)化的目標(biāo)是最小化每輪移動消耗,式(2)作為目標(biāo)函數(shù)優(yōu)化時,算法優(yōu)化的目標(biāo)是最大化剩余能量。從圖3中可以看出,當(dāng)考慮移動傳感器節(jié)點(diǎn)的剩余能量時,3種算法都會有一個更長的系統(tǒng)生命周期。盡管單輪最優(yōu)算法每一輪都會以最少的總能量消耗來派遣移動傳感器節(jié)點(diǎn),但是這個算法總是會得到最短的生命周期。這是因為單輪最優(yōu)算法沒有均衡移動傳感器節(jié)點(diǎn)的負(fù)載,使得一些移動傳感器節(jié)點(diǎn)過早地耗盡它們的能量。這些過早耗盡能量的移動傳感器節(jié)點(diǎn)會加重剩余存活移動傳感器節(jié)點(diǎn)的負(fù)擔(dān),讓它們有很大的負(fù)載,令情況變得更加糟糕。本文提出的算法由于不僅嘗試最優(yōu)化目標(biāo)函數(shù)而且均衡移動傳感器節(jié)點(diǎn)的負(fù)載,使得算法能得到一個更長的生命周期。注意到CentralLBSD算法的性能要優(yōu)于DistLBSD算法的性能,因為CentralLBSD擁有整個網(wǎng)絡(luò)的信息。

圖3 網(wǎng)絡(luò)生存壽命的比較

盡管CentralLBSD算法擁有比DistLBSD算法要優(yōu)的網(wǎng)絡(luò)生存壽命和負(fù)載均衡效果,但是CentralLBSD算法會產(chǎn)生大量的消息傳輸量。圖4演示了CentralLBSD算法和DistLBSD算法產(chǎn)生的數(shù)據(jù)包數(shù)量隨著事件地點(diǎn)數(shù)量的變化而變化的圖。從圖中可以觀察到CentralLBSD算法產(chǎn)生的消息傳輸量隨著事件地點(diǎn)的增加而增加的非?？?而DistLBSD算法的消息傳輸量則基本保持不變,因為消息交換的負(fù)載分散在網(wǎng)格頭之間。

圖4 消息傳輸數(shù)量的比較

圖5 平均能量消耗

圖5比較了3種算法的平均能量消耗。由于單輪最優(yōu)算法總是會找單輪的最優(yōu)解,所以它會有一個最少的平均能量消耗。通過使用優(yōu)先列表,本研究提出的算法的平均能量消耗會比最優(yōu)解稍稍高一點(diǎn)。在DistLBSD算法中,搜索長度的使用會防止事件所在的網(wǎng)格頭搜索那些距離很遠(yuǎn)的移動傳感器節(jié)點(diǎn),這樣就使得算法的平均能量消耗比CentralLBSD算法要小。

圖6比較了3種算法的能量消耗的標(biāo)準(zhǔn)差。從圖中可以觀察到單輪最優(yōu)算法的標(biāo)準(zhǔn)差是CentralLBSD算法的兩倍,說明單輪最優(yōu)算法會造成移動傳感器節(jié)點(diǎn)的負(fù)載很不均衡。DistLBSD算法的標(biāo)準(zhǔn)差要比CentralLBSD算法高,因為每個網(wǎng)格頭只能獲得部分移動傳感器節(jié)點(diǎn)的信息。

圖6 能量消耗的標(biāo)準(zhǔn)差

6 結(jié)論

本論文研究了混合無線傳感器網(wǎng)絡(luò)中如何有效派遣移動傳感器節(jié)點(diǎn)訪問事件地點(diǎn)的問題。針對移動傳感器節(jié)點(diǎn)的負(fù)載均衡問題,本文首先提出了一個集中式的移動傳感器節(jié)點(diǎn)派遣算法CentralLBSD算法。本文對移動傳感器節(jié)點(diǎn)的派遣問題進(jìn)行數(shù)學(xué)建模,并提出了一個集中式的移動傳感器節(jié)點(diǎn)派遣算法CentralLBSD,使之可以適用于任意數(shù)量的移動傳感器節(jié)點(diǎn)和任意數(shù)量的事件地點(diǎn)之間的派遣問題。為了減小網(wǎng)絡(luò)中節(jié)點(diǎn)之間的消息傳輸量,接著又提出了一個分布式的移動傳感器節(jié)點(diǎn)派遣算法DistLBSD。DistLBSD可以有效降低節(jié)點(diǎn)之間的消息傳輸量。仿真實驗表明本文提出的2個移動傳感器節(jié)點(diǎn)派遣算法不但能夠降低節(jié)點(diǎn)移動的總能耗,同時保證了節(jié)點(diǎn)間的能耗均衡,從而延長整個網(wǎng)絡(luò)的生存期。集中式的算法節(jié)能效果更好,但網(wǎng)絡(luò)中的通信量較大,適用于中小規(guī)模,且配備了計算能力較強(qiáng)的Sink節(jié)點(diǎn)的網(wǎng)絡(luò);而分布式的算法也提供了可用的節(jié)能效果,且網(wǎng)間通信量較小,適用與較大型的WSN應(yīng)用場景。未來的工作可以在此基礎(chǔ)上考慮處理時間受限和網(wǎng)絡(luò)中存在障礙物的情況,進(jìn)一步提高算法的實用性,并通過實物實驗進(jìn)行驗證。

[1] Zhang L,Shao Y,Zhu R,et al. Sensor Deployment for Full Detection on Delay Tolerant Event in Hybrid Wireless Sensor Networks[J]. Sensor Letters,2013,11(5):900-909.

[2]Ko R S. Analyzing the Redeployment Problem of Mobile Wireless Sensor Networks Via Geographic Models[J]. Wireless Communications and Mobile Computing,2013,13(2):111-129.

[3]Yan Chang,Shukui Zhang,Yang Zhang. Uncertainty-Aware Sensor Deployment Strategy in Mixed Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks. 2013,Article ID:834704.

[4]Pantazis N A,Nikolidakis S A,Vergados D D. Energy-Efficient Routing Protocols in Wireless Sensor Networks:A Survey[J]. Communications Surveys and Tutorials,IEEE,2013,15(2):551-591.

[5]Mei Y G,Lu Y H,Hu Y C,et al. Lee. Deployment Strategy for Mobile Robots with Energy and Timing Constraints[C]//Proc IEEE Int’l Conf Robotics and Automation,2005:2816-2821.

[6]李明. 基于差分算法的異構(gòu)無線傳感器網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度方案[J]. 傳感技術(shù)學(xué)報,2012,25(6):826-830.

[7]劉輝亞,徐建波. 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的移動信標(biāo)節(jié)點(diǎn)路徑規(guī)劃[J]. 傳感技術(shù)學(xué)報,2010,23(6):873-877.

[8]周彤,洪炳镕,樸松昊. 基于虛擬力的混合感知網(wǎng)節(jié)點(diǎn)部署[J]. 計算機(jī)研究與發(fā)展,2007,44(6):965-972.

[9]王良民,李菲,秦穎. 基于移動節(jié)點(diǎn)無線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)方法[J]. 通信學(xué)報,2011,32(4):1-8.

[10]Akkaya K,Guneydas I,Biak A. Autonomous Actor Positioning in Wireless Sensor and Actor Networks Using Stable-Matching[J]. International Journal of Parallel,Emergent and Distributed Systems,2010,(25):439-464.

[11]Milan Lukic,Ivan Stojmenovic. Energy-Balanced Matching and Sequence Dispatch of Robots to Events:Pairwise Exchanges and Sensor Assisted Robot Coordination[C]//MASS. 2013:249-253.

[12]Verma A,Sawant H,Tan J. Selection and Navigation of Mobile Sensor Nodes Using a Sensor Network[J]. Pervasive and Mobile Computing,2006,2(1):65-84.

[13]Bl?ser M. A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality[J]. ACM-SIAM Symp on Discrete Algorithms,2003:638-645.

[14]Bramer M. Principles of Data Mining[M]. Springer,2013.

[15]Cormen T H,Leiserson C E,Rivest R L,et al. Introduction to Algorithms[M]. The MIT Press,2001.

[16]Li X,Santoro N,Stojmenovic I. Localized Distance-Sensitive Service Discovery in Wireless Sensor and Actor Networks[J]. IEEE Trans Comput,2009,58(9):1275-1288.

[17]Lukic M,Mezei I. Distributed Distance Sensitive Imesh Based Service Discovery in Dense Wsan[C]//Ad-Hoc,Mobile,and Wireless Networks,Ser. Lecture Notes in Computer Science. Springer Berlin/Heidelberg,2012,(7363):435-448.

[18]Wang G,Cao G,Porta T L,et al. Sensor Relocation in Mobile Sensor Networks[C]//IEEE Infocom,2005:2302-2312.

[19]Rahimi M,Shah H,Sukhatme G S,et al. Studying the Feasibility of Energy Harvesting in a Mobile Sensor Network[C]//Proc IEEE Int’l Conf Robotics and Automation,2003:19-24.

苗春雨(1978-),男,副教授,博士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)、可信計算等;

戴國勇(1983-),男,講師,博士研究生,主要研究方向是無線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)安全等;

陳慶章(1956-),男,教授,博士生導(dǎo)師,主要研究方向是無線傳感器網(wǎng)絡(luò)、分布式處理與協(xié)同工作等。

Energy-BalancedMobileSensorsDispatchAlgorithm*

MIAOChunyu1,2,DAIGuoyong1,CHENYuzheng1,CHENQinzhang2*

(1.Department of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310014,China;2.Xingzhi College,Zhejiang Normal University,Jinhua Zhejiang 321004,China)

In a hybrid wireless sensor network,the most energy-cost operation of mobile sensors is movement. It is a challenging research topic that how to reduce the moving cost of mobile sensors while allow it completing the task. A mobile sensor dispatch algorithm that can balance the load of each mobile sensor is proposed,and it can be applied for any number of mobile sensors and event locations. When there are more mobile sensors than event locations,it translates the problem into a maximum bipartite matching problem. When there are less mobile sensors than event locations,it first clustering the event locations,then dispatching each mobile sensor to one cluster of event locations. In order to reduce the amount of message transmission between sensors,this paper further proposes a distributed algorithm. Simulation results show that the distributed algorithm can effectively reduce the amount of message transmission and the whole algorithm can efficiently extend system lifetime.

wireless sensor networks;mobile sensors dispatch;load balance;maximum match

項目來源:國家自然科學(xué)基金項目(61379023)

2014-06-11修改日期:2014-07-19

10.3969/j.issn.1004-1699.2014.09.019

TP393.17

:A

:1004-1699(2014)09-1260-09