WRSN中一種聚類分簇多跳能量補(bǔ)充策略

張媛媛,馮 勇,付曉東

(昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室,昆明 650500) E-mail:zhyuanAngel@163.com

1 引 言

無線可充電傳感器網(wǎng)絡(luò)(Wireless Rechargeable Sensor Networks,WRSN)是部署在監(jiān)測(cè)區(qū)域內(nèi)的若干個(gè)傳感器節(jié)點(diǎn)的可充電式網(wǎng)絡(luò).節(jié)點(diǎn)可通過充電獲取能量,并將收集到的數(shù)據(jù)以無線的形式發(fā)送到基站,再由基站將數(shù)據(jù)上傳至互聯(lián)網(wǎng).隨著可快速充電網(wǎng)絡(luò)的飛速發(fā)展,WRSN技術(shù)成為了眾多充電研究領(lǐng)域的焦點(diǎn).傳感器節(jié)點(diǎn)使用電池供電,而電池能量是有限的,這會(huì)導(dǎo)致在無線通信過程中會(huì)消耗大量傳感器節(jié)點(diǎn)的能量,因此解決能耗問題成為了該領(lǐng)域研究的關(guān)鍵,于是涌現(xiàn)出各種節(jié)能的方法以及充電的方法[1],然而節(jié)能的方法可能會(huì)增加網(wǎng)絡(luò)延遲,只能有限延長(zhǎng)網(wǎng)絡(luò)壽命,緩解耗能的現(xiàn)狀,并不能從根本上解決問題.在充電領(lǐng)域的研究中通常采用的是單跳能量傳輸[2],但這種方式在網(wǎng)絡(luò)節(jié)點(diǎn)較多的情況下可能會(huì)增加充電成本降低充電效率,可見其可擴(kuò)展性和效率是十分有限的.為了解決這一問題,本文采用多跳能量傳輸方式.除此之外,現(xiàn)有工作中采用多小車充電技術(shù)[3].MC是一個(gè)具有自主移動(dòng)能力和計(jì)算、通信能力的充電裝置,該充電裝置在本文中統(tǒng)稱為充電小車,它們通過相互配合實(shí)現(xiàn)對(duì)缺電節(jié)點(diǎn)的能量補(bǔ)給,而研究多小車充電技術(shù)時(shí)需要盡可能地達(dá)到讓MC的數(shù)量呈現(xiàn)最低值,或者提高M(jìn)C的充電效率,但是實(shí)際環(huán)境中MC是相對(duì)代價(jià)很高的一種設(shè)備,為了更有效的降低充電代價(jià),本文將最小化充電裝置個(gè)數(shù)即采用單小車充電來簡(jiǎn)化充電規(guī)劃.

本文中還涉及到的另一先進(jìn)技術(shù)是聚類方法[4],其引申出來的分析往往用于從大范圍的數(shù)據(jù)庫中快速、準(zhǔn)確地尋找數(shù)據(jù).該技術(shù)在社會(huì)各行業(yè)領(lǐng)域都起到很重要的作用,其中Choi J等人[5]提出將傳感器節(jié)點(diǎn)分組成簇是在無線傳感器網(wǎng)絡(luò)(WSN)中減少重復(fù)信息傳輸?shù)挠行Х椒?并且能準(zhǔn)確的預(yù)估能量的消耗.本文將傳感器節(jié)點(diǎn)抽象成每一個(gè)數(shù)據(jù)點(diǎn),利用聚類思想為MC尋找合適的簇點(diǎn).綜上所述,為了解決現(xiàn)有能量補(bǔ)充方案的缺陷,本文創(chuàng)新的提出一種聚類分簇的多跳能量補(bǔ)充策略.

本文組織如下:第二節(jié)介紹了相關(guān)工作.第三節(jié)用網(wǎng)絡(luò)模型與問題陳述來描述網(wǎng)絡(luò)的能量問題.第四節(jié)詳細(xì)介紹了該能量補(bǔ)充方案的工作過程.第五部分通過仿真實(shí)驗(yàn)的結(jié)果和分析對(duì)該算法做出了性能評(píng)價(jià).最后在第六節(jié)中對(duì)全文進(jìn)行總結(jié).

2 相關(guān)工作

在這個(gè)部分,我們將回顧現(xiàn)有的使用無線能量補(bǔ)充技術(shù)延長(zhǎng)網(wǎng)絡(luò)壽命的工作,其中分為單跳能量傳輸、多跳能量傳輸以及多小車充電技術(shù)這三個(gè)方面.

在單跳能量傳輸方面,文獻(xiàn)[6]考慮單跳能量傳輸,M.Ma等人設(shè)計(jì)出一種貪婪算法,找到一個(gè)充電序列,能夠使用移動(dòng)充電裝置最大限度的提高網(wǎng)絡(luò)的生命周期,但該文獻(xiàn)提出來的優(yōu)化技術(shù)和充電算法是基于單節(jié)點(diǎn)的充電模型,具有非常有限的可擴(kuò)展性.文獻(xiàn)[7]提出賦予移動(dòng)充電裝置更廣的用途,不僅可以補(bǔ)充聚合及轉(zhuǎn)發(fā)節(jié)點(diǎn)(AFN),還能夠在選定的AFN節(jié)點(diǎn)處采集數(shù)據(jù).該文獻(xiàn)綜合考慮數(shù)據(jù)傳輸方式、無線電功率以及流量選擇方式這三種因素,提出一種啟發(fā)式算法來解決為節(jié)點(diǎn)補(bǔ)充能量的優(yōu)化問題.為了提高網(wǎng)絡(luò)生命周期,文獻(xiàn)[8]提出了一種新的路由選擇指標(biāo),能夠形成具有最佳充電性能的路由.在文獻(xiàn)[9]中,Peng等人提出了一個(gè)由固定的傳感器節(jié)點(diǎn),MC和基站(BS)組成的三層架構(gòu)來監(jiān)視MC和傳感器的能量狀態(tài).傳感器周期性地發(fā)送有關(guān)其電池狀態(tài)的信息,并由基站計(jì)算充電序列并將信息發(fā)送給MC.

多跳能量傳輸[10]更適合網(wǎng)絡(luò)節(jié)點(diǎn)較多的情況,該方式已在眾多研究中被證實(shí)可使得充電效率有所提升.現(xiàn)有工作通常采用諧振中繼器實(shí)現(xiàn)多跳能量傳輸,其涉及的磁共振無線能量傳輸耦合是一種很前沿的傳感器能量補(bǔ)充技術(shù)[11].該技術(shù)在每個(gè)傳感器上的線圈周圍產(chǎn)生一個(gè)能夠傳輸電力的磁場(chǎng),當(dāng)充電裝置對(duì)其進(jìn)行充電時(shí),會(huì)將自身的發(fā)射線圈與傳感器接收線圈調(diào)成同一個(gè)振動(dòng)頻率,這時(shí)能量就會(huì)以電流形式傳輸出去,方便實(shí)現(xiàn)一對(duì)多充電,因此采用諧振中繼器可以有效提高充電效率.文獻(xiàn)[12]中Xie等人提出具有擴(kuò)展性的網(wǎng)絡(luò)部署,將整個(gè)網(wǎng)絡(luò)按邊長(zhǎng)在MC充電范圍內(nèi)的正六邊形進(jìn)行劃分,分割后以正六邊形的中心點(diǎn)作為錨點(diǎn),采用離散化和線性化技術(shù)對(duì)整個(gè)網(wǎng)絡(luò)規(guī)劃哈密頓回路,讓MC周期性的沿規(guī)定的路線進(jìn)行能量傳輸.該文獻(xiàn)雖然開發(fā)了一個(gè)可證明的近似達(dá)到高期望精度水平的最優(yōu)解,但卻不能很好的適應(yīng)節(jié)點(diǎn)能耗的動(dòng)態(tài)性,屬于當(dāng)前能量補(bǔ)充技術(shù)中的離線充電方式.文獻(xiàn)[13]中Xiang等人提出了距離最近優(yōu)先充電方法作為充電策略,對(duì)所提出的移動(dòng)充電策略進(jìn)行了對(duì)比實(shí)驗(yàn)分析,除此之外還考慮一種多跳能量流問題,并針對(duì)問題制定研究方案,為了優(yōu)化該能量流問題設(shè)計(jì)出合適的算法.

對(duì)于多小車充電的研究,文獻(xiàn)[14]提出一種新型框架,采用相鄰交叉耦合諧振中繼器為多跳無線充電問題提供方案.為了達(dá)到能量消耗與節(jié)電延遲之間的平衡,Wang C等人提出了一種混合數(shù)據(jù)收集策略,收集時(shí)間敏感數(shù)據(jù)和時(shí)間不敏感數(shù)據(jù).為了最大限度的減少充電成本,該文獻(xiàn)提出了兩步近似算法,首先確定一組具有代表性的傳感器位置記作錨點(diǎn),并采用多小車充電方案,利用近似算法的旅行商問題為多小車分配一個(gè)完整的最優(yōu)路徑.為了進(jìn)一步降低系統(tǒng)成本,用后優(yōu)化算法迭代地添加移動(dòng)充電小車的位置來改善充電結(jié)果.文獻(xiàn)[15]中考慮了充電過程中的節(jié)點(diǎn)能量需求和節(jié)點(diǎn)能耗問題,提出一種多跳無線充電優(yōu)化算法.首先利用Dijkstra算法[16]找到最短路徑樹,然后采用混合整數(shù)線性算法(MILP)來尋找充電小車的最小數(shù)量.分析表明充電小車的最小數(shù)量取決于充電樹的最大高度以及充電小車的電量.但是該文獻(xiàn)解決方案沒有考慮到節(jié)點(diǎn)的充電時(shí)間和總能量,并且采用多小車充電會(huì)導(dǎo)致充電成本的增加.

本文就上述問題提出了無線可充電傳感器中一種聚類分簇的多跳能量補(bǔ)充策略.本策略采用了聚類算法分配簇點(diǎn),提出計(jì)算節(jié)點(diǎn)密度電量比動(dòng)態(tài)分配充電優(yōu)先級(jí),并通過對(duì)比實(shí)驗(yàn)評(píng)估該策略的網(wǎng)絡(luò)性能.

3 網(wǎng)絡(luò)模型與問題陳述

3.1 基礎(chǔ)網(wǎng)絡(luò)模型

本文構(gòu)建的基礎(chǔ)網(wǎng)絡(luò)由三部分組成.分別是基站(Base Station,BS)、網(wǎng)絡(luò)傳感器節(jié)點(diǎn)(Sensor)以及移動(dòng)充電裝置(Mobile Charger,MC),具體網(wǎng)絡(luò)模型如圖1所示.在本文中,假設(shè)BS有足夠的能量和通信能力使其能夠直接向MC發(fā)送信息.BS從節(jié)點(diǎn)接收充電請(qǐng)求消息,并直接將收到的消息轉(zhuǎn)發(fā)給MC.MC具有從服務(wù)池動(dòng)態(tài)獲取各個(gè)傳感器的充電信息和位置信息的計(jì)算能力,并根據(jù)充電優(yōu)先級(jí)找到下一個(gè)目標(biāo)節(jié)點(diǎn).具體的參數(shù)符號(hào)如表1所示.

圖1 網(wǎng)絡(luò)模型Fig.1 Network model

3.2 問題公式

在本節(jié)中,為了降低充電成本,提高充電效率,首先給出能量消耗公式,然后給出能量傳輸?shù)男使?

3.2.1 能量消耗公式

無線通信模型中提出一個(gè)距離閾值d0,其值與實(shí)際環(huán)境相關(guān).當(dāng)節(jié)點(diǎn)不位于充電服務(wù)池時(shí),假設(shè)發(fā)送節(jié)點(diǎn)a與接收節(jié)點(diǎn)b的距離的距離不小于閾值時(shí),即dab≥d0時(shí),文獻(xiàn)[17]中證明了收發(fā)數(shù)據(jù)消耗的能量與距離之間的四次冪關(guān)系.因此基于發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離,可以計(jì)算發(fā)送數(shù)據(jù)所消耗的能量值.舉個(gè)例子,節(jié)點(diǎn)a′向距離d以外的另一節(jié)點(diǎn)b′發(fā)送k個(gè)字節(jié)的數(shù)據(jù),該過程消耗的能量Ec可由公式(1)計(jì)算得到.

Ec(k,d)=Eelec(k)+Eamp(k,d)

=kEelec+kε-mpd4

(1)

其中Eelec表示節(jié)點(diǎn)發(fā)送與接收數(shù)據(jù)所消耗的能量,Eamp表示放大器消耗的能量,其大小取決于可接受的位錯(cuò)誤率ε-mp以及發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離.

表1 參數(shù)符號(hào)表
Table 1 Parameter symbol

參數(shù)符號(hào)參數(shù)意義N傳感器個(gè)數(shù)Rs傳感器通信范圍S充電服務(wù)池Es節(jié)點(diǎn)的剩余電量Ec發(fā)送/接收數(shù)據(jù)包的能量消耗Et能量閾值VmMC的移動(dòng)速度RrMC的充電范圍

3.2.2 能量傳輸效率

1)多跳能量傳輸:文獻(xiàn)[18]提出一個(gè)節(jié)點(diǎn)既可以傳輸能量也可以接收能量,并且相鄰節(jié)點(diǎn)之間能夠交換能量.對(duì)此,有文獻(xiàn)[5]提出當(dāng)能量從MC通過多跳傳輸至其他節(jié)點(diǎn)時(shí),在整個(gè)充電路徑中會(huì)存在能量丟失的情況.我們給出一個(gè)中心節(jié)點(diǎn)a,一個(gè)中間節(jié)點(diǎn)b和一個(gè)最終節(jié)點(diǎn)c,那么總的能量分配Etotal是:

圖2 簇點(diǎn)個(gè)數(shù)Fig.2 Number of clusters

Etotal=Echarge+Ea+Eb+Ec

(2)

Echarge=2λcharge|Ab|2

(3)

其中Ea,Eb,Ec表示節(jié)點(diǎn)a,b,c的能量消耗,可由公式(1)求得.|Ab|表示當(dāng)給節(jié)點(diǎn)b充電時(shí),節(jié)點(diǎn)b的接收功率.λcharge是充電過程中能量消耗的速率.我們假設(shè)傳輸?shù)街虚g節(jié)點(diǎn)的所有能量將被用于從中間節(jié)點(diǎn)到最終節(jié)點(diǎn)的能量傳輸.也就是說,電池在充放電過程中沒有能量損失,從而得到充電效率為:

λcharge|Ab|2=λb|Ab|2+2λc|Ac|2

(4)

(5)

2)單跳能量傳輸:基于上述表達(dá)式,我們給出節(jié)點(diǎn)a的單跳能量傳輸效率公式,為了提高充電效率和網(wǎng)絡(luò)生存周期,我們需要盡可能地使ηcharge變大:

Echarge=λcharge|Aa|2

(6)

λcharge|Aa|2=λa|Aa|2

(7)

(8)

4 能量補(bǔ)充算法

本節(jié)將詳細(xì)描述在無線可充電傳感器網(wǎng)絡(luò)中一種聚類分簇多跳能量補(bǔ)充算法.

4.1 簇點(diǎn)初始化算法

4.1.1 簇點(diǎn)個(gè)數(shù)的確定

圖3 孤立點(diǎn)個(gè)數(shù)Fig.3 Number of isolated nodes

實(shí)際環(huán)境中的錨節(jié)點(diǎn)即簇點(diǎn),在下文中統(tǒng)稱簇點(diǎn).假設(shè)簇點(diǎn)的大小是固定的,文獻(xiàn)[19]給出了覆蓋區(qū)域Ω所需最小節(jié)點(diǎn)數(shù)量n的公式,其半徑為傳感器通信半徑Rs:

(9)

圖4 簇點(diǎn)初始化Fig.4 Cluster point initialization

定義1.?(x1,y1)∈Ω,定義它的一個(gè)鄰域?yàn)?

(10)

(11)

(12)

(13)

由上述公式可得不同節(jié)點(diǎn)數(shù)相對(duì)應(yīng)的簇點(diǎn)個(gè)數(shù)如圖2所示.

4.1.2 簇點(diǎn)初始化過程

對(duì)于簇點(diǎn)的初始位置確定,本文在研究初始位置的最初階段時(shí)采用隨機(jī)初始化方式確定固定個(gè)數(shù)的簇點(diǎn)的初始位置,即RI-CB MWRN算法(Random Initialization-Clustering Based Multi-hop Wireless Rechargeable Network).在初始化簇點(diǎn)位置之后,采用聚類的簇點(diǎn)生成算法以及相應(yīng)的優(yōu)先級(jí)算法來完成整個(gè)網(wǎng)絡(luò)的充電過程.具體的算法過程將后面一節(jié)中詳細(xì)介紹.而后對(duì)于簇點(diǎn)位置的隨機(jī)初始化這一部分進(jìn)行了進(jìn)一步的更改,我們提出通過節(jié)點(diǎn)的連通度來實(shí)現(xiàn).算法具體過程為:首先定義通信范圍內(nèi)的節(jié)點(diǎn)互為鄰居節(jié)點(diǎn),那么擁有鄰居節(jié)點(diǎn)的個(gè)數(shù)即為節(jié)點(diǎn)的連通度.其次把所有節(jié)點(diǎn)的連通度放在集合δ中,將δ中的最大值記作δmax.當(dāng)|δmax|≤k時(shí),找到距MC最近的點(diǎn)i放入簇點(diǎn)集合Α中,然后對(duì)每一個(gè)δ中的節(jié)點(diǎn)j到i的距離記作dij,進(jìn)行冒泡排序后優(yōu)先選擇dij最大的節(jié)點(diǎn)放入Α中,否則取下一個(gè)δmax,直到Α中簇點(diǎn)個(gè)數(shù)為k.通過比較隨機(jī)分布和節(jié)點(diǎn)連通度分布得到的聚類初始位置,可以看出最終聚類后產(chǎn)生的孤立點(diǎn)個(gè)數(shù)明顯不同.從圖3可以看出,隨機(jī)初始化節(jié)點(diǎn)分布導(dǎo)致的孤立節(jié)點(diǎn)數(shù)量總體上大于節(jié)點(diǎn)度數(shù)初始化分布導(dǎo)致的孤立節(jié)點(diǎn)數(shù)量.當(dāng)孤立節(jié)點(diǎn)數(shù)量增加時(shí),MC的移動(dòng)距離將增加,從理論上講,充電成本會(huì)明顯增加,不利于實(shí)現(xiàn)更好的實(shí)驗(yàn)結(jié)果.在這里,如圖4所示給出了簇點(diǎn)初始化的樣例圖.

算法1.初始化簇點(diǎn)算法的偽代碼

Input:sensor nodesN,the number of clustersk,set of degreeδ,δmax

Output:set of initialize anchors Α0

1:Initialize:Α0=null

2:considerifromδmaxas a candidate anchorαi,Α0←Α0∪αi

3:while Α0≠null do

4: calculate dijofδmax

5: by Bubble sort,add dijto arrayφ

6: for(j=0;j<φ.length;j++)

7: Α0←Α0∪αj

8: if |Α0|≤k then

9:δmax=δmax-1

10: end if

11: else break

12: end for

13:end while

4.2 HNDLE-CB 算法

基于上述工作內(nèi)容,下面將詳細(xì)描述HNDLE-CB算法的實(shí)現(xiàn)步驟.首先網(wǎng)絡(luò)工作過程為:MC檢查傳感器節(jié)點(diǎn)剩余的電池能量Es.當(dāng)傳感器節(jié)點(diǎn)Es≤Et時(shí),會(huì)向BS發(fā)送充電請(qǐng)求,并放入服務(wù)池,然后將其置于休眠狀態(tài).

1)簇點(diǎn)生成算法.首先我們需要初始化一組數(shù)據(jù)點(diǎn).這里給出一個(gè)無標(biāo)記的數(shù)據(jù)集合[20]X={X(1),X(2),…,X(m)}.初始化的過程是選取節(jié)點(diǎn)度數(shù)最大的數(shù)據(jù)點(diǎn).其次我們將互為鄰居節(jié)點(diǎn)的點(diǎn)用虛線連接,節(jié)點(diǎn)擁有的線條數(shù)量即為它的度數(shù).對(duì)于每一個(gè)傳感器節(jié)點(diǎn)X(i),需要找到離它最近的簇點(diǎn)j,且X(i)必須包含在簇點(diǎn)j的充電范圍R內(nèi),這時(shí)將X(i)分配給簇點(diǎn)j,否則將重新尋找不在充電范圍R內(nèi)的X(i)距離最近的一個(gè)簇點(diǎn)j′.如果沒有滿足條件的簇點(diǎn)j′,則將不在充電范圍R內(nèi)的節(jié)點(diǎn)視作孤立點(diǎn).對(duì)于這一步,我們要做的是選擇離傳感器節(jié)點(diǎn)最近的且符合條件的簇點(diǎn)并分配給X(i).最后將簇點(diǎn)重新分配,它的新位置就是該簇點(diǎn)包含的所有點(diǎn)的平均值.其中,簇點(diǎn)j距離X(i)最近的判斷所用的是歐式空間[21]中兩點(diǎn)之間的直線距離,即平面上兩點(diǎn)A=(a1,b1)和B=(a2,b2)之間的歐式距離公式為:

(14)

具體簇點(diǎn)生成算法過程如圖5所示.

2)優(yōu)先級(jí)分配算法.在第一步找到簇點(diǎn)集合Α以后,MC接收到充電請(qǐng)求后,每隔T個(gè)時(shí)間檢查服務(wù)池內(nèi)的請(qǐng)求記錄集合,這些記錄主要包括請(qǐng)求節(jié)點(diǎn)的剩余能量Es以及節(jié)點(diǎn)的位置L.初始時(shí)將MC的狀態(tài)設(shè)為空閑,并將其位于所有Sensor的中心點(diǎn)處.當(dāng)接收節(jié)點(diǎn)的充電請(qǐng)求時(shí),MC會(huì)更新服務(wù)池,并計(jì)算服務(wù)池中節(jié)點(diǎn)的節(jié)點(diǎn)密度電量比Ψ.我們首先定義剩余能量大于閾值的節(jié)點(diǎn)i的服務(wù)池集合Si.充電序列可以表示為r=(1,2,…,i,…,k),其中簇點(diǎn)i∈Α,k=|Α|,MC需找到他們所屬的簇點(diǎn).當(dāng)服務(wù)池里節(jié)點(diǎn)數(shù)量為?時(shí),?=|Si|,MC會(huì)從?中得到每一個(gè)節(jié)點(diǎn)的Es,以及節(jié)點(diǎn)同屬同一個(gè)簇點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)為:

(15)

為了方便分析,我們提出一個(gè)計(jì)算節(jié)點(diǎn)密度電量比Ψ的能量補(bǔ)充算法.其中Ψ滿足以下公式:

(16)

MC將移動(dòng)到與Ψmin相對(duì)應(yīng)的簇點(diǎn)處充電.實(shí)際上,該HNDLE-CB算法是選擇β越大Es越小的節(jié)點(diǎn)優(yōu)先充電.

算法2.HNDLE-CB算法的偽代碼.

Input:set of initialize anchorsA0,recharge sensorsSi,sensor nodesN,coverage radiusRr,

Output:set of anchors A,recharging sequence r

1:while(！convergence)do

2: for(i=0;i

3: for(j=0;j

4: ifi∈Α0andLij

5:jbelongs toi

7: end if

8: end for

9: end for

10:end while

11: if there is node m,dmi>Rr

12: m as isolated node

14: end if

15: ?=|Si|

16:while (t≤Τ and ?!=null) do

17: for(i=0;i

19: Ψj=Es(j)/β

20:byBubble sort , array[j]←Ψj

21: end for

22: add array tor

23:end while

5 性能分析

本文構(gòu)建了無線可充電傳感器網(wǎng)絡(luò)應(yīng)用場(chǎng)景的仿真環(huán)境,選取了一塊 30m×30m 的區(qū)域,并隨機(jī)布置基站和25～200個(gè)傳感器節(jié)點(diǎn),將MC部署在所有傳感器節(jié)點(diǎn)位置的中心處,所有傳感器節(jié)點(diǎn)都具有相同的數(shù)據(jù)接受能力,并且節(jié)點(diǎn)與MC擁有相同的諧振頻率,可接受MC發(fā)送的能量.假設(shè)每一個(gè)傳感器節(jié)點(diǎn)的初始電量為10000(unit),在收發(fā)消息的能量消耗過程中,當(dāng)剩余能量達(dá)到了閾值250(unit)時(shí),這些傳感器節(jié)點(diǎn)會(huì)被放入充電服務(wù)池中,并依次向MC發(fā)送充電請(qǐng)求.MC計(jì)算服務(wù)池中節(jié)點(diǎn)的密度電量比Ψ作為充電優(yōu)先級(jí),依次給節(jié)點(diǎn)充電,這是HNDLE-CB算法的實(shí)驗(yàn)過程.詳細(xì)的仿真參數(shù)如表2所示.本文基于C#仿真平臺(tái)對(duì)HNDLE-CB算法進(jìn)行性能分析,并把Cellular MWRN[12]算法與本文4.1.2節(jié)中描述的隨機(jī)初始化簇點(diǎn)的RI-CB MWRN算法進(jìn)行性能對(duì)比.我們從錨點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)的失效率、網(wǎng)絡(luò)的生存時(shí)間以及充電成本這四個(gè)指標(biāo)來對(duì)上述三種算法進(jìn)行性能分析.

圖5 簇點(diǎn)生成算法Fig.5 Cluster point generation algorithm

表2 仿真參數(shù)
Table 2 Simulation parameters

參數(shù)名參數(shù)值監(jiān)測(cè)區(qū)域30m×30m傳感器初始電量10000(unit)節(jié)點(diǎn)個(gè)數(shù)[25,200]通信半徑20mMC覆蓋半徑[3,5] MC的移動(dòng)速度5m/s數(shù)據(jù)包大小100bytes充電速率[100,300]能量閾值250(unit)網(wǎng)絡(luò)覆蓋概率0.8

5.1 錨點(diǎn)個(gè)數(shù)

本組實(shí)驗(yàn)討論各算法分別產(chǎn)生的錨點(diǎn)個(gè)數(shù)的情形.從圖6(a)可以清楚地看到,隨著節(jié)點(diǎn)數(shù)量的增加,錨節(jié)點(diǎn)數(shù)量也隨之增加.理論上,錨點(diǎn)的數(shù)量可能會(huì)導(dǎo)致MC充電成本的增加.本文提出的HNDLE-CB算法產(chǎn)生的錨點(diǎn)個(gè)數(shù)始終低于其他兩種算法產(chǎn)生的錨點(diǎn)個(gè)數(shù).這是因?yàn)楸舅惴ㄍㄟ^網(wǎng)絡(luò)覆蓋率以及節(jié)點(diǎn)的度數(shù)合理的規(guī)劃出錨點(diǎn)的生成過程.從圖6(b)中可以看到隨著覆蓋半徑的增大,錨點(diǎn)個(gè)數(shù)呈現(xiàn)下降的趨勢(shì).這是因?yàn)橹C振中繼器的覆蓋半徑越大,覆蓋的節(jié)點(diǎn)個(gè)數(shù)越多,所需要的錨點(diǎn)就會(huì)越少.

5.2 節(jié)點(diǎn)失效率

本組實(shí)驗(yàn)討論各算法分別產(chǎn)生的節(jié)點(diǎn)失效率的情形.從圖6(c)可以清楚地看到,當(dāng)節(jié)點(diǎn)個(gè)數(shù)從25到200呈現(xiàn)線性增長(zhǎng)時(shí),節(jié)點(diǎn)的失效率也隨之增長(zhǎng).這是因?yàn)楣?jié)點(diǎn)數(shù)量增多時(shí),在一段時(shí)間內(nèi)節(jié)點(diǎn)缺電個(gè)數(shù)的幾率會(huì)增大,這時(shí)會(huì)向MC提出更多的充電請(qǐng)求,使得MC的充電負(fù)擔(dān)過重,一旦超過MC的服務(wù)能力時(shí),死亡節(jié)點(diǎn)的數(shù)量便會(huì)增加,因此各算法所得的節(jié)點(diǎn)失效率都是呈增長(zhǎng)趨勢(shì).而本文提出的HNDLE-CB算法的節(jié)點(diǎn)失效率相較于Cellular MWRN、RI-CB MWRN始終更低.這是由于本策略會(huì)提出一種充電優(yōu)先級(jí)算法,會(huì)優(yōu)先選擇密度較為集中并且缺電情形較為嚴(yán)重的節(jié)點(diǎn)充電,極大的避免了節(jié)點(diǎn)快速陷入饑餓狀態(tài)甚至死亡,因此該算法能最大程度減少網(wǎng)絡(luò)中缺電節(jié)點(diǎn)的死亡數(shù)量.如圖6(d)所示,當(dāng)充電效率提高時(shí),MC有更多的時(shí)間去給缺電節(jié)點(diǎn)充電,因此失效率會(huì)下降.

圖6 3種算法在4個(gè)不同指標(biāo)的性能對(duì)比Fig.6 Performance comparison of three algorithms in four different indicators

5.3 充電成本

本組實(shí)驗(yàn)討論各算法分別導(dǎo)致的充電成本的情形.圖6(e)展示了節(jié)點(diǎn)數(shù)量與充電成本之間的關(guān)系.當(dāng)節(jié)點(diǎn)個(gè)數(shù)為達(dá)到125時(shí),充電成本呈增長(zhǎng)趨勢(shì),而當(dāng)節(jié)點(diǎn)個(gè)數(shù)超過125時(shí)充電成本有所下降.出現(xiàn)這種現(xiàn)象的原因是當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí),提出充電請(qǐng)求的節(jié)點(diǎn)的分布比較稀疏,導(dǎo)致有些節(jié)點(diǎn)距離MC的位置較遠(yuǎn),MC為各種節(jié)點(diǎn)充電的過程中將大量的工作花費(fèi)在移動(dòng),使得MC的移動(dòng)距離增大,從而增加MC的充電成本.而當(dāng)節(jié)點(diǎn)個(gè)數(shù)達(dá)到一定程度時(shí),缺電節(jié)點(diǎn)的個(gè)數(shù)相應(yīng)也會(huì)增加,導(dǎo)致服務(wù)池中排滿了許多需要充電的節(jié)點(diǎn),但MC此時(shí)只能在較近的距離內(nèi)發(fā)現(xiàn)滿足條件的缺電節(jié)點(diǎn),來不及響應(yīng)距離較遠(yuǎn)的待充電節(jié)點(diǎn),一旦等待時(shí)間變久即失效,于是MC一直在為自己附近的缺電節(jié)點(diǎn)充電,使得MC的移動(dòng)總距離減小,因而充電成本下降.而圖6(f)中,三種算法的充電成本都會(huì)隨著充電效率的增加而增大.因?yàn)槌潆娦实奶岣?MC為節(jié)點(diǎn)充電的速度就越快.那么為完成更多的充電請(qǐng)求MC的移動(dòng)總距離就會(huì)越大.

5.4 網(wǎng)絡(luò)生存時(shí)間

本組實(shí)驗(yàn)討論各算法的網(wǎng)絡(luò)生存時(shí)間的情形.從圖6(g)中可以看出,隨著節(jié)點(diǎn)個(gè)數(shù)的增加,網(wǎng)絡(luò)生存時(shí)間也在相應(yīng)降低.該圖證明了當(dāng)節(jié)點(diǎn)數(shù)量增多時(shí),網(wǎng)絡(luò)的生存周期呈遞減趨勢(shì)的現(xiàn)象.這是由于隨著節(jié)點(diǎn)數(shù)量增多時(shí),MC無法滿足目標(biāo)節(jié)點(diǎn)的充電請(qǐng)求,使得節(jié)點(diǎn)死亡個(gè)數(shù)增多從而導(dǎo)致網(wǎng)絡(luò)停止工作.在圖6(h)中,隨著充電速率的遞增,網(wǎng)絡(luò)生存周期不斷增長(zhǎng).這是因?yàn)楫?dāng)充電速率增加時(shí),MC為節(jié)點(diǎn)的充電效率得到提升,可以在同樣的時(shí)間內(nèi)為請(qǐng)求節(jié)點(diǎn)提供高效的充電服務(wù),因此節(jié)點(diǎn)的死亡率會(huì)下降,從而增加了網(wǎng)絡(luò)的生存周期.

6 結(jié) 語

無線充電技術(shù)可以達(dá)到延長(zhǎng)網(wǎng)絡(luò)的生命周期,能夠有效處理現(xiàn)階段傳感器節(jié)點(diǎn)能量不足的問題.為了達(dá)到更優(yōu)的效果,本文研究如何基于聚類進(jìn)行分簇尋找錨節(jié)點(diǎn)并提出一種高效的HNDLE-CB多跳能量補(bǔ)充策略.該策略根據(jù)網(wǎng)絡(luò)覆蓋率計(jì)算簇點(diǎn)個(gè)數(shù),結(jié)合節(jié)點(diǎn)的連通度初始化簇點(diǎn)位置,聚類迭代得到簇點(diǎn)的最終位置,通過節(jié)點(diǎn)密度電量比率Ψ計(jì)算傳感器節(jié)點(diǎn)的充電優(yōu)先級(jí),按照這樣的充電方式優(yōu)先為分布密集且容易失效的節(jié)點(diǎn)充電,能夠適應(yīng)動(dòng)態(tài)的網(wǎng)絡(luò)變化,滿足正常充電的需求.廣泛的仿真結(jié)果證明了HNDLE-CB策略與其他策略相比,能夠在一定程度上有效降低節(jié)點(diǎn)失效率,提高網(wǎng)絡(luò)充電效率.