王瑩瑩,鄭永愛,王詠梅

(蘇州高博軟件技術(shù)職業(yè)學(xué)院,江蘇 蘇州 215163)

0 引言

在無線傳感器網(wǎng)絡(luò)(WSN,wireless sensor network)中，具有感知、計算及通信能力的傳感器節(jié)點(diǎn)被部署在監(jiān)控區(qū)域內(nèi)，實(shí)現(xiàn)對特定物理量的采集，傳感器節(jié)點(diǎn)自組織成網(wǎng)，最終將采集的數(shù)據(jù)傳輸?shù)交綶1]。

在WSN中，大部分傳感器節(jié)點(diǎn)采用電池供電，節(jié)點(diǎn)能量十分有限，若節(jié)點(diǎn)能量耗盡，將影響整個網(wǎng)絡(luò)的運(yùn)行。對于節(jié)點(diǎn)而言，其能量主要消耗在數(shù)據(jù)采集與數(shù)據(jù)傳輸過程中，而傳輸數(shù)據(jù)的能耗遠(yuǎn)遠(yuǎn)大于采集數(shù)據(jù)的能耗，因此利用有限的網(wǎng)絡(luò)資源，在源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間建立一條健壯的、節(jié)能的、高效的、低時延的路徑，減少節(jié)點(diǎn)能耗、延長網(wǎng)絡(luò)生命周期一直是WSN的研究熱點(diǎn)[2-3]。

1 相關(guān)工作

根據(jù)拓?fù)浣Y(jié)構(gòu)不同，當(dāng)前的路由協(xié)議主要分為平面路由與分層路由。在平面路由協(xié)議中網(wǎng)絡(luò)中所有節(jié)點(diǎn)地位相同，節(jié)點(diǎn)數(shù)據(jù)經(jīng)過多跳轉(zhuǎn)發(fā)到達(dá)基站，網(wǎng)絡(luò)健壯性好、易于維護(hù)，但當(dāng)網(wǎng)絡(luò)規(guī)模增大時，節(jié)點(diǎn)能耗與數(shù)據(jù)時延迅速增加，不利于網(wǎng)絡(luò)擴(kuò)展，已經(jīng)不能應(yīng)用于當(dāng)前的大規(guī)模無線傳感器網(wǎng)絡(luò)中。而分簇路由以其良好的可擴(kuò)展性、易維護(hù)性、低時延、高能效等特點(diǎn)，被廣泛應(yīng)用于大型無線傳感器網(wǎng)絡(luò)。

最經(jīng)典的分簇路由是Heinemann等人提出的LEACH[4]分簇路由協(xié)議，其將網(wǎng)絡(luò)劃分為若干個簇，每個簇選舉出一個簇首來負(fù)責(zé)簇內(nèi)成員節(jié)點(diǎn)的管理與數(shù)據(jù)收集與轉(zhuǎn)發(fā)；以“輪”作為網(wǎng)絡(luò)的運(yùn)行周期，每一輪更換一次簇首以均衡節(jié)點(diǎn)的能耗。但是LEACH仍存在許多缺點(diǎn)，例如：簇首的選舉具有一定的隨機(jī)性，無法保證簇首具有足夠的能量完成簇內(nèi)數(shù)據(jù)的收集與轉(zhuǎn)發(fā)；節(jié)點(diǎn)分布的隨機(jī)性，均勻分簇容易會導(dǎo)致簇首負(fù)載不均；簇首通過單跳的方式與基站通信，不適用于大規(guī)模網(wǎng)絡(luò)。眾多學(xué)者針對LEACH的缺點(diǎn)，提出了改進(jìn)算法，為避免低能量節(jié)點(diǎn)被隨機(jī)的選為簇首，文獻(xiàn)[5]將節(jié)點(diǎn)的剩余能量引入到閾值公式中，緩解了低能量節(jié)點(diǎn)過早死亡的問題。EEUC[6]算法引入成簇半徑的概念來控制簇的大小，使距離基站近的簇半徑小，從而使簇首節(jié)約出能量用于數(shù)據(jù)的轉(zhuǎn)發(fā)，由此來均衡節(jié)點(diǎn)的能耗。但是在大型的傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)并不是均勻分布的，在節(jié)點(diǎn)分布密集的區(qū)域，簇首的負(fù)載重，能量消耗大，EEUC算法依然存在節(jié)點(diǎn)能耗不均的狀況。為了進(jìn)一步均衡節(jié)點(diǎn)的能耗，文獻(xiàn)[7]提出了一種非均勻分簇算法[8]，既考慮到節(jié)點(diǎn)的位置信息，又考慮到節(jié)點(diǎn)的分布密度情況。文獻(xiàn)[9]引入“前置感知區(qū)域”的概念，在簇首節(jié)點(diǎn)的“前置感知區(qū)域”內(nèi)根據(jù)節(jié)點(diǎn)的剩余能量以及位置信息選舉附屬簇首節(jié)點(diǎn)，減少了因?yàn)椤澳芰炕貍鳌彼斐傻哪芰肯模瑥亩_(dá)到節(jié)約能耗的目的。文獻(xiàn)[10]提出了一種提基于簇的無線傳感器網(wǎng)絡(luò)交會路由協(xié)議CRRP，用于緩解sink周圍節(jié)點(diǎn)因轉(zhuǎn)發(fā)任務(wù)重而能耗大的問題。

除此之外，眾多學(xué)者將各種聚類算法應(yīng)用在WSN的網(wǎng)絡(luò)分簇中[11-14]，文獻(xiàn)[15]采用k-means聚類算法進(jìn)行簇首選舉，并引入Mobile Agent對簇內(nèi)數(shù)據(jù)進(jìn)行收集以及融合處理。文獻(xiàn)[16]將模糊邏輯的聚類算法用在分簇上，在均勻分環(huán)的基礎(chǔ)上，將節(jié)點(diǎn)的能量、節(jié)點(diǎn)度、節(jié)點(diǎn)到基站的距離、環(huán)寬、啟動能量等參數(shù)作為模糊規(guī)則器的輸入，輸出每一環(huán)的最優(yōu)簇數(shù)以及節(jié)點(diǎn)成為簇首的競爭半徑，從而進(jìn)行不均勻分簇。文獻(xiàn)[17]提出一種基于密度的聚類分析算法，其利用節(jié)點(diǎn)的局部密度差異來建立均衡分散的簇。文獻(xiàn)[18]基于模糊規(guī)則算法考慮節(jié)點(diǎn)相對能量、相對密度以及相對中心度進(jìn)行簇首選舉，采用改進(jìn)的蟻群算法進(jìn)行簇間路由優(yōu)化。

為了進(jìn)一步減少數(shù)據(jù)傳輸過程中節(jié)點(diǎn)能量的消耗，同時兼顧節(jié)點(diǎn)間能耗的均衡以及網(wǎng)絡(luò)的可擴(kuò)展性，本文提出了一種可擴(kuò)展的WSN分簇算法。在簇首選舉階段，綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)度、價值度等因素；滿足能量條件時，采用簇內(nèi)簇首輪換的方式，減少成簇能耗；當(dāng)新節(jié)點(diǎn)加入網(wǎng)絡(luò)時，引入“入網(wǎng)許可值”的概念，來確定新節(jié)點(diǎn)要加入的簇。

2 網(wǎng)絡(luò)模型與節(jié)點(diǎn)能耗模型

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

為了方便研究，本文對無線傳感器網(wǎng)絡(luò)作如下假設(shè)：

1)節(jié)點(diǎn)隨機(jī)分布在監(jiān)控區(qū)域，一經(jīng)部署位置不再發(fā)生變化，基站可以獲知所有節(jié)點(diǎn)的位置信息；

2)網(wǎng)絡(luò)中每一個節(jié)點(diǎn)都具有唯一標(biāo)識的ID，節(jié)點(diǎn)初始能量、存儲能力、處理能力、通信能力相同，節(jié)點(diǎn)可以感知自己的剩余能量，知道自己的位置坐標(biāo)以及基站的位置坐標(biāo)。

3)基站的位置固定，且計算能力以及能量不受限；

4)節(jié)點(diǎn)可以根據(jù)通信距離來調(diào)整通信功率的大小；

5)節(jié)點(diǎn)具有數(shù)據(jù)融合的能力，以減少需要傳輸?shù)臄?shù)據(jù)量。

2.2 節(jié)點(diǎn)能耗模型

如圖1所示，本文采用文獻(xiàn)[19]提出的一階無線電模型，其中節(jié)點(diǎn)能耗包括：發(fā)射電路能耗、放大電路能耗以及接收電路能耗。

圖1 一階無線電模型

傳感器節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)包的能耗為：

(1)

傳感器節(jié)點(diǎn)接收kbit數(shù)據(jù)包的能耗為：

ERx(k)=k·Eelec

(2)

其中：d為數(shù)據(jù)的傳輸距離，Eelec為電路發(fā)送或接收單位bit數(shù)據(jù)的能耗，εfs與εmp分別為自由空間模型與多路徑衰減模型功率放大所需要的能量，當(dāng)傳輸距離小于d0時采用自由空間模型，當(dāng)傳輸距離大于d0時采用多路徑衰減模型，d0取值如公式(3)所示。

(3)

3 算法描述

3.1 網(wǎng)絡(luò)分簇

1)網(wǎng)絡(luò)候選簇首選舉：

網(wǎng)絡(luò)中候選簇首的選舉采用公式(4)，T(i)為節(jié)點(diǎn)Ni的閾值，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)會產(chǎn)生一個0～1的隨機(jī)數(shù)，與節(jié)點(diǎn)閾值進(jìn)行比較，若隨機(jī)數(shù)小于閾值則其被選擇為候選簇首。

(4)

其中：P為節(jié)點(diǎn)當(dāng)選為簇首的概率；Ei為節(jié)點(diǎn)Ni當(dāng)前剩余能量，Eaver為當(dāng)前網(wǎng)絡(luò)中所有節(jié)點(diǎn)能量的平均值，剩余能量越大T(i)的取值就越高，節(jié)點(diǎn)被選中的概率就越大；r表示當(dāng)前節(jié)點(diǎn)連續(xù)未當(dāng)選簇首的輪數(shù)，r越大該節(jié)點(diǎn)被選為簇首的概率也就越大，r為0則表示該節(jié)點(diǎn)上輪剛剛當(dāng)選過簇首，但是只要節(jié)點(diǎn)的剩余能量多，其可以繼續(xù)被選作為簇首。

2)簇的組建:

候選簇首的選舉完成之后，由普通節(jié)點(diǎn)根據(jù)其到候選簇首以和候選簇首到基站的距離來選擇出其可以加入的簇首，然后根據(jù)可加入簇首的剩余能量、鄰居節(jié)點(diǎn)度來確定最終要加入的簇首。其詳細(xì)的步驟如下：

1)候選簇首廣播自己的位置信息、剩余能量、鄰居節(jié)點(diǎn)數(shù)。

2)普通節(jié)點(diǎn)根據(jù)公式(5)計算數(shù)據(jù)由簇首到基站的代價，選擇代價值最小的3個候選簇首加入自己的候選簇首列表。

(5)

其中：dNi_CHj表示節(jié)點(diǎn)Ni到候選簇首CHj的距離，dCHj_BS表示候選簇首CHj到基站的距離。由公式(4)可知，數(shù)據(jù)傳輸所消耗的能量與數(shù)據(jù)的傳輸距離有關(guān)，簇內(nèi)的通信距離一般較小，因此采用自由空間模型，將簇內(nèi)通信代價最小問題轉(zhuǎn)化為節(jié)點(diǎn)到簇首距離的平方值最小問題；簇首到基站的距離相對較遠(yuǎn)，因此采用多路徑衰減模型，將簇首到基站通信代價最小問題轉(zhuǎn)化為簇首到基站距離的四次方的最小化問題。

假設(shè)某個節(jié)點(diǎn)與其周圍的候選簇首的分布如圖2所示，根據(jù)公式(5)計算代價由小到大的順序也是D、A、C、B，因此D、A、C三個候選簇首的信息被加入到該普通節(jié)點(diǎn)候選簇首列表中。

1.2 治療方法 對照組患者采用甲氨蝶呤小劑量分次肌注聯(lián)合米非司酮進(jìn)行治療，甲氨蝶呤劑量：0.4 mg·kg-1·d-1，5 d為一個療程，米非司酮劑量100 mg，2次/d，連續(xù)服用3 d，劑量600 mg。觀察組給予患者一次性甲氨蝶呤肌注給藥聯(lián)合米非司酮(100 mg，2次/d)進(jìn)行治療，甲氨蝶呤一次性劑量50 mg/m2，在患者給藥4～7 d，如實(shí)驗(yàn)室檢查血β-hCG下降幅度小于15%或持續(xù)上升，于第7天再次肌注同劑量甲氨蝶呤。

圖2 簇首選擇示意圖

3)普通節(jié)點(diǎn)根據(jù)公式(6)從自己的候選簇首列表中選擇ValueCHj取值最大的簇首作為自己的最終簇首。

(6)

其中：EChj為候選簇首CHj的當(dāng)前剩余能量，Ech_aver為3個候選簇首能量的平均值，剩余能量越多ValueCHj的取值也就越大；NeiCH_Can(j)為候選簇首CHj的鄰居節(jié)點(diǎn)的數(shù)量，Neiaver為3個候選簇首鄰居節(jié)點(diǎn)的平均值。

4)普通節(jié)點(diǎn)加入選定的簇首，當(dāng)所有的普通節(jié)點(diǎn)完成簇首選舉時，未被選中的候選簇首和普通節(jié)點(diǎn)一樣根據(jù)公式(5)與公式(6)選擇簇首并加入。

5)簇的建立完成之后，為避免數(shù)據(jù)沖突，簇首為每一個成員節(jié)點(diǎn)分配TDMA時隙，成員節(jié)點(diǎn)根據(jù)時隙規(guī)則在規(guī)定的時隙與簇首進(jìn)行通信。

其中，在簇首在時隙分配過程中所分配的時隙數(shù)大于簇內(nèi)節(jié)點(diǎn)的數(shù)量，即預(yù)留若干時隙供新加入的節(jié)點(diǎn)的使用；當(dāng)新節(jié)點(diǎn)申請入簇時，不需要等待當(dāng)前簇周期的結(jié)束，也不要重新進(jìn)行時隙的劃分，既增加了網(wǎng)絡(luò)的可擴(kuò)展性，又提高了網(wǎng)絡(luò)的運(yùn)行效率，減少時延，節(jié)約能量。

3.2 簇內(nèi)簇首調(diào)整

在每一輪簇首的選舉以及簇的建立過程中，都需要廣播消息以獲取節(jié)點(diǎn)的信息，為了進(jìn)一步減少能量消耗，本文所提算法采用簇內(nèi)簇首輪換的方式。即當(dāng)網(wǎng)絡(luò)中所有簇首的能量都大于閾值Ea時，不需要在全網(wǎng)范圍內(nèi)重新進(jìn)行簇首的選舉。

在簇內(nèi)數(shù)據(jù)收集的過程中，成員節(jié)點(diǎn)每輪向簇首發(fā)送自己的剩余能量信息，簇首計算自己的剩余能量是否大于簇內(nèi)節(jié)點(diǎn)的平均能量，若大于則繼續(xù)擔(dān)任簇首，若小于根據(jù)簇內(nèi)簇首選舉方法進(jìn)行新簇首的選擇[14]，詳細(xì)步驟如下所示。

(7)

(8)

其中：dij2為第i個簇內(nèi)的第j個簇成員節(jié)點(diǎn)到其他成員節(jié)點(diǎn)距離平方的均值，(xj,yj)為該節(jié)點(diǎn)的位置坐標(biāo)，Mi為第i個簇內(nèi)的成員節(jié)點(diǎn)的個數(shù)，R為節(jié)點(diǎn)的通信距離，Eij表示第i個簇內(nèi)的第j個簇成員節(jié)點(diǎn)的當(dāng)前剩余能量，Ei_aver為簇內(nèi)的平均能量值。由公式(7)(8)可知，剩余能量越多，與簇內(nèi)通信代價越小，其被選為簇首的概率就會越大，該種簇內(nèi)簇首輪換機(jī)制，既減少簇的重建所帶來的能耗，又能保證節(jié)點(diǎn)能耗的均勻，防止個別節(jié)點(diǎn)因能耗過大而死亡。

2)當(dāng)前簇首在簇內(nèi)廣播新簇首消息，并將TDMA時隙規(guī)則以及簇內(nèi)成員的信息發(fā)送給新簇首，完成任務(wù)交接，當(dāng)前簇首作為普通節(jié)點(diǎn)，沿用新簇首的時隙向新簇首發(fā)送數(shù)據(jù)。

3)簇內(nèi)其他成員節(jié)點(diǎn)收到消息后，修改自己所維護(hù)的簇首信息，繼續(xù)進(jìn)行數(shù)據(jù)的采集與發(fā)送。

3.3 網(wǎng)絡(luò)擴(kuò)展

當(dāng)新節(jié)點(diǎn)申請加入網(wǎng)絡(luò)時，首先由新節(jié)點(diǎn)廣播自己的加入請求消息，網(wǎng)絡(luò)中的簇首收到請求消息后將自己的位置信息、簇內(nèi)當(dāng)前負(fù)載、剩余能量發(fā)送給新節(jié)點(diǎn)。新節(jié)點(diǎn)收到各簇首消息后，根據(jù)公式(9)選取Per(j)取值最大的簇首加入。

(9)

其中：dchj為新節(jié)點(diǎn)到簇首CHj的距離，Echj與Lchj分別為簇首CHj的剩余能量與當(dāng)前負(fù)載即當(dāng)前成員節(jié)點(diǎn)的個數(shù)，E0為節(jié)點(diǎn)的初始能量，1/p為網(wǎng)絡(luò)內(nèi)的平均簇成員數(shù)目。

新節(jié)點(diǎn)選定簇首后，向該簇首發(fā)送入網(wǎng)請求，簇首接受請求后，將預(yù)留的時隙分配給新節(jié)點(diǎn)，新節(jié)點(diǎn)正式成為簇成員開始進(jìn)行數(shù)據(jù)的采集與發(fā)送。

4 仿真與分析

采用Python語言中的numpy、pandas庫以及matplotlib庫，對本文算法以及經(jīng)典的LEACH、EEUC等算法在網(wǎng)絡(luò)的生命周期、網(wǎng)絡(luò)能耗以及節(jié)點(diǎn)能量的均衡性進(jìn)行了對比以及可視化分析。

4.1 仿真環(huán)境與參數(shù)設(shè)置

仿真環(huán)境為100個節(jié)點(diǎn)隨機(jī)分布在200*200的區(qū)域內(nèi)，基站坐標(biāo)為(100,200)，每輪簇首的數(shù)量占網(wǎng)絡(luò)中存活節(jié)點(diǎn)的10%(p=0.1)。數(shù)據(jù)傳輸模型采用一階無線模型，其中實(shí)驗(yàn)中涉及到的部分參其他數(shù)取值如表1所示。

表1 實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果分析

圖3為網(wǎng)絡(luò)運(yùn)行到第10輪時節(jié)點(diǎn)的分布情況以及本文算法(AEECA)的成簇情況。由實(shí)驗(yàn)結(jié)果可知，簇首較均勻的分布在網(wǎng)絡(luò)中，并沒有出現(xiàn)簇首“扎堆”或“邊緣化”的情況，負(fù)載相對比較均衡。這主要是因?yàn)樵诖厥椎倪x舉過程中不僅僅考慮到節(jié)點(diǎn)的剩余能量，還綜合考慮了節(jié)點(diǎn)的位置信息、以及節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量，使簇首的數(shù)量與節(jié)點(diǎn)的密度成正比。

圖3 節(jié)點(diǎn)分布情況及成簇情況圖

圖4與圖5分別為本文算法(AEECA)與LEACH算法、EEUC算法就網(wǎng)絡(luò)生命周期指標(biāo)以及網(wǎng)絡(luò)中所有節(jié)點(diǎn)總能量所進(jìn)行的仿真與對比。網(wǎng)絡(luò)生命周期是衡量無線傳感器網(wǎng)絡(luò)質(zhì)量的一個非常重要的指標(biāo)。在本文的仿真實(shí)驗(yàn)中，以網(wǎng)絡(luò)中節(jié)點(diǎn)的存活數(shù)量來表示網(wǎng)網(wǎng)絡(luò)的生命周期。由仿真結(jié)果可知，3種算法的網(wǎng)絡(luò)生命周期從長到短依次為AEECA、EEUC、LEACH。

圖4 網(wǎng)絡(luò)生命周期對比

圖5 能耗對比

與LEACH算法比較，AEECA算法的能耗小的原因主要有以下幾個：

1)在簇首選舉過程中，LEACH算法每輪都要重新選擇簇首，而AEECA采用的是一定條件下簇內(nèi)簇首輪換的方式，節(jié)約了全網(wǎng)范圍內(nèi)進(jìn)行簇首選舉的能耗。

2)在簇的組建過程中，LEACH算法是節(jié)點(diǎn)選擇距離自己近的簇首加入，而AEECA綜合考慮了簇首距離基站的距離，簇首的剩余能量以及節(jié)點(diǎn)密度等因素，不僅可以促進(jìn)節(jié)點(diǎn)間的負(fù)載均衡，還可以減少信息回傳所帶來的能耗。

圖6對3種算法每輪的能耗作了仿真與對比，整體來看每輪能耗隨著網(wǎng)絡(luò)運(yùn)行輪數(shù)的增加而減少，原因是網(wǎng)絡(luò)中的存活的節(jié)點(diǎn)越來越少，另外LEACH算法每輪的能耗都比其他兩種算法高，EEUC各輪的能耗比較均衡，AEECA大部分輪能耗維持在較低水平，小部分輪數(shù)能耗較高，原因是當(dāng)簇內(nèi)平均能耗低于閾值時，需要在全網(wǎng)范圍內(nèi)進(jìn)行簇首選舉，此時能耗則較高，其他輪則是采用簇內(nèi)簇首輪換的方式進(jìn)行的，能耗低于全網(wǎng)簇首選舉。

圖6 每輪能耗對比

綜上所述，本文算法在網(wǎng)絡(luò)分簇階段，根據(jù)節(jié)點(diǎn)的剩余能量來進(jìn)行候選簇首的選舉，可以避免低能量節(jié)點(diǎn)當(dāng)選簇首；在簇首的選舉過程中，節(jié)點(diǎn)根據(jù)數(shù)據(jù)經(jīng)各簇首轉(zhuǎn)發(fā)至基站所經(jīng)過路徑的平方和，來選取轉(zhuǎn)發(fā)代價最小的3個簇首作為自己的候選簇首，可以避免當(dāng)簇首分布較偏的時候，數(shù)據(jù)因距離較遠(yuǎn)而帶來的能耗過大問題。節(jié)點(diǎn)從3個候選簇首中，選取剩余能量大、鄰居節(jié)點(diǎn)多的候選簇首作為自己的最終簇首，既保證了簇首具有較高的能量，又能保證簇首分布在節(jié)點(diǎn)相對集中的區(qū)域[20]。

為了增加網(wǎng)絡(luò)的可擴(kuò)展性，當(dāng)新的就節(jié)點(diǎn)申請加入網(wǎng)絡(luò)時，引入節(jié)點(diǎn)的入網(wǎng)許可值，綜合考慮要加入簇的能量和距離，使得選擇的簇頭節(jié)點(diǎn)對于新入網(wǎng)節(jié)點(diǎn)而言，具有更好的健壯性。另外，基于簇的負(fù)載值的考慮，使得網(wǎng)絡(luò)的負(fù)載分布更均勻。

5 結(jié)束語

本文在分析當(dāng)前分簇算法的基礎(chǔ)上，以減少能耗，增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性為目的，提出了一種可擴(kuò)展的無線傳感器網(wǎng)絡(luò)分簇算法，從網(wǎng)絡(luò)分簇、簇內(nèi)簇首選舉、網(wǎng)絡(luò)擴(kuò)展3個部分對算法進(jìn)行了描述與實(shí)驗(yàn)驗(yàn)證，結(jié)果表明本文所提算法可以較少網(wǎng)絡(luò)能耗、均衡節(jié)點(diǎn)間的負(fù)載，延長網(wǎng)絡(luò)的生命周期。