一種可擴展的WSN節(jié)能分簇算法

王瑩瑩,鄭永愛,王詠梅

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

0 引言

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

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

1 相關工作

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

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

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

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

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

2.1 網(wǎng)絡模型

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

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

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

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

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

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

2.2 節(jié)點能耗模型

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

圖1 一階無線電模型

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

(1)

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

ERx(k)=k·Eelec

(2)

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

(3)

3 算法描述

3.1 網(wǎng)絡分簇

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

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

(4)

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

2)簇的組建:

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

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

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

(5)

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

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

1.2 治療方法 對照組患者采用甲氨蝶呤小劑量分次肌注聯(liá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)進行治療，甲氨蝶呤一次性劑量50 mg/m2，在患者給藥4～7 d，如實驗室檢查血β-hCG下降幅度小于15%或持續(xù)上升，于第7天再次肌注同劑量甲氨蝶呤。

圖2 簇首選擇示意圖

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

(6)

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

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

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

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

3.2 簇內簇首調整

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

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

(7)

(8)

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

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

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

3.3 網(wǎng)絡擴展

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

(9)

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

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

4 仿真與分析

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

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

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

表1 實驗參數(shù)

4.2 實驗結果分析

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

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

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

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

圖5 能耗對比

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

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

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

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

圖6 每輪能耗對比

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

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

5 結束語

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