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

2015-09-29 04:49:38馬晨明王萬良姚信威

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

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

馬晨明 ，王萬良 ，洪 榛 ，姚信威

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

1 引言

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

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

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

2.2 能量補(bǔ)給模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 理論分析

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

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

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

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

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

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

6 仿真實驗及分析

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

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

表1 仿真實驗參數(shù)設(shè)置

6.2 實驗結(jié)果

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

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

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

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

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

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

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

7 結(jié)束語

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

1 錢志鴻,王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述.電子與信息學(xué)報,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ǎng)拓?fù)錁?gòu)建研究.電子與信息學(xué)報,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ǎng)絡(luò)中一種能量均衡的基于連通支配集的數(shù)據(jù)收集算法.電子學(xué)報,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ǎng)絡(luò)拓?fù)渥钚∧芰刻匦缘姆植际酵負(fù)淇刂扑惴?計算機(jī)學(xué)報,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ǎng)絡(luò)拓?fù)淇刂扑惴?自動化學(xué)報,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 馬晨明,王萬良,洪榛.異構(gòu)無線傳感器網(wǎng)絡(luò)中基于CDS樹的拓?fù)淇刂品椒?傳感技術(shù)學(xué)報,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ǎng)絡(luò)分簇路由算法.傳感技術(shù)學(xué)報,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è)報(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

一些圖的無符號拉普拉斯譜半徑

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

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

熱采水平井加熱半徑計算新模型

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

消息

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

消息

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