賈明偉，吳 敏，沙 超,2，王汝傳,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003；2.蘇州大學(xué) 江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006)

基于鄰居節(jié)點(diǎn)位置的無(wú)線傳感網(wǎng)休眠算法

賈明偉1，吳 敏1，沙 超1,2，王汝傳1,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003；2.蘇州大學(xué) 江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006)

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)往往以隨機(jī)方式密集部署，從而易于產(chǎn)生大量冗余。文中在考慮網(wǎng)絡(luò)覆蓋率的前提下，提出了一種休眠調(diào)度算法。節(jié)點(diǎn)根據(jù)自己與鄰居節(jié)點(diǎn)的位置關(guān)系，計(jì)算鄰居節(jié)點(diǎn)對(duì)自己感知區(qū)域的覆蓋程度。若鄰居節(jié)點(diǎn)對(duì)自己的感知區(qū)域覆蓋度超過(guò)給定的閾值，則節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。仿真實(shí)驗(yàn)證明了算法的有效性，通過(guò)關(guān)閉網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)，節(jié)省了網(wǎng)絡(luò)能量，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期；和同類算法相比較，算法檢測(cè)冗余節(jié)點(diǎn)的能力明顯優(yōu)于同類算法，較大程度地減少了網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)。

無(wú)線傳感器網(wǎng)絡(luò)；休眠；覆蓋冗余；鄰居節(jié)點(diǎn)位置

0 引 言

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的部署方式有兩種：確定性部署和隨機(jī)性部署。針對(duì)一些價(jià)值比較昂貴的無(wú)線傳感器節(jié)點(diǎn)或者受限于特定的應(yīng)用需求，無(wú)線節(jié)點(diǎn)多采用確定性部署;而針對(duì)一些價(jià)值比較低廉或者確定性部署無(wú)法完成的無(wú)線傳感器網(wǎng)絡(luò)環(huán)境，無(wú)線節(jié)點(diǎn)采用隨機(jī)性部署[1]。在隨機(jī)性部署的無(wú)線傳感器網(wǎng)絡(luò)中，為了保證節(jié)點(diǎn)完全覆蓋目標(biāo)范圍，節(jié)點(diǎn)的密度往往很大,從而造成冗余[2-3]。判斷出這些冗余節(jié)點(diǎn)，并將其休眠既可以節(jié)省網(wǎng)絡(luò)的能量又能減少網(wǎng)絡(luò)中信道沖突發(fā)生的概率。

無(wú)線傳感器網(wǎng)絡(luò)一經(jīng)部署，節(jié)點(diǎn)往往不能移動(dòng)，節(jié)點(diǎn)的電池也不可以替換，所以能量問(wèn)題一直是無(wú)線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)。在滿足覆蓋率的前提下，讓一部分節(jié)點(diǎn)處于休眠狀態(tài)可以有效地節(jié)省網(wǎng)絡(luò)的總體能量，從而延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期。

文中提出一種覆蓋冗余節(jié)點(diǎn)判別算法(SALN)。傳感器節(jié)點(diǎn)根據(jù)自己以及鄰居節(jié)點(diǎn)的位置計(jì)算自己被鄰居節(jié)點(diǎn)覆蓋的程度，當(dāng)節(jié)點(diǎn)被鄰居節(jié)點(diǎn)的覆蓋度達(dá)到預(yù)定閾值時(shí)，節(jié)點(diǎn)判定自己為冗余節(jié)點(diǎn)，從而進(jìn)入休眠狀態(tài)。

1 相關(guān)工作

當(dāng)前的無(wú)線傳感器網(wǎng)絡(luò)休眠調(diào)度算法主要分為以下幾類:第一類是根據(jù)網(wǎng)絡(luò)的連通性判斷節(jié)點(diǎn)是否需要休眠，在不改變網(wǎng)絡(luò)連通性的前提下休眠冗余節(jié)點(diǎn)[4-5];第二類是基于距離的休眠調(diào)度算法，根據(jù)節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的距離，為節(jié)點(diǎn)設(shè)置不同的休眠概率[4];第三類是根據(jù)網(wǎng)絡(luò)的覆蓋率判斷節(jié)點(diǎn)是否為冗余節(jié)點(diǎn)，在滿足一定覆蓋率的前提下，將部分節(jié)點(diǎn)休眠[6-11]。此外，還有根據(jù)實(shí)際的應(yīng)用需求對(duì)節(jié)點(diǎn)進(jìn)行輪轉(zhuǎn)休眠調(diào)度，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期。

在第一類休眠調(diào)度算法中，文獻(xiàn)[4]首先將網(wǎng)絡(luò)劃分為一個(gè)個(gè)網(wǎng)格，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以和相鄰網(wǎng)格中的任意節(jié)點(diǎn)通信，其次讓網(wǎng)格中的節(jié)點(diǎn)輪轉(zhuǎn)工作，以節(jié)省網(wǎng)絡(luò)能量。文獻(xiàn)[5]將擁有相同鄰居的節(jié)點(diǎn)分在同一組中，在滿足網(wǎng)絡(luò)連通性的前提下，根據(jù)一定條件，將單獨(dú)的節(jié)點(diǎn)加到一個(gè)組中或自己形成一個(gè)組，每個(gè)組中選一個(gè)節(jié)點(diǎn)工作，其余休眠。這類算法以網(wǎng)絡(luò)的連通性作為判斷依據(jù)，從而決定一個(gè)節(jié)點(diǎn)是否休眠。文獻(xiàn)[6]是典型的第二類休眠調(diào)度算法，它將網(wǎng)絡(luò)分簇，簇中節(jié)點(diǎn)根據(jù)與簇頭的距離設(shè)置不同的休眠概率。在第三類休眠調(diào)度算法中，文獻(xiàn)[7]提出了一種分布式的休眠調(diào)度算法。算法的基本思想是：初始時(shí)，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)節(jié)點(diǎn)組，在保障覆蓋度的前提下，相鄰的節(jié)點(diǎn)組融合為一個(gè)節(jié)點(diǎn)組，直到節(jié)點(diǎn)組之間不能再融合，融合階段結(jié)束后，算法在每一個(gè)節(jié)點(diǎn)組中選出1～2個(gè)節(jié)點(diǎn)處于工作狀態(tài)，其余節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。文獻(xiàn)[8]提出一種輕量級(jí)部署調(diào)度算法，稱為L(zhǎng)DAS。算法先設(shè)計(jì)一個(gè)節(jié)點(diǎn)被它的n個(gè)鄰居節(jié)點(diǎn)完全覆蓋的概率，然后計(jì)算一個(gè)節(jié)點(diǎn)被它的n個(gè)鄰居覆蓋的區(qū)域占自身監(jiān)測(cè)區(qū)域的百分比，基于這兩個(gè)結(jié)果判斷節(jié)點(diǎn)是否應(yīng)該休眠。文獻(xiàn)[9]在文獻(xiàn)[8]的基礎(chǔ)上，重點(diǎn)考慮了兩個(gè)問(wèn)題：一是大量節(jié)點(diǎn)同時(shí)休眠產(chǎn)生感知盲區(qū)問(wèn)題；二是節(jié)點(diǎn)是否處于網(wǎng)絡(luò)邊界問(wèn)題。文獻(xiàn)[10]提出了一種面向異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)休眠調(diào)度算法。首先根據(jù)鄰居節(jié)點(diǎn)之間的距離對(duì)鄰居節(jié)點(diǎn)進(jìn)行分類，針對(duì)不同類型的鄰居節(jié)點(diǎn)，算出滿足覆蓋率條件下所需此種類型鄰居節(jié)點(diǎn)的最少個(gè)數(shù)，然后節(jié)點(diǎn)根據(jù)所有類型的鄰居傳感器節(jié)點(diǎn)的個(gè)數(shù)判斷是否休眠。第三類算法主要是判斷休眠一個(gè)節(jié)點(diǎn)后對(duì)網(wǎng)絡(luò)覆蓋率的影響，若一個(gè)節(jié)點(diǎn)休眠后對(duì)網(wǎng)絡(luò)覆蓋率無(wú)影響或影響很小，則判定為冗余。

此外，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的區(qū)域覆蓋問(wèn)題，Tian等[12]提出基于節(jié)點(diǎn)狀態(tài)調(diào)度的分布式覆蓋算法；Zhang等[13]提出分布式節(jié)點(diǎn)密度控制算法，根據(jù)節(jié)點(diǎn)鄰居和自己的位置信息計(jì)算相互的覆蓋關(guān)系；Y.Xu等[14]采用整數(shù)序列編碼的遺傳算法，找出網(wǎng)絡(luò)的一個(gè)最小覆蓋子集；M.Cardei等[15]用整數(shù)規(guī)劃調(diào)節(jié)傳感半徑，用貪心算法找到K個(gè)覆蓋子集；H.Chen等[16]把網(wǎng)絡(luò)劃分為網(wǎng)格，并用貪心算法找最小的覆蓋子集。

綜合上述各類休眠調(diào)度算法，文中選取第三類基于覆蓋率的休眠調(diào)度算法作為研究點(diǎn)，重點(diǎn)關(guān)注休眠節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)覆蓋率的影響。受文獻(xiàn)[8,10]的思想啟發(fā)，文中提出一種以鄰居節(jié)點(diǎn)位置及間距來(lái)判斷是否冗余的方法。在滿足指定覆蓋率的前提下，最大化休眠網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)。

2 網(wǎng)絡(luò)模型及相關(guān)定義

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

(1)為了滿足連通性和覆蓋率，節(jié)點(diǎn)以隨機(jī)方式密集部署。

(2)節(jié)點(diǎn)的通信距離和感知距離相同。感知范圍是以節(jié)點(diǎn)所在位置為圓心、感知距離為半徑的圓。

(3)節(jié)點(diǎn)自帶定位功能，暫時(shí)不考慮節(jié)點(diǎn)的定位問(wèn)題。

(4)節(jié)點(diǎn)的能量受限，且一經(jīng)部署不能移動(dòng)，不能替換電池。

2.2 相關(guān)定義

(1)鄰居節(jié)點(diǎn)。

網(wǎng)絡(luò)中節(jié)點(diǎn)i的鄰居集合定義為:

(1)

其中：ix為節(jié)點(diǎn)i的x坐標(biāo)；iy為節(jié)點(diǎn)i的y坐標(biāo)；R為傳感器節(jié)點(diǎn)的最大感知距離。

(2)覆蓋重疊區(qū)域。

假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)i有一個(gè)鄰居節(jié)點(diǎn)j，兩個(gè)節(jié)點(diǎn)的感知覆蓋區(qū)域所形成的圓(以下簡(jiǎn)稱感知圓)相交于P和Q兩點(diǎn)，以節(jié)點(diǎn)i的感知圓的兩條半徑以及圓上的一段弧組成的扇形區(qū)域稱作節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的覆蓋重疊區(qū)域，如圖1中陰影部分所示。

(3)覆蓋重疊區(qū)域圓心角。

節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的覆蓋重疊圓心角即為圖1中的α角，其大小可由式(2)給出：

(2)

其中：r為兩個(gè)節(jié)點(diǎn)之間的距離；R為節(jié)點(diǎn)感知圓的半徑。

(4)覆蓋區(qū)間。

假設(shè)節(jié)點(diǎn)的感知圓上的每一個(gè)點(diǎn)擁有一個(gè)弧度值，定義過(guò)圓心平行于Y軸與圓周相交的點(diǎn)的弧度值為0弧度，圓上其他點(diǎn)的弧度值按圓周上的逆時(shí)針?lè)较蛞来卧龃?。?jié)點(diǎn)j在節(jié)點(diǎn)i上的覆蓋區(qū)間定義為[q,p]，其中q為Q點(diǎn)的弧度值，p為P點(diǎn)的弧度值，Q、P為兩感知圓的交點(diǎn)。

(5)節(jié)點(diǎn)的被覆蓋率。

節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)覆蓋區(qū)間的集合定義為：

(3)

舉例說(shuō)明，如圖1所示，節(jié)點(diǎn)i有三個(gè)鄰居節(jié)點(diǎn)，分別為節(jié)點(diǎn)j、h、g，節(jié)點(diǎn)j、h、g對(duì)節(jié)點(diǎn)i的覆蓋重疊區(qū)域圓心角分別為α、β、γ，相應(yīng)的覆蓋區(qū)間分別為[q,p]、[e,f]、[c,d]。節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的覆蓋區(qū)間的并集為：

(4)

從圖1可以看出，節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的覆蓋重疊區(qū)域占據(jù)了節(jié)點(diǎn)i感知區(qū)域的絕大部分。可簡(jiǎn)單認(rèn)為只有銳角∠EiP(i為節(jié)點(diǎn)i的感知圓的圓心)所對(duì)應(yīng)扇形區(qū)域未被節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)覆蓋，其余部分全部被其鄰居節(jié)點(diǎn)覆蓋(實(shí)際上，節(jié)點(diǎn)i的未覆蓋區(qū)域面積要小于∠EiP所對(duì)應(yīng)扇形區(qū)域的面積)。此時(shí)節(jié)點(diǎn)i的被覆蓋率為：

(5)

圖1 節(jié)點(diǎn)被覆蓋率計(jì)算

3 方法實(shí)現(xiàn)及分析

3.1 SALN算法實(shí)現(xiàn)

SALN算法分為三個(gè)階段：節(jié)點(diǎn)初始化階段、內(nèi)部計(jì)算階段和休眠調(diào)度階段。

步驟1：節(jié)點(diǎn)初始化階段。

傳感器節(jié)點(diǎn)部署完成之后，每個(gè)節(jié)點(diǎn)向外界發(fā)送自己的坐標(biāo)位置，同時(shí)監(jiān)聽(tīng)鄰居節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)包，數(shù)據(jù)包包含鄰居節(jié)點(diǎn)的x坐標(biāo)和y坐標(biāo)。

步驟2：節(jié)點(diǎn)內(nèi)部計(jì)算階段。

當(dāng)通信完成之后，節(jié)點(diǎn)為每一個(gè)鄰居節(jié)點(diǎn)保存一個(gè)坐標(biāo)值。節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的坐標(biāo)值和自身的坐標(biāo)值計(jì)算各個(gè)鄰居節(jié)點(diǎn)的覆蓋區(qū)間。計(jì)算完成后，節(jié)點(diǎn)將這些覆蓋區(qū)間進(jìn)行合并，并計(jì)算出節(jié)點(diǎn)被鄰居節(jié)點(diǎn)的覆蓋率。關(guān)于覆蓋區(qū)間的計(jì)算，舉例說(shuō)明如下。如圖1所示，若計(jì)算節(jié)點(diǎn)j在節(jié)點(diǎn)i上的覆蓋區(qū)間，首先計(jì)算C點(diǎn)的弧度值。當(dāng)節(jié)點(diǎn)i的x坐標(biāo)值大于節(jié)點(diǎn)j的x坐標(biāo)值時(shí)，c=β；當(dāng)節(jié)點(diǎn)i的x坐標(biāo)值小于等于節(jié)點(diǎn)j的x坐標(biāo)值時(shí)，c=360-β。公式如下：

(6)

(7)

節(jié)點(diǎn)j在節(jié)點(diǎn)i上的覆蓋區(qū)間為[q,p](p、q均在0～360之間)。q和p的值由式(8)和式(9)給出。

(8)

(9)

步驟3:節(jié)點(diǎn)休眠調(diào)度階段。

節(jié)點(diǎn)根據(jù)計(jì)算得出的被覆蓋率，同給定的閾值θ(0～1之間)相比較，從而確定自己是否為冗余節(jié)點(diǎn)。如果節(jié)點(diǎn)的被覆蓋率大于θ，節(jié)點(diǎn)可以進(jìn)入休眠狀態(tài)；否則，正常工作。θ的值通常根據(jù)在網(wǎng)絡(luò)實(shí)際運(yùn)行時(shí)用戶所要求的覆蓋率進(jìn)行設(shè)置。

3.2 時(shí)間復(fù)雜度分析

由SALN算法的實(shí)現(xiàn)過(guò)程可知，節(jié)點(diǎn)判斷自己是否冗余所費(fèi)時(shí)長(zhǎng)主要和節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量有關(guān)。若網(wǎng)絡(luò)中節(jié)點(diǎn)的平均鄰居數(shù)量為nnei，則SALN的時(shí)間復(fù)雜度為O(nnei)，由于節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)必定小于節(jié)點(diǎn)總數(shù)n，故時(shí)間復(fù)雜度為O(n)。

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

4.1 實(shí)驗(yàn)設(shè)置

用Matlab+Java進(jìn)行仿真實(shí)驗(yàn)，通過(guò)改變網(wǎng)絡(luò)規(guī)模、節(jié)點(diǎn)的被覆蓋率閾值，從而觀察網(wǎng)絡(luò)休眠節(jié)點(diǎn)的數(shù)量、網(wǎng)絡(luò)的總體覆蓋率。由于節(jié)點(diǎn)部署的方式為隨機(jī)性部署，故每次的實(shí)驗(yàn)結(jié)果不唯一。以下實(shí)驗(yàn)數(shù)據(jù)均是在同一實(shí)驗(yàn)參數(shù)條件下，重復(fù)10次的平均值。

4.2 算法自身對(duì)比實(shí)驗(yàn)

當(dāng)在網(wǎng)絡(luò)中撒播250個(gè)感知半徑為10 m的節(jié)點(diǎn)時(shí)，增大網(wǎng)絡(luò)規(guī)模，在不同的閾值下，網(wǎng)絡(luò)達(dá)到休眠條件的節(jié)點(diǎn)數(shù)量如圖2所示。

圖2 不同條件下節(jié)點(diǎn)休眠個(gè)數(shù)對(duì)比

從圖中可以看出,網(wǎng)絡(luò)規(guī)模越大，滿足休眠條件的節(jié)點(diǎn)數(shù)量就越少。因?yàn)榫W(wǎng)絡(luò)規(guī)模越大，節(jié)點(diǎn)之間的平均距離就越大，節(jié)點(diǎn)的平均鄰居數(shù)就越少，平均被覆蓋率越小，從而造成休眠節(jié)點(diǎn)數(shù)減少。在同一網(wǎng)絡(luò)規(guī)模下，被覆蓋率閾值設(shè)置越大，休眠的節(jié)點(diǎn)數(shù)量也越少。因?yàn)楸桓采w率閾值越高，滿足覆蓋率閾值條件的節(jié)點(diǎn)數(shù)就越少。

在150 m×150 m的區(qū)域內(nèi)隨機(jī)撒播250個(gè)和200個(gè)感知半徑為10 m的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)初始化時(shí)的覆蓋情況如圖3(a)和(c)所示，圖中灰色的區(qū)域?yàn)楣?jié)點(diǎn)的感知區(qū)域，空白區(qū)域?yàn)槲幢还?jié)點(diǎn)覆蓋的區(qū)域。圖3(b)和(d)為節(jié)點(diǎn)調(diào)用完算法后網(wǎng)絡(luò)的覆蓋情況。

從對(duì)比圖可以直觀且明顯地看出，調(diào)用算法后網(wǎng)絡(luò)中冗余節(jié)點(diǎn)的數(shù)量大大減少了。

表1為在150 m×150 m的區(qū)域內(nèi)隨機(jī)撒播250個(gè)節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)設(shè)置不同的被覆蓋率閾值時(shí)，網(wǎng)絡(luò)的總體覆蓋率的變化情況，此時(shí)網(wǎng)絡(luò)未運(yùn)行算法時(shí)的覆蓋率為93.9%。

圖3 算法運(yùn)行前后直觀對(duì)比圖

節(jié)點(diǎn)被覆蓋率算法運(yùn)行后覆蓋率/%320/36093.39330/36093.62340/36093.9350/36093.9360/36093.9

從表1可以看出,當(dāng)節(jié)點(diǎn)的被覆蓋閾值設(shè)置為340/350、350/360時(shí)網(wǎng)絡(luò)的總體覆蓋率并無(wú)影響。此時(shí)滿足休眠條件的節(jié)點(diǎn)個(gè)數(shù)分別為70以及53，休眠節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的比值分別為28.0%和21.2%，也就是說(shuō)在不改變網(wǎng)絡(luò)原始覆蓋率的前提下，執(zhí)行算法后，可以減少網(wǎng)絡(luò)中21.2%～28.0%的冗余節(jié)點(diǎn)。即使節(jié)點(diǎn)的被覆蓋率設(shè)置為320/360，相比較未調(diào)用算法時(shí)，網(wǎng)絡(luò)的總體覆蓋率也只下降了0.61個(gè)百分點(diǎn)而已，而此時(shí)，休眠節(jié)點(diǎn)的占比可達(dá)到28.0%，由此可以看出文中算法的實(shí)用性和高效性。

表2為隨機(jī)撒播250個(gè)以及300個(gè)節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)的總體覆蓋率隨網(wǎng)絡(luò)規(guī)模的變化情況。

從表中可以看出，并非網(wǎng)絡(luò)規(guī)模越小，部署的密度越大，節(jié)點(diǎn)調(diào)用算法后網(wǎng)絡(luò)的總體覆蓋率就越大。當(dāng)網(wǎng)絡(luò)的規(guī)模過(guò)小，密度過(guò)大時(shí)，節(jié)點(diǎn)調(diào)用完算法后，網(wǎng)絡(luò)的總體覆蓋率反而會(huì)下降。造成這種現(xiàn)象的原因是若網(wǎng)絡(luò)中的節(jié)點(diǎn)很密集，滿足被覆蓋率閾值的節(jié)點(diǎn)占比過(guò)高，從而大量的傳感器節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，使網(wǎng)絡(luò)總體覆蓋率降低。一種解決辦法是：為網(wǎng)絡(luò)中的節(jié)點(diǎn)設(shè)置一個(gè)休眠優(yōu)先級(jí)。當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中依次休眠時(shí)，節(jié)點(diǎn)計(jì)算覆蓋區(qū)間時(shí)就不會(huì)再考慮已休眠的節(jié)點(diǎn)，從而不會(huì)出現(xiàn)這種現(xiàn)象。當(dāng)撒播250個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)規(guī)模為100 m×150 m時(shí)，總體覆蓋率出現(xiàn)最大值。此時(shí)的網(wǎng)絡(luò)密度為100 m2內(nèi)有1.67個(gè)節(jié)點(diǎn)。同時(shí)，當(dāng)撒播300個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)規(guī)模為150 m×150 m時(shí),網(wǎng)絡(luò)總體覆蓋率達(dá)到最大值。此時(shí)的節(jié)點(diǎn)密度為100 m2內(nèi)有1.33個(gè)節(jié)點(diǎn)。算法實(shí)際投入運(yùn)行時(shí)，網(wǎng)絡(luò)的節(jié)點(diǎn)密度應(yīng)在1.33～1.67之間，這樣監(jiān)測(cè)區(qū)域才能達(dá)到最優(yōu)覆蓋。

表2 不同網(wǎng)絡(luò)密度下算法執(zhí)行后的覆蓋率 %

4.3 SALN算法同其他算法的對(duì)比實(shí)驗(yàn)

下圖為在不同實(shí)驗(yàn)條件設(shè)置下，SALN算法和Random算法、GBS算法、NDBS算法的對(duì)比實(shí)驗(yàn)圖，得到不同網(wǎng)絡(luò)覆蓋率以及撒播不同節(jié)點(diǎn)數(shù)目對(duì)節(jié)點(diǎn)關(guān)閉率(休眠節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比值)的影響。其中，Random算法是在保證特定網(wǎng)絡(luò)覆蓋率的情況下，隨機(jī)性休眠網(wǎng)絡(luò)中的節(jié)點(diǎn)。GBS算法是首先將網(wǎng)絡(luò)劃分為網(wǎng)格，針對(duì)每個(gè)網(wǎng)格中的節(jié)點(diǎn)，在保證覆蓋率的前提下，隨機(jī)休眠節(jié)點(diǎn)。在NDBS算法中，節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的數(shù)量和指定的網(wǎng)絡(luò)覆蓋率判斷自己是否是冗余節(jié)點(diǎn)，是否休眠[8]。

圖4為在100 m×100 m的網(wǎng)絡(luò)中撒播500個(gè)半徑為10 m的節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)關(guān)閉率隨著網(wǎng)絡(luò)覆蓋率的變化情況。當(dāng)網(wǎng)絡(luò)的實(shí)際覆蓋率在0.5～0.9[8]之間變化時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)閉率呈下降趨勢(shì)。由圖4也可以看出，指定的網(wǎng)絡(luò)覆蓋率越高，滿足關(guān)閉條件的節(jié)點(diǎn)數(shù)量也就越少。同時(shí)，在相同的網(wǎng)絡(luò)覆蓋率條件下，SALN算法的節(jié)點(diǎn)關(guān)閉率明顯高于其他三種算法。

圖4 不同覆蓋率下節(jié)點(diǎn)關(guān)閉率的變化情況

圖5是在100 m×100 m的網(wǎng)絡(luò)中撒播不同數(shù)量的節(jié)點(diǎn)時(shí)，四種算法的節(jié)點(diǎn)關(guān)閉率的變化趨勢(shì)圖。此時(shí)節(jié)點(diǎn)的半徑為10 m，網(wǎng)絡(luò)覆蓋率為0.8。當(dāng)在網(wǎng)絡(luò)中的撒播節(jié)點(diǎn)數(shù)量越多時(shí)，滿足關(guān)閉條件的節(jié)點(diǎn)數(shù)量也就越多。從圖5中也可以看出，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目增加時(shí)，四種算法的節(jié)點(diǎn)關(guān)閉率均呈現(xiàn)上升狀態(tài)。同時(shí)，在相同的節(jié)點(diǎn)數(shù)目下，SALN算法的節(jié)點(diǎn)關(guān)閉率要高于其他三種算法。

圖5 不同節(jié)點(diǎn)數(shù)目下節(jié)點(diǎn)關(guān)閉率的變化情況

由圖4、5可以看出，無(wú)論是改變網(wǎng)絡(luò)的覆蓋率還是在網(wǎng)絡(luò)中撒播不同的節(jié)點(diǎn)數(shù)量，文中提出的SALN算法在四種關(guān)閉冗余節(jié)點(diǎn)的算法中有明顯優(yōu)勢(shì)。

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

文中提出了一種基于鄰居節(jié)點(diǎn)位置的覆蓋冗余判別算法。節(jié)點(diǎn)只需知道網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的位置，即可判斷自己是否冗余，減少了網(wǎng)絡(luò)中的額外通信量，節(jié)省了網(wǎng)絡(luò)能量消耗。仿真實(shí)驗(yàn)從網(wǎng)絡(luò)規(guī)模、休眠節(jié)點(diǎn)數(shù)、被覆蓋閾值等方面對(duì)SALN算法進(jìn)行了驗(yàn)證和分析，計(jì)算出了網(wǎng)絡(luò)部署時(shí)的最優(yōu)部署值區(qū)間；同時(shí)從網(wǎng)絡(luò)覆蓋率和撒播不同數(shù)量節(jié)點(diǎn)將該算法同其他算法進(jìn)行了比較，驗(yàn)證了該算法的關(guān)閉冗余節(jié)點(diǎn)能力。

在下一步工作中，將優(yōu)化文中提出的算法，以防止網(wǎng)絡(luò)中大量節(jié)點(diǎn)同時(shí)進(jìn)入休眠狀態(tài)?？紤]經(jīng)過(guò)計(jì)算后滿足休眠條件的節(jié)點(diǎn)，在其鄰居節(jié)點(diǎn)休眠后不再滿足休眠條件這種特殊情況的出現(xiàn)。同時(shí)，考慮加入節(jié)點(diǎn)的輪轉(zhuǎn)工作。

[1] 馬祖長(zhǎng),孫怡寧,梅 濤.無(wú)線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25(4):114-124.

[2] 徐朋豪,馮玉光,奚文駿,等.基于ZigBee的無(wú)線溫濕度采集系統(tǒng)研究[J].國(guó)外電子測(cè)量技術(shù),2013,32(1):33-36.

[3] 石 欣,冉啟可,范 敏,等.無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)加權(quán)DV-Distance算法[J].儀器儀表學(xué)報(bào),2013,34(9):1975-1981.

[4] Zebbane B.Energy-efficient protocol based sleep-scheduling for wireless sensor networks[C]//Proceedings of 2012 international conference on complex systems.[s.l.]:[s.n.],2012:407-412.

[5] Zebbane B.Enhancing the sensor network lifetime by topologycontrolandsleep-scheduling[C]//Proceedingsofinternationalconferenceonsmartcommunicationsinnetworktechnologies.[s.l.]:IEEE,2013.

[6]SinghB,LobiyalDK.Energypreservingsleepschedulingforcluster-basedwirelesssensornetworks[C]//Procofsixthinternationalconferenceoncontemporarycomputing.[s.l.]:IEEE,2013:97-101.

[7] 石冠雄.節(jié)點(diǎn)休眠調(diào)度仿真系統(tǒng)及優(yōu)化算法[D].天津:天津大學(xué),2012.

[8]WuK,GaoY,LiFL,etal.Lightweightdeployment-awareschedulingforwirelesssensornetworks[J].MobileNetworksandApplications,2005,10(6):837-852.

[9] 溫 濤,張冬青,郭 權(quán),等.無(wú)線傳感器網(wǎng)絡(luò)冗余節(jié)點(diǎn)休眠調(diào)度算法[J].通信學(xué)報(bào),2014,35(10):67-80.

[10] 孫力娟,魏 靜,郭 劍,等.面向異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào),2014,42(10):1907-1912.

[11] 韓志杰,吳志斌,王汝傳,等.新的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制算法[J].通信學(xué)報(bào),2011,32(10):174-184.

[12]TianD,GeorganasND.Acoverage-preservingnodeschedulingschemeforlargewirelesssensornetworks[C]//ProcoffirstACMinternationalworkshoponwirelesssensornetworksandapplications.NewYork:ACMPress,2002:32-41.

[13]ZhangH,HouJC.Maintainingschemecoverageandconnectivityinlargesensornetworks[C]//ProcofNSFinternationalworkshopontheoreticalandalgorithmicaspectsofsensor,adhocwireless,andpeer-to-peernetworks.Chicago,USA:[s.n.],2004.

[14]XuY,YaoX.AGAapproachtotheoptimalplacementofsensorsinwirelesssensornetworkswithobstaclesandpreferences[C]//ProcofIEEEconsumercommunicationsandnetworkingconference.LasVegas,NV,USA:IEEE,2006:127-131.

[15]CardeiM,WuJ,LuM,etal.Maximumnetworklifetimeinwirelesssensornetworkswithadjustablesensingranges[C]//ProceedingsoftheIEEEinternationalconferenceonwirelessandmobilecomputingnetworkingandcommunications.[s.l.]:IEEE,2005:438-445.

[16]ChenH,WuH,TzengNF.Grid-basedapproachforworkingnodeselectioninwirelesssensornetworks[C]//ProcofIEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2004:3673-3678.

A Sleeping Algorithm for Wireless Sensor Network Based on Location of Neighbors

JIA Ming-wei1,WU Min1,SHA Chao1,2,WANG Ru-chuan1,2

(1.Computer and Software College,Nanjing University of Posts and Telecommunications, Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province，Soochow University, Suzhou 215006,China)

In Wireless Sensor Networks (WSNs),nodes are densely deployed,which may increase a number of redundant nodes.Considering the network’s coverage,a type of sleeping scheduling algorithm is proposed about coverage redundancy.Each node calculates the coverage rate of its sensing area according to the locations of its neighbors nodes.If the coverage rate is beyond the threshold,the node goes into sleeping mode while other sensor nodes remain active.Simulation experiment shows the effectiveness of the algorithm.By sleeping redundant nodes in the network,network energy is saved and network life is prolonged.Moreover,compared with other algorithms,the ability of the algorithm to detect redundant nodes is much better.The number of redundant nodes is greatly reduced in the network.

wireless sensor networks;sleeping scheduling;coverage redundancy;location of neighbors

2015-07-20

2015-10-23

時(shí)間：2016-03-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202355)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20123223120006)；中國(guó)博士后基金(2013M531394)；江蘇省自然科學(xué)基金(BK2012436)；江蘇省博士后基金(0801019C)；江蘇省高校自然科學(xué)基礎(chǔ)研究項(xiàng)目(14KJB520029)；江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題(KJS1327)

賈明偉(1991-)，男，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集、覆蓋等；吳 敏，副教授，碩士生導(dǎo)師，研究方向?yàn)楹Ａ繑?shù)據(jù)管理,網(wǎng)絡(luò)安全技術(shù),密鑰管理和認(rèn)證以及物聯(lián)網(wǎng)在智能家居、醫(yī)療健康護(hù)理等方面的應(yīng)用技術(shù)等；沙 超，副教授，碩士生導(dǎo)師，研究方向?yàn)閃SN的數(shù)據(jù)融合技術(shù)、智能定位算法、QoS路由機(jī)制以及覆蓋調(diào)度技術(shù)等；王汝傳，教授，博士生導(dǎo)師，研究方向?yàn)榛谕ㄐ啪W(wǎng)絡(luò)的計(jì)算機(jī)軟件技術(shù)、網(wǎng)絡(luò)安全技術(shù)、信息網(wǎng)絡(luò)應(yīng)用技術(shù)等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.090.html

TP301.6

A

1673-629X(2016)04-0056-05

10.3969/j.issn.1673-629X.2016.04.012