帶有能量補(bǔ)給的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?/h1>

2015-09-29 04:49:38馬晨明王萬(wàn)良姚信威

電信科學(xué)訂閱 2015年8期 收藏

關(guān)鍵詞：網(wǎng)絡(luò)拓?fù)?/a>消息半徑

馬晨明 ，王萬(wàn)良 ，洪 榛 ，姚信威

（1.浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023；2.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310023；3.浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院 杭州 310018）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)作為物聯(lián)網(wǎng)底層的重要組成部分，已經(jīng)受到了國(guó)內(nèi)外的廣泛關(guān)注[1]。受到成本和體積的限制，傳感器節(jié)點(diǎn)的能量一直是值得高度關(guān)注的問(wèn)題。拓?fù)淇刂芠2]是無(wú)線傳感器網(wǎng)絡(luò)中節(jié)約能量、增加運(yùn)行時(shí)間的關(guān)鍵技術(shù)，可以均衡網(wǎng)絡(luò)的能耗，最終達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命時(shí)間的目的。拓?fù)淇刂浦饕赏負(fù)錁?gòu)建和拓?fù)渚S護(hù)[3]組成，拓?fù)錁?gòu)建用于優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，減少節(jié)點(diǎn)之間的通信干擾；拓?fù)渚S護(hù)是恢復(fù)、輪換、再生成拓?fù)涞倪^(guò)程，節(jié)點(diǎn)在拓?fù)錁?gòu)建后將啟動(dòng)拓?fù)渚S護(hù)以保障網(wǎng)絡(luò)的有效運(yùn)行。

LBCDS[4]是一種集中式的拓?fù)錁?gòu)建算法，由某個(gè)節(jié)點(diǎn)對(duì)全局網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行搜集，然后再開始運(yùn)行具體算法。算法首先計(jì)算網(wǎng)絡(luò)的平均節(jié)點(diǎn)度，然后采用貪心的思想依次選擇節(jié)點(diǎn)度最接近于平均節(jié)點(diǎn)度的節(jié)點(diǎn)作為活躍節(jié)點(diǎn)直到網(wǎng)絡(luò)完全連通。但是，該算法需要較長(zhǎng)的計(jì)算時(shí)間，同時(shí)也沒(méi)有考慮節(jié)點(diǎn)的剩余能量的影響。

MIP-MCDS[5]和 NMIP-MCDS[6]采用令牌流對(duì)拓?fù)錁?gòu)建問(wèn)題進(jìn)行數(shù)學(xué)建模，以最小化網(wǎng)絡(luò)分發(fā)的令牌作為目標(biāo)函數(shù)，求解完畢后，各個(gè)持有令牌的節(jié)點(diǎn)組成最小連通支配集。但是，該類算法需要獲得全網(wǎng)的拓?fù)浣Y(jié)構(gòu)信息，因此存在計(jì)算復(fù)雜度高、求解速度慢等問(wèn)題。

EBCDS[7]是一種分布式拓?fù)錁?gòu)建算法，可以應(yīng)用在節(jié)點(diǎn)比較密集的環(huán)境中。首先選擇能量水平和節(jié)點(diǎn)度均較大的節(jié)點(diǎn)構(gòu)造最大獨(dú)立集，然后啟動(dòng)一個(gè)超時(shí)搜集三跳內(nèi)的路徑消息，超時(shí)結(jié)束后由ID較小的節(jié)點(diǎn)選擇較優(yōu)的路徑連通。但是，EBCDS將三跳鄰域中所有節(jié)點(diǎn)均進(jìn)行了連通，導(dǎo)致產(chǎn)生的連通支配集規(guī)模較大，同時(shí)算法的消息復(fù)雜度也較高。

以上文獻(xiàn)關(guān)注如何構(gòu)建高效的網(wǎng)絡(luò)拓?fù)?，而參考文獻(xiàn)[8]指出選擇合適的拓?fù)渚S護(hù)策略將大大增加網(wǎng)絡(luò)的生命時(shí)間。參考文獻(xiàn)[9]提出的拓?fù)渚S護(hù)方法以最小能量為目標(biāo)簡(jiǎn)化網(wǎng)絡(luò)拓?fù)洌?dāng)節(jié)點(diǎn)發(fā)現(xiàn)它的鄰居節(jié)點(diǎn)出現(xiàn)故障后，它會(huì)重新運(yùn)行拓?fù)錁?gòu)建算法以連通網(wǎng)絡(luò)。參考文獻(xiàn)[10]采用的是基于時(shí)間的拓?fù)渚S護(hù)策略，即定期觸發(fā)拓?fù)渚S護(hù)以平衡節(jié)點(diǎn)的能耗。參考文獻(xiàn)[11]對(duì)每個(gè)簇進(jìn)行單獨(dú)維護(hù)，當(dāng)簇頭的剩余能量低于簇內(nèi)平均剩余能量時(shí)，需要選舉新的簇頭。算法要求保證新簇頭和原簇頭之間的距離小于k×d0/n，同時(shí)還需要簇頭滿足剩余能量大于簇內(nèi)成員的平均能量。假設(shè)網(wǎng)絡(luò)不存在這樣的節(jié)點(diǎn)，原簇頭會(huì)一直運(yùn)行，直到能量耗盡。

以上算法針對(duì)拓?fù)錁?gòu)建或拓?fù)渚S護(hù)單獨(dú)進(jìn)行研究，而沒(méi)有將兩個(gè)過(guò)程很好地進(jìn)行結(jié)合，同時(shí)以上算法均假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)性能完全相同，沒(méi)有考慮到可能存在不同計(jì)算、通信半徑或能量水平的節(jié)點(diǎn)，這在實(shí)際研究中是缺乏應(yīng)用價(jià)值的。參考文獻(xiàn)[12]將拓?fù)錁?gòu)建和拓?fù)渚S護(hù)進(jìn)行結(jié)合，同時(shí)考慮了節(jié)點(diǎn)通信半徑異構(gòu)的問(wèn)題，算法在初始時(shí)采用了兩輪消息交換的方式獲得鄰居節(jié)點(diǎn)信息，但是在通信開銷上仍然可以進(jìn)一步優(yōu)化。隨著節(jié)點(diǎn)能量采集技術(shù)的完善，節(jié)點(diǎn)已經(jīng)可以將周圍環(huán)境中的太陽(yáng)光照、熱力溫差、機(jī)械振動(dòng)、氣流和壓力變化等能源持續(xù)不斷地轉(zhuǎn)化為可用的電能[13]，這對(duì)延長(zhǎng)網(wǎng)絡(luò)的生命時(shí)間起到了重要的作用。

為了考慮節(jié)點(diǎn)能量采集技術(shù)對(duì)拓?fù)淇刂扑惴óa(chǎn)生的影響，同時(shí)進(jìn)一步降低當(dāng)前算法的通信開銷并優(yōu)化網(wǎng)絡(luò)的生命時(shí)間，本文在節(jié)點(diǎn)的通信半徑和能量水平存在異構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)模型中，提出了一種同時(shí)包含拓?fù)錁?gòu)建和拓?fù)渚S護(hù)過(guò)程的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?HELM)。算法首先運(yùn)行拓?fù)錁?gòu)建過(guò)程，以較小的通信開銷生成連通支配集，然后利用鄰域節(jié)點(diǎn)信息并結(jié)合時(shí)間、能量和故障的觸發(fā)條件，提出了一種由sink節(jié)點(diǎn)執(zhí)行決策的拓?fù)渚S護(hù)算法，進(jìn)一步優(yōu)化了A3M[12]算法在拓?fù)錁?gòu)建和拓?fù)渚S護(hù)過(guò)程中的能耗，并最大限度地延長(zhǎng)網(wǎng)絡(luò)的運(yùn)行時(shí)間。

2 系統(tǒng)模型

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

用圖G(V,E)表示該網(wǎng)絡(luò)模型，其中，V是節(jié)點(diǎn)集合，E是由V中節(jié)點(diǎn)組成的通信鏈路集合，假設(shè)：

·N個(gè)節(jié)點(diǎn)隨機(jī)部署在M×M的區(qū)域中；

·sink節(jié)點(diǎn)位于中心（M/2，M/2），且計(jì)算、存儲(chǔ)和能量均不受限制；

·為了能夠更好地控制成本，網(wǎng)絡(luò)由小部分高級(jí)節(jié)點(diǎn)和大部分普通節(jié)點(diǎn)組成，高級(jí)節(jié)點(diǎn)具有能量采集能力，而普通節(jié)點(diǎn)只含有有限的電池能量。節(jié)點(diǎn)通過(guò)ID進(jìn)行唯一標(biāo)識(shí)，不需要配備GPS獲得位置信息；

·節(jié)點(diǎn)可以通過(guò)接收信息的信號(hào)強(qiáng)度RSSI獲得鄰居節(jié)點(diǎn)之間的距離d；

·假設(shè)所有節(jié)點(diǎn)的通信半徑R∈[Rmin,Rmax]，則節(jié)點(diǎn)vi和vj之間存在通信鏈路 （當(dāng)且僅當(dāng)vi和vj相互處于對(duì)方的通信半徑內(nèi)）；

·初始網(wǎng)絡(luò)拓?fù)錇槿B通圖。

2.2 能量補(bǔ)給模型

目前，傳感器節(jié)點(diǎn)的能量采集類型以太陽(yáng)能和振動(dòng)能為主，其中，太陽(yáng)能的功率密度為10～15 mW/cm3，振動(dòng)能功率密度約為0.275 mW/cm3?？紤]到太陽(yáng)能受到夜晚無(wú)光照的限制，本文研究?jī)?nèi)容以振動(dòng)能為主，采用與參考文獻(xiàn)[14]相同的振動(dòng)能源能量補(bǔ)給模型，假設(shè)振動(dòng)中心獲得的振動(dòng)能量最大，所有節(jié)點(diǎn)獲得的能量與振動(dòng)中心的距離成反比，這樣不同位置由于機(jī)械振動(dòng)強(qiáng)度不同，則所獲得的能量補(bǔ)給大小也不同。

3 拓?fù)錁?gòu)建

在通信半徑相同的網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)u收到鄰居節(jié)點(diǎn)v的消息后，可以確定u、v處于同一通信半徑內(nèi)。當(dāng)節(jié)點(diǎn)的通信半徑存在異構(gòu)時(shí)，參考文獻(xiàn)[12]采用兩輪消息交換的方式以獲得鄰居節(jié)點(diǎn)信息，但是這會(huì)增加通信開銷。通過(guò)比較節(jié)點(diǎn)之間的距離與通信半徑，只需要一次信息交換就能確定節(jié)點(diǎn)之間是否可以通信。假設(shè)節(jié)點(diǎn)u收到了v發(fā)送的hello消息，通過(guò)信號(hào)強(qiáng)度RSSI可以獲得u、v之間的距離 d（u,v），然后和通信半徑 Ru進(jìn)行比較，如果 Ru≥d（u,v）就可以確定節(jié)點(diǎn)之間可以通信，這樣就確定了網(wǎng)絡(luò)中的鄰居節(jié)點(diǎn)集合。

下面對(duì)算法的相關(guān)術(shù)語(yǔ)進(jìn)行描述。

·節(jié)點(diǎn)的顏色：白色，初始狀態(tài)；紅色，中間狀態(tài)；黑色，活躍節(jié)點(diǎn)；灰色，普通節(jié)點(diǎn)。

·N1:節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合。

·Hop:節(jié)點(diǎn)距離sink節(jié)點(diǎn)的跳數(shù)。

·E、Emax:分別表示節(jié)點(diǎn)的當(dāng)前剩余能量和最大初始能量。

·R、Rmax:分別表示節(jié)點(diǎn)的通信半徑和網(wǎng)絡(luò)中最大節(jié)點(diǎn)的通信半徑。

·權(quán)值w1:支配節(jié)點(diǎn)不僅需要較高的剩余能量，還要考慮節(jié)點(diǎn)的能量采集能力，另外優(yōu)先選擇通信半徑大、節(jié)點(diǎn)之間距離遠(yuǎn)的節(jié)點(diǎn)，這樣可以減少支配集的規(guī)模，∑Eharvest(u)表示節(jié)點(diǎn)從上次成為活躍節(jié)點(diǎn)后到當(dāng)前時(shí)間所采集的能量之和。

·competition(ID,E,Hop,First)消息:First表示最早收到的發(fā)送節(jié)點(diǎn)ID。

算法的主要思想是權(quán)值最大的節(jié)點(diǎn)會(huì)最先廣播competition消息而成為活躍節(jié)點(diǎn)。初始時(shí)，sink廣播competition消息而變成紅色，然后等待時(shí)間T1確定自己能否成為活躍節(jié)點(diǎn)。節(jié)點(diǎn)v收到消息后，先確認(rèn)是否鄰居節(jié)點(diǎn)，如果發(fā)現(xiàn)自己的Hop屬性還沒(méi)有初始化或小于當(dāng)前Hop+1，則進(jìn)行更新，然后將鄰居節(jié)點(diǎn)信息存儲(chǔ)到N1。如果當(dāng)前節(jié)點(diǎn)是白色，啟動(dòng)與w1成反比的定時(shí)器T2。時(shí)間T2內(nèi)，節(jié)點(diǎn)收到滿足連通性的消息時(shí)，則對(duì)N1進(jìn)行更新。當(dāng)T2結(jié)束，當(dāng)前節(jié)點(diǎn)v設(shè)置First并廣播一個(gè)competition消息。如果在時(shí)間T1內(nèi)，上層的紅色鄰居節(jié)點(diǎn)u收到了該消息，發(fā)現(xiàn)First==IDu，則當(dāng)前節(jié)點(diǎn)成為黑色節(jié)點(diǎn)，否則查看First對(duì)應(yīng)的ID是否在N1中，如果存在，則將它的顏色標(biāo)記為黑色。時(shí)間T1結(jié)束后，如果當(dāng)前節(jié)點(diǎn)仍然沒(méi)有收到First==IDu的消息，則當(dāng)前節(jié)點(diǎn)變成灰色節(jié)點(diǎn)。

圖1給出了HELM算法的一個(gè)運(yùn)行實(shí)例。初始時(shí)，節(jié)點(diǎn) S廣播 competition消息，節(jié)點(diǎn) A、B、C、D、E、F 處于 S的通信半徑內(nèi)，將能收到S的消息，B不是S的鄰居節(jié)點(diǎn)，這是因?yàn)楣?jié)點(diǎn)B的通信半徑RB

4 拓?fù)渚S護(hù)

本節(jié)提出了一種面向時(shí)間、能量、故障觸發(fā)機(jī)制的混合型拓?fù)渚S護(hù)算法。算法結(jié)合靜態(tài)和動(dòng)態(tài)拓?fù)渚S護(hù)的優(yōu)點(diǎn)，根據(jù)當(dāng)前網(wǎng)絡(luò)狀況選擇局部或全局拓?fù)湫迯?fù)策略，以達(dá)到最小化網(wǎng)絡(luò)能耗的目的。局部拓?fù)湫迯?fù)是在能量不足或失效的節(jié)點(diǎn)鄰域內(nèi)生成替代節(jié)點(diǎn)，可快速恢復(fù)網(wǎng)絡(luò)，所需要的時(shí)延和能耗也較少；全局拓?fù)湫迯?fù)需要對(duì)全網(wǎng)進(jìn)行重構(gòu)，這樣會(huì)消耗過(guò)多的能量而影響網(wǎng)絡(luò)的生命。拓?fù)渚S護(hù)過(guò)程描述如下。

圖1 拓?fù)錁?gòu)建算法的運(yùn)行實(shí)例

在拓?fù)錁?gòu)建結(jié)束后，節(jié)點(diǎn)首先會(huì)對(duì)鄰居節(jié)點(diǎn)計(jì)算權(quán)值w2，然后按照w2的大小進(jìn)行排序，得到有關(guān)節(jié)點(diǎn)的ID、顏色和w2的列表FList。w2計(jì)算如式(2)，這里考慮節(jié)點(diǎn)之間的距離越近，那么鄰居節(jié)點(diǎn)的權(quán)值w2就越高，因?yàn)閮蓚€(gè)節(jié)點(diǎn)如果位于同一位置，那么該節(jié)點(diǎn)自然也就可以覆蓋當(dāng)前節(jié)點(diǎn)所需要覆蓋的節(jié)點(diǎn)，而此時(shí)由于已經(jīng)搜集了鄰域的節(jié)點(diǎn)能量，可以使用相對(duì)剩余能量來(lái)替代能量。

然后，各個(gè)節(jié)點(diǎn)會(huì)通過(guò)虛擬骨干向sink節(jié)點(diǎn)發(fā)送一個(gè)有關(guān)本地拓?fù)涞膌ocal message，消息中包括節(jié)點(diǎn)的ID和FList。由于sink節(jié)點(diǎn)不受性能的約束，可以建立一個(gè)全局拓?fù)?，利用該信息可以?duì)失效或者能量不足的節(jié)點(diǎn)執(zhí)行快速修復(fù)，下面對(duì)3種觸發(fā)機(jī)制進(jìn)行描述。

基于時(shí)間觸發(fā)的機(jī)制是在sink節(jié)點(diǎn)中進(jìn)行，sink節(jié)點(diǎn)記錄每次發(fā)生全局拓?fù)湫迯?fù)的時(shí)間，然后每隔一定的時(shí)間執(zhí)行該過(guò)程以平衡節(jié)點(diǎn)之間的能耗。

基于故障觸發(fā)的機(jī)制是在當(dāng)前的節(jié)點(diǎn)失效后的γ時(shí)間后觸發(fā)，如果sink節(jié)點(diǎn)在一定的間隔中沒(méi)有收到節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，就會(huì)認(rèn)為該節(jié)點(diǎn)失效了，然后開始執(zhí)行拓?fù)渚S護(hù)策略。

基于能量觸發(fā)機(jī)制是在節(jié)點(diǎn)的剩余能量小于閾值時(shí)，向sink節(jié)點(diǎn)發(fā)送reconstruction消息 (send,gateway,sink)請(qǐng)求網(wǎng)絡(luò)重建，其中，send表示發(fā)送節(jié)點(diǎn)ID，gateway表示下一跳節(jié)點(diǎn)ID，sink表示基站ID。reconstruction消息沿著gateway向sink節(jié)點(diǎn)發(fā)送，如果當(dāng)前節(jié)點(diǎn)ID不等于sink，節(jié)點(diǎn)繼續(xù)選擇合適的gateway進(jìn)行轉(zhuǎn)發(fā)。信息到達(dá)基站后，sink節(jié)點(diǎn)開始評(píng)估網(wǎng)絡(luò)的狀態(tài)以執(zhí)行合適的拓?fù)渚S護(hù)策略，下面對(duì)具體的策略進(jìn)行描述。

sink節(jié)點(diǎn)對(duì)當(dāng)前網(wǎng)絡(luò)進(jìn)行評(píng)估，如果發(fā)現(xiàn)時(shí)間T內(nèi)收到了多個(gè)節(jié)點(diǎn)的重建請(qǐng)求，則證明網(wǎng)絡(luò)已經(jīng)并非最優(yōu)，需要立即重啟全局拓?fù)湫迯?fù)，并對(duì)當(dāng)前時(shí)間進(jìn)行更新；如果請(qǐng)求數(shù)較少，sink節(jié)點(diǎn)會(huì)在全局拓?fù)渲姓业骄S護(hù)節(jié)點(diǎn)u，然后從u的FList中依次選擇灰色且性能最優(yōu)的節(jié)點(diǎn)加入列表ReplaceID，直到完全覆蓋被替換節(jié)點(diǎn)u的FList中的所有灰色節(jié)點(diǎn)，如果局部拓?fù)湫迯?fù)不能得到連通的拓?fù)?，那么sink節(jié)點(diǎn)會(huì)重啟全局拓?fù)湫迯?fù)以保證網(wǎng)絡(luò)的連通。

隨 后 ，sink節(jié)點(diǎn)將decision message(flag,time,ReplaceID)沿著虛擬骨干對(duì)全網(wǎng)進(jìn)行發(fā)送，其中，flag表示拓?fù)湫迯?fù)策略，time表示需要等待的時(shí)延，如果是局部修復(fù)策略，ReplaceID表示需要成為活躍節(jié)點(diǎn)的ID集合，否則該集合為空?；钴S節(jié)點(diǎn)將收到的消息向普通節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，節(jié)點(diǎn)收到消息后檢查是否需要成為活躍節(jié)點(diǎn)。

5 理論分析

定理1如果初始網(wǎng)絡(luò)是連通的，那么通過(guò)拓?fù)錁?gòu)建后形成的支配集也是連通的。

證明算法形成的支配集由黑色節(jié)點(diǎn)組成。由于節(jié)點(diǎn)共存在4種顏色，初始時(shí)所有節(jié)點(diǎn)都是白色，節(jié)點(diǎn)一旦廣播competition消息就會(huì)變成紅色，然后根據(jù)是否收到滿足First等于自己ID的消息來(lái)決定成為黑色或灰色節(jié)點(diǎn)，也就是說(shuō)算法結(jié)束后只可能存在白色、黑色、灰色節(jié)點(diǎn)。假如還存在白色節(jié)點(diǎn)，那就說(shuō)明該節(jié)點(diǎn)沒(méi)有收到過(guò)其他節(jié)點(diǎn)廣播的competition消息，這與定理假設(shè)初始網(wǎng)絡(luò)是連通的相矛盾，得證。

定理2拓?fù)錁?gòu)建算法中每個(gè)節(jié)點(diǎn)至多只需要發(fā)送一次消息，而時(shí)間復(fù)雜度為O(n)。

證明當(dāng)前節(jié)點(diǎn)收到上層節(jié)點(diǎn)發(fā)送的消息后，會(huì)在超時(shí)結(jié)束后廣播一次消息，并根據(jù)收到消息的First屬性決定變?yōu)楹谏蚧疑４送?，?jié)點(diǎn)的操作不需要排序，均能在常數(shù)時(shí)間內(nèi)完成，因此算法的時(shí)間復(fù)雜度為O(n)。

定理3拓?fù)渚S護(hù)算法至多只需要發(fā)送2n的消息，算法的時(shí)間復(fù)雜度為O(nlgn)。

證明節(jié)點(diǎn)需要對(duì)鄰居節(jié)點(diǎn)計(jì)算權(quán)值w2并排序，這個(gè)過(guò)程需要O(ΔlgΔ)的時(shí)間，Δ為最大鄰居節(jié)點(diǎn)數(shù)。消息沿著虛擬骨干向基站轉(zhuǎn)發(fā)，最壞的情況下，消息被轉(zhuǎn)發(fā)n次到達(dá)sink節(jié)點(diǎn)?；跁r(shí)間機(jī)制的拓?fù)渚S護(hù)策略每隔時(shí)間T進(jìn)行重構(gòu)，不需要其他額外操作；基于能量和故障機(jī)制的拓?fù)渚S護(hù)策略，采用局部拓?fù)湫迯?fù)時(shí)，至多需要O(Δ)的時(shí)間來(lái)判斷是否可以生成替代節(jié)點(diǎn)集ReplaceID，而采用全局拓?fù)渚S護(hù)時(shí)需要O(1)的時(shí)間決定。sink節(jié)點(diǎn)根據(jù)當(dāng)前網(wǎng)絡(luò)狀況將執(zhí)行的策略和時(shí)延封裝在decision消息并沿著拓?fù)浞聪蜣D(zhuǎn)發(fā)至多n次，因此拓?fù)渚S護(hù)發(fā)送的消息最多不會(huì)超過(guò)2n，而算法的時(shí)間復(fù)雜度在最壞情況下為O(n lg n)。

6 仿真實(shí)驗(yàn)及分析

6.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

仿真實(shí)驗(yàn)選擇性能較好且同時(shí)包含拓?fù)錁?gòu)建和拓?fù)渚S護(hù)過(guò)程的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ˋ3M作為比較對(duì)象，實(shí)驗(yàn)采用基于網(wǎng)絡(luò)事件驅(qū)動(dòng)的軟件Atarraya[15]進(jìn)行評(píng)估，仿真開始時(shí)，振動(dòng)能源的能量采集速率λ=0，隨著時(shí)間的增加，λ將以0.001 mJ/unit的速率遞增，算法采用的能耗模型與參考文獻(xiàn)[12]相同，其他參數(shù)見(jiàn)表1。

表1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

6.2 實(shí)驗(yàn)結(jié)果

首先通過(guò)一組節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖闡述仿真實(shí)驗(yàn)的運(yùn)行過(guò)程。實(shí)驗(yàn)初始時(shí)，將150個(gè)通信半徑和能量各不相同的傳感器節(jié)點(diǎn)部署到網(wǎng)絡(luò)中，如圖2(a)所示，此時(shí)所有節(jié)點(diǎn)均為白色。當(dāng)算法運(yùn)行結(jié)束后，可以得到如圖2(b)所示的網(wǎng)絡(luò)拓?fù)洌渲?，黑色表示活躍節(jié)點(diǎn)，灰色表示處于休眠的節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果取自隨機(jī)生成的20個(gè)拓?fù)鋵?shí)例分別運(yùn)行10次后的平均值，從通信開銷和網(wǎng)絡(luò)生命時(shí)間對(duì)算法進(jìn)行評(píng)估。

實(shí)驗(yàn)1主要對(duì)拓?fù)錁?gòu)建算法的通信開銷進(jìn)行評(píng)估，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100時(shí)，觀察發(fā)送和接收的消息數(shù)隨著最大通信半徑變化而發(fā)生的改變。如圖3所示，HELM不管是需要發(fā)送還是需要接收的消息數(shù)都要比A3M更少，特別是當(dāng)節(jié)點(diǎn)的最大通信半徑較大(40 m)時(shí)，HELM需要接收的消息數(shù)為3 212.3條，而A3M需要接收大約7 942.5條消息，相當(dāng)于HELM節(jié)省了59.6%的通信開銷，這說(shuō)明HELM的擴(kuò)展性較好。

實(shí)驗(yàn)2將節(jié)點(diǎn)的最大通信半徑固定為30 m，通過(guò)改變節(jié)點(diǎn)的數(shù)量來(lái)觀察算法的通信開銷。如圖4所示，隨著節(jié)點(diǎn)數(shù)量的增加，需要發(fā)送和接收的消息數(shù)都在不斷增加。HELM需要發(fā)送的消息數(shù)量等于節(jié)點(diǎn)的數(shù)量，而A3M需要發(fā)送的消息數(shù)量為300～650條。相比之下，兩個(gè)算法需要接收的消息數(shù)量更多，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200個(gè)時(shí)，HELM、A3M分別需要接收9 310.5條、22 475.8條消息，從圖4中曲線的變化趨勢(shì)預(yù)測(cè)，當(dāng)節(jié)點(diǎn)數(shù)量更密集時(shí)，這一情況會(huì)更加明顯。

實(shí)驗(yàn)3對(duì)拓?fù)渚S護(hù)的性能進(jìn)行評(píng)估，將最大通信半徑為20 m的100個(gè)節(jié)點(diǎn)進(jìn)行部署，節(jié)點(diǎn)每隔10個(gè)單元時(shí)間向sink節(jié)點(diǎn)發(fā)送數(shù)據(jù),拓?fù)渚S護(hù)中的時(shí)間、能量、故障閾值見(jiàn)表1中的T1、T2、T3，這里暫不考慮數(shù)據(jù)融合和能量采集的影響，觀察通信覆蓋率隨時(shí)間的變化情況。圖5顯示了4種拓?fù)渚S護(hù)策略的運(yùn)行情況，HELM和A3M兩種拓?fù)渚S護(hù)策略與靜態(tài)和動(dòng)態(tài)拓?fù)渚S護(hù)相比都將延長(zhǎng)網(wǎng)絡(luò)的運(yùn)行時(shí)間，特別是HELM，直到時(shí)間點(diǎn)20 988.2時(shí)開始出現(xiàn)第一個(gè)節(jié)點(diǎn)的死亡而導(dǎo)致通信覆蓋率下降，這一現(xiàn)象在A3M中發(fā)生在時(shí)間點(diǎn)17 558.1，此時(shí)HELM提高了19.5%的網(wǎng)絡(luò)運(yùn)行時(shí)間，這是因?yàn)镠ELM的拓?fù)渚S護(hù)策略只有在不得已的情況下才對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu)，否則對(duì)當(dāng)前拓?fù)鋱?zhí)行局部修復(fù)以減少網(wǎng)絡(luò)能耗。

實(shí)驗(yàn)4在實(shí)驗(yàn)3的基礎(chǔ)上對(duì)HELM中基于時(shí)間機(jī)制的維護(hù)策略進(jìn)行評(píng)估，觀察時(shí)間輪換的策略對(duì)通信覆蓋率產(chǎn)生的影響。從圖6中發(fā)現(xiàn)，考慮時(shí)間因素能夠得到更好的通信覆蓋率。當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)死亡時(shí)，不考慮時(shí)間輪換的策略相比考慮時(shí)間輪換的策略提前了2 158.2個(gè)單位時(shí)間，隨著時(shí)間的不斷增加，兩個(gè)算法的通信覆蓋率差距在不斷變大，這是因?yàn)榛跁r(shí)間輪換的策略使得節(jié)點(diǎn)之間的能量消耗更加平衡，而不考慮時(shí)間輪換的策略可能由于某些關(guān)鍵節(jié)點(diǎn)的死亡而使得網(wǎng)絡(luò)性能快速下降。

實(shí)驗(yàn)5在實(shí)驗(yàn)3的基礎(chǔ)上對(duì)HELM中基于故障機(jī)制的拓?fù)渚S護(hù)策略進(jìn)行評(píng)估，將節(jié)點(diǎn)的故障率分別設(shè)為1%和3%，觀察通信覆蓋率的變化情況。如圖7所示，隨著節(jié)點(diǎn)故障率的增加，在相同生命時(shí)間下兩種拓?fù)渚S護(hù)策略的通信覆蓋率都有所下降，其中，HELM拓?fù)渚S護(hù)策略的第一個(gè)死亡節(jié)點(diǎn)的時(shí)間提前了1 836.5個(gè)時(shí)間單元。此外，由圖可知，A3M拓?fù)渚S護(hù)策略下降得更快，這是因?yàn)楫?dāng)節(jié)點(diǎn)失效時(shí)，A3M不但每次都需要進(jìn)行拓?fù)渲貥?gòu)，而且在重構(gòu)過(guò)程中A3M需要發(fā)送和接收的消息數(shù)量比HELM更多，這就造成A3M的能耗更大，嚴(yán)重影響了網(wǎng)絡(luò)的生命時(shí)間。

實(shí)驗(yàn)6對(duì)能量補(bǔ)給模型的性能進(jìn)行評(píng)估，觀察是否考慮能量采集對(duì)網(wǎng)絡(luò)的生命時(shí)間產(chǎn)生的影響。如圖8所示，隨著時(shí)間的增加剩余存活節(jié)點(diǎn)數(shù)量逐漸下降，但是考慮能量補(bǔ)給的網(wǎng)絡(luò)的存活節(jié)點(diǎn)數(shù)量始終要大于不考慮能量補(bǔ)給的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量，這是因?yàn)椴糠止?jié)點(diǎn)可以通過(guò)采集而有效補(bǔ)給能量。帶有能量補(bǔ)給的網(wǎng)絡(luò)出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的時(shí)間為23 568.5，相比無(wú)能量補(bǔ)給模型，該模型相當(dāng)于延長(zhǎng)了7.2%的網(wǎng)絡(luò)生命時(shí)間。

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

隨著傳感器節(jié)點(diǎn)可以通過(guò)能量采集進(jìn)行供能，當(dāng)前拓?fù)淇刂扑惴ㄐ枰紤]節(jié)點(diǎn)能量補(bǔ)給的特性以延長(zhǎng)網(wǎng)絡(luò)的生命時(shí)間，本文在通信半徑和能量存在異構(gòu)的網(wǎng)絡(luò)中提出了一種結(jié)合拓?fù)錁?gòu)建和拓?fù)渚S護(hù)過(guò)程的拓?fù)淇刂扑惴?。算法首先以較少的通信開銷構(gòu)建連通支配集，而當(dāng)拓?fù)洳辉俑咝r(shí)，及時(shí)運(yùn)行拓?fù)渚S護(hù)算法，由sink節(jié)點(diǎn)決定采用局部或全局拓?fù)湫迯?fù)策略以節(jié)約網(wǎng)絡(luò)能量。仿真結(jié)果顯示，拓?fù)錁?gòu)建算法相比A3M可以節(jié)省超過(guò)59%的通信開銷，而拓?fù)渚S護(hù)策略更是將網(wǎng)絡(luò)的運(yùn)行時(shí)間提高了將近20%。此外，與無(wú)能量補(bǔ)給的網(wǎng)絡(luò)模型相比，帶有能量補(bǔ)給的網(wǎng)絡(luò)模型最終使網(wǎng)絡(luò)的生命時(shí)間延長(zhǎng)了7.2%。HELM可以應(yīng)用在環(huán)境比較惡劣的地區(qū)，當(dāng)節(jié)點(diǎn)失效時(shí)可以通過(guò)較小的能耗代價(jià)保障網(wǎng)絡(luò)拓?fù)涞馁|(zhì)量。

1 錢志鴻,王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述.電子與信息學(xué)報(bào),2013,35(1)：215～227 Qian Z H,Wang Y J.Internet of things-oriented wireless sensor networks review. Journal of Electronics & Information Technology,2013,35(1):215～227

2 Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks. IEEE Communications Surveys and Tutorials,2013,15(1):121～144

3 Labrador M A,Wightman P M.Topology Control in Wireless Sensor Network.Berlin:Springer,2009

4 He J,Ji S L,Fan P Z,et al.Constructing a load-balanced virtual backbone in wireless sensor networks.Proceedings of International Conference on Computing Networking and Communications,Maui,Hawaii,USA,2012:147～163

5 Wightman P M,Fabregas A,Labrador M A.An optimal solution to the MCDS problem for topology construction in wireless sensor networks.Proceedings of IEEE Latin-American Conference on Communications,Bogota,Columbia,2010:1～6

6 洪榛,俞立,張貴軍等.基于最小連通支配集的無(wú)線傳感網(wǎng)拓?fù)錁?gòu)建研究.電子與信息學(xué)報(bào),2012,34(8)：2000～2006 Hong Z,Yu L,Zhang G J,et al.Topology construction based on minimum connected dominating set for wireless sensor networks.Journal of Electronics&Information Technology,2012,34(8):2000～2006

7 奎曉燕,杜華坤,梁俊斌.無(wú)線傳感器網(wǎng)絡(luò)中一種能量均衡的基于連通支配集的數(shù)據(jù)收集算法.電子學(xué)報(bào),2013,41(8)：1521～1528 Kui X Y,Du H K,Liang J B.An energy-balanced connected dominating sets for data gathering in wireless sensor networks.Acta Electronica Sinica,2013,41(8):1521～1528

8 Wightman P M,Labrador M A.Topology maintenance:extending the lifetime of wireless sensor networks.IEEE Latin America Transactions,2010,8(4):1～6

9 沈中,常義林,崔燦等.一種可自維護(hù)無(wú)線網(wǎng)絡(luò)拓?fù)渥钚∧芰刻匦缘姆植际酵負(fù)淇刂扑惴?計(jì)算機(jī)學(xué)報(bào),2007,30(4)：569～578 Shen Z,Chang Y L,Cui C,et al.A distributed topology control algorithm for self-maintenance of the minimum-energy property of a wireless networks topology.Chinese Journal of Computers,2007,30(4):569～578

10 Liao Y,Qi H,Li W.Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks.IEEE Sensors Journal,2013,13(5):1498～1506

11 康一梅,李志軍,胡江等.一種低能耗層次型無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?自動(dòng)化學(xué)報(bào),2010,36(4)：543～549 Kang Y M,Li Z J,Hu J,et al.A Low-power hierarchical wireless sensor network topology control algorithm.Acta Automatica Sinica,2010,36(4):543～549

12 馬晨明,王萬(wàn)良,洪榛.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中基于CDS樹的拓?fù)淇刂品椒?傳感技術(shù)學(xué)報(bào),2014,27(6)：814～820 Ma C M,Wang W L,Hong Z.A topology control method based on CDS tree in heterogeneous wireless sensor network.Chinese Journal of Sensors and Actuators,2014,27(6):814～820

13 Sudevalayam S,Kulkarni P.Energy harvesting sensor nodes:survey and implications.Communications Surveys&Tutorials,2011,13(3):443～461

14 姚玉坤,王冠,任智等.能耗均衡的自供能無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法.傳感技術(shù)學(xué)報(bào),2013,10(26)：1420～1425 Yao Y K,Wang G,Ren Z,et al.Energy balanced clustering algorithm for self-energized wireless sensor networks.Chinese Journal of Sensors and Actuators,2013,10(26):1420～1425

15 Wightman P M,Labrador M A.Atarraya:a simulation tool to teach and research topology control algorithms for wireless sensor networks.Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009

猜你喜歡

網(wǎng)絡(luò)拓?fù)?/a>消息半徑

基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法

網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46

一張圖看5G消息

通信產(chǎn)業(yè)報(bào)(2020年43期)2020-01-15 06:38:43

連續(xù)展成磨削小半徑齒頂圓角的多刀逼近法

制造技術(shù)與機(jī)床(2019年6期)2019-06-25 10:17:18

電子制作(2018年23期)2018-12-26 01:01:16

勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D

汽車維修技師(2017年10期)2017-03-17 02:25:01

一些圖的無(wú)符號(hào)拉普拉斯譜半徑

華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2017年1期)2017-02-27 13:41:05

電測(cè)與儀表(2016年5期)2016-04-22 01:13:46

熱采水平井加熱半徑計(jì)算新模型

中國(guó)海上油氣(2015年3期)2015-07-01 16:32:08

消息

中國(guó)衛(wèi)生(2014年12期)2014-11-12 13:12:26

消息

中國(guó)衛(wèi)生(2014年8期)2014-11-12 13:00:50