苗春雨,戴國(guó)勇,陳宇錚,陳慶章

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

?

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

苗春雨1,2,戴國(guó)勇1,陳宇錚1,陳慶章2*

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

(1)

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

(2)

為了均衡移動(dòng)傳感器的能量消耗,我們?cè)诿恳惠啚橐苿?dòng)傳感器計(jì)算派遣計(jì)劃時(shí)也會(huì)同時(shí)考慮移動(dòng)傳感器消耗的能量和剩余的能量的標(biāo)準(zhǔn)差。具體來(lái)說(shuō),移動(dòng)傳感器的能量消耗的標(biāo)準(zhǔn)差是:

(3)

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

(4)

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

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

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

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

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

當(dāng)|S|≥|L|時(shí),對(duì)于每一個(gè)移動(dòng)傳感器節(jié)點(diǎn)si∈S,我們先計(jì)算si移動(dòng)到每一個(gè)事件地點(diǎn)lj∈L所消耗的能量c(si,lj)。我們定義消耗的能量函數(shù)為c(si,lj)=Δmove×d(si,lj).然后構(gòu)造一個(gè)帶權(quán)的完全二分圖G=(S∪L,S×L),二分圖G的點(diǎn)集包含了所有的移動(dòng)傳感器節(jié)點(diǎn)和所有的事件地點(diǎn),對(duì)于每一個(gè)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是一個(gè)不小于maxsi∈s{esi}的大數(shù)。為了簡(jiǎn)便,我們就令emax=maxsi∈S{esi}。不難看出,目標(biāo)函數(shù)式(5)和式(6)都可以被看成是為了最小化整個(gè)匹配的權(quán)值。在圖論中,一個(gè)匹配P是一個(gè)邊的集合,其中任意兩條邊都沒(méi)有公共頂點(diǎn)。在移動(dòng)傳感器節(jié)點(diǎn)派遣問(wèn)題中,我們的目標(biāo)就是找到G上的一個(gè)匹配P,使得①P里的匹配數(shù)最大,②P中所有邊的權(quán)值和盡可能小,③P的邊權(quán)值的標(biāo)準(zhǔn)差盡可能小。

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

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

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

(7)

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

(8)

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

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

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

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

③Blj=Blo并且si是Plist(lj)里的最后一個(gè)候選移動(dòng)傳感器節(jié)點(diǎn),但不是Plist(lo)里的最后一個(gè)候選移動(dòng)傳感器節(jié)點(diǎn)。因?yàn)槭录攸c(diǎn)lj已經(jīng)不能再?gòu)腜list(lj)中挑選其他的候選移動(dòng)傳感器節(jié)點(diǎn),所以此時(shí)si應(yīng)該要跟lj匹配。

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

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

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

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

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

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

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

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

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

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

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

圖2 DistLBSD算法工作的例子

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

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

事件網(wǎng)格競(jìng)爭(zhēng)移動(dòng)傳感器節(jié)點(diǎn)有3個(gè)步驟:

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

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

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

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

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

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

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

4.3 移動(dòng)傳感器節(jié)點(diǎn)接收競(jìng)爭(zhēng)的條件

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

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

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

5 仿真實(shí)驗(yàn)與分析

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

5.1 仿真實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

圖5 平均能量消耗

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

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

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

6 結(jié)論

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

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

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

[9]王良民,李菲,秦穎. 基于移動(dòng)節(jié)點(diǎn)無(wú)線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)方法[J]. 通信學(xué)報(bào),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-),男,副教授,博士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、可信計(jì)算等;

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

陳慶章(1956-),男,教授,博士生導(dǎo)師,主要研究方向是無(wú)線傳感器網(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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(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