劉志強， 關乾煜， 王瑞利， 何平基， 張 旭

(內(nèi)蒙古工業(yè)大學 信息工程學院，內(nèi)蒙古 呼和浩特 010080)

0 引 言

由于無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)部署的環(huán)境特殊，網(wǎng)絡中各節(jié)點的能量消耗成為影響整個網(wǎng)絡生命周期的關鍵因素[1]。而硬件條件的限制，使得高效的拓撲路由協(xié)議成為了WSNs領域研究的熱點。根據(jù)網(wǎng)絡的拓撲結(jié)構(gòu)，可以將WSNs劃分為兩種類型的拓撲路由協(xié)議，分別為平面型和層次型[2]。

層次型路由算法低能量自適應聚簇分層(low energy adaptive clustering hierarchy,LEACH)[3]是最早提出分簇概念的層次路由協(xié)議，被視作層次路由協(xié)議中的經(jīng)典。在這一算法中，利用“輪”這一單位來分割網(wǎng)絡生命周期，一輪即重新分簇(建簇階段)到數(shù)據(jù)傳輸(拓撲穩(wěn)定階段)兩個階段的過程。在這種算法中，有效劃分了網(wǎng)絡節(jié)點的角色，高效率分配了不同節(jié)點的任務，其最大的突破在于極大的壓縮了網(wǎng)絡能耗。

但是這種算法的問題主要體現(xiàn)在簇的劃分、簇頭的選取等方面。因此，業(yè)內(nèi)人士紛紛探索LEACH拓撲路由算法的改進策略。LEACH-C(LEACH-centralized)[4]和LEACH-F(LEACH-fixed)[5]這兩種改進算法，同樣沿襲了由建簇階段到數(shù)據(jù)傳輸?shù)耐負浞€(wěn)定階段的過程，在建簇階段便強調(diào)了節(jié)點的能耗問題，節(jié)點會向基站節(jié)點發(fā)送自身的能耗狀況，基站節(jié)點在獲取到基礎數(shù)據(jù)后，會展開模擬退火算法(simulated annealing algorithm)進而得到最優(yōu)的簇頭分配方案，以此方案為指導來進行網(wǎng)絡分簇。相比于LEACH算法，上述兩類算法并未對數(shù)據(jù)傳輸?shù)姆€(wěn)定階段進行出改進，其特殊之處主要體現(xiàn)在應用模擬退火算法來計算各節(jié)點的能耗數(shù)據(jù)，以此實現(xiàn)降低網(wǎng)絡開銷。

Improved-LEACH[6]算法中增設了節(jié)點未當選簇頭的輪數(shù)間隔以及節(jié)點的剩余能量這兩類信息，一次影響節(jié)點成為簇頭的概率，且呈現(xiàn)出明顯的正相關關系。針對此算法展開了仿真實驗，結(jié)果顯示，相比于LEACH算法，第一個節(jié)點死亡時間的提升幅度高達106 %，由此可見，應用此算法能夠有效提升網(wǎng)絡的生命周期。

LEACH-CR[7](low energy adaptive clustering hierarchy-consumption reduction)算法首先明確了分簇數(shù)量，通過設置閾值M(M=節(jié)點數(shù)/分簇數(shù)量/2)來完成邏輯分區(qū)操作。分區(qū)后的每個分簇內(nèi)，簇頭節(jié)點的選擇秉持著能量優(yōu)先的原則，即優(yōu)先選取能量最大的節(jié)點來執(zhí)行與基站節(jié)點通信的任務。因此，簇內(nèi)的網(wǎng)絡能耗得以分擔，整體網(wǎng)絡壽命也會有大幅延長。

由上分析可見，在層次型拓撲路由結(jié)構(gòu)中，簇頭的選擇是延長WSNs生命周期的關鍵，目前簇頭多數(shù)是基于剩余能耗或者隨機數(shù)下選取的，弊端較大。本文在LEACH算法的基礎上，研究簇頭選取機制。

1 以骨干節(jié)點作為簇首的拓撲路由算法

LEACH算法所有節(jié)點都參與到簇頭的選擇中，導致簇頭分布不均勻[8]。另外，簇頭的選取都是各個節(jié)點產(chǎn)生一個隨機數(shù)，當該隨機數(shù)小于指定值時，選作簇頭,一定會出現(xiàn)大于指定值的情況，這時，各個節(jié)點又得產(chǎn)生新的隨機數(shù)，重新進行比較，降低效率，增加了損耗。近年來，很多改進算法都考慮到了能耗問題，但仍存在一些缺陷,不能夠達到更好的能耗均衡的效果。

鑒于這些問題，以及WSNs中的傳感器節(jié)點硬件資源的局限性，提出了一種以骨干節(jié)點充當簇頭的(skeleton nodes acting as cluster head,SNACH)拓撲路由算法，使得簇頭均勻分布以實現(xiàn)網(wǎng)絡能量均衡。

1.1 算法描述

SNACH算法的創(chuàng)新點在于將圖像處理技術中圖形骨架的概念運用到WSNs中，圖形中提取的骨架可以抽象表示出圖形原本的模樣，在WSNs中提取的骨架節(jié)點也能夠反映出原始網(wǎng)絡的結(jié)構(gòu)特征。這些“骨架”上的節(jié)點到邊界的距離基本相等，并大致處于網(wǎng)絡的中軸位置,將該特點應用到WSNs層次路由協(xié)議的簇頭選取中，令這些骨架節(jié)點以及骨架節(jié)點的1～3跳節(jié)點作為簇頭的備選集合，并根據(jù)最優(yōu)簇頭的數(shù)目設定一個步長，使集合中的節(jié)點輪流當選簇頭，這樣能夠使簇頭均勻分布，并均衡了網(wǎng)絡能耗。

1.2 在監(jiān)測區(qū)域內(nèi)提取骨干節(jié)點

1)識別邊界節(jié)點

識別監(jiān)測區(qū)域的邊界節(jié)點，用于準確提取出骨干節(jié)點。本文采用多維標度(multi-dimensional scaling,MDS)分析技術。在網(wǎng)絡中選取任意一個網(wǎng)絡內(nèi)部節(jié)點以及邊界節(jié)點，這兩個節(jié)點通過發(fā)送局部的洪泛消息，從而獲得局部鄰居節(jié)點信息，再根據(jù)這些信息得到鄰居節(jié)點間最小跳數(shù)矩陣，進而通過MDS算法進行維度規(guī)約，得到節(jié)點的虛擬坐標，最終分析出網(wǎng)絡的邊界節(jié)點信息。

2)提取骨干節(jié)點

以圖像G為對象，首先根據(jù)邊界節(jié)點進行計算分析，確定其所有對應的連通分支，所有連通分支就將同屬于一個邊界分支集合C中。假設G中任意兩個節(jié)點及相應的邊界分支，分別用參數(shù)u，v和Ci表示，那么節(jié)點u與v之間的最短路徑長度就可表述為d(u,v)。節(jié)點v與邊界分支C之間的距離用D(v,Ci)表示，對應的節(jié)點v與分支內(nèi)所有節(jié)點最小距離值由D(v,Ci)=min(d(v,w),w∈Ci)進行計算。在圖G中，任一節(jié)點到兩個及以上最近邊界分支的距離相同，則該節(jié)點就將以骨架節(jié)點進行判定。這一結(jié)果的理論依據(jù)可以簡單描述為：若網(wǎng)絡存在多個邊界分支，那么每個骨架節(jié)點所處于的位置不得低于兩條邊界分支的中間，即骨架節(jié)點是不同邊界分支的中間節(jié)點。這一判定的具體原理為：首先定義每個邊界節(jié)點，參數(shù)〈Ci,IDj〉的含義是邊界分支Ci內(nèi)的一個叫IDj的節(jié)點，以此為基礎，所定義的邊界節(jié)點將以自身名字等為洪泛信息向圖G發(fā)送，同時為該信息定義一種計數(shù)器對轉(zhuǎn)發(fā)的次數(shù)進行統(tǒng)計記錄。則所有內(nèi)部節(jié)點所接收和記錄的洪泛信息中計數(shù)器值最小的節(jié)點，其與邊界分支的距離就將作為最短距離。洪泛信息實現(xiàn)了對每個節(jié)點與邊界分支距離的計算和確定。骨干節(jié)點形式化的定義為

對于任一的網(wǎng)絡連接圖而言，G與v分別表示連通圖與圖內(nèi)的任一節(jié)點，若節(jié)點v與G的關系存在以下任意一項，則可將節(jié)點v判定為骨干節(jié)點：

1)若網(wǎng)絡連通圖G中存在不低于兩條的邊界分支(邊界分支用Ci,…,Cj表示)，如果存在D(v,Ci)=…=D(v,Cj)=minD(v,B(G))，即節(jié)點v與上述邊界分支的距離相等且均為最小值；

按照骨干節(jié)點的定義方式，就能夠在簇內(nèi)提取出一定數(shù)量的骨干節(jié)點。這時，就可以將這些骨干節(jié)點作為簇頭節(jié)點。在網(wǎng)絡中，這些簇頭基本處于“中軸”位置，并且至少存在兩個邊界節(jié)點到該點的最短距離相同。

3)擴展骨干節(jié)點

骨干節(jié)點是選舉簇頭的最優(yōu)集合，但考慮到簇頭節(jié)點能量消耗大的問題，在骨架節(jié)點的基礎上對骨架節(jié)點進行擴展，得到一個簇頭的備選集合，稱為骨架節(jié)點網(wǎng)絡帶。對于監(jiān)測區(qū)域內(nèi)傳感器節(jié)點較少的網(wǎng)絡而言，可以直接將骨架節(jié)點3跳以內(nèi)的鄰居節(jié)點作為對原始骨架節(jié)點的擴展，并加入到簇頭的備選集合中。對于節(jié)點較為密集的監(jiān)測區(qū)域而言，就可以經(jīng)擴展得到更多的簇頭備選節(jié)點。首先，找到距離最近的兩個骨架節(jié)點連通分支，從而得到兩個分支的最短路徑，并將路徑上的節(jié)點都作為簇頭備選節(jié)點加入到骨架節(jié)點集合中去，最終得到一條擴展的骨架節(jié)點連通分支，形成一個包含最優(yōu)骨架節(jié)點以及擴展骨架節(jié)點的集合，集合內(nèi)節(jié)點相對于其他節(jié)點而言都位于網(wǎng)絡的中間位置到邊界距離相對平均，是選擇簇頭的最優(yōu)備選集合。

1.3 節(jié)點成簇完成網(wǎng)絡拓撲結(jié)構(gòu)

成簇的過程是一個簇頭廣播公告消息和普通節(jié)點選擇是否加入的雙向過程。首先，當選簇頭的節(jié)點廣播一個包含自己身份信息的消息，這個消息的廣播方式同樣是利用載波偵聽多路訪問(carrier sense multiple access,CSMA)協(xié)議。此時各節(jié)點會接收到很多包含簇頭自身信息的消息，對于普通節(jié)點而言，會選擇接收時信號較強的節(jié)點作為自己的簇頭，并發(fā)送一個包含自身信息的反饋消息，將該節(jié)點入簇的請求告知簇頭。當每個節(jié)點都找到合適的簇頭后，分簇完成。此時簇頭可以根據(jù)簇內(nèi)節(jié)點信息進行時分多址(time division multiple address,TDMA)調(diào)度表的創(chuàng)建，令節(jié)點只在自己所分配的TDMA時隙中發(fā)送數(shù)據(jù)，其他時間處于休眠狀態(tài)，這樣既降低了能耗，又防止了數(shù)據(jù)傳輸沖突。SNACH算法的工作流程如圖1所示。

圖1 SNACH算法流程

1.4 算法步驟

1)在整個監(jiān)測區(qū)域內(nèi)識別邊界節(jié)點，通過邊界節(jié)點信息提取骨干節(jié)點作為簇頭；

2)對骨干節(jié)點進行擴展，得到一個連通性較好的骨干帶網(wǎng)絡作為簇頭的備選集合；

do{

3)對簇頭以及簇頭的備選集合中的各節(jié)點建立能量模型；

4)簇頭廣播一個通告消息，其他節(jié)點通過收到消息的信號強弱來判斷選擇哪一個簇頭，直到每一個節(jié)點都加入到簇中，分簇完成。

}while(簇頭節(jié)點能量過低)。

1.5 算法分析

在拓撲發(fā)現(xiàn)的過程中先提取骨架節(jié)點作為簇頭，這些骨架節(jié)點在監(jiān)測區(qū)域內(nèi)基本處于“中軸”位置，而對骨架節(jié)點進行擴展后的骨架節(jié)點網(wǎng)絡帶也處于整個監(jiān)測區(qū)域的中間位置。在簇內(nèi)的各個節(jié)點都需要將自身的信息發(fā)送給簇頭，再由簇頭發(fā)送給基站。因此，選取一個在物理空間里，位置適當?shù)墓?jié)點作為簇頭，則能夠大大減少節(jié)點發(fā)送自身信息時的傳送距離，減少簇內(nèi)成員節(jié)點與簇頭通信過程中能量的消耗。以此為基礎，在簇頭的備選集合中建立節(jié)點能量模型，當簇頭能量過低時，選取能量相對最高的節(jié)點作為簇頭，在實現(xiàn)了能量均衡的同時，延長了節(jié)點壽命，保證了整個網(wǎng)絡的正常運行。

2 OMNeT++仿真實驗

2.1 仿真環(huán)境

搭建OMNeT++5.0仿真平臺，編寫NED網(wǎng)絡模塊以及消息文件，并通過C++編程語言實現(xiàn)對應模塊的邏輯結(jié)構(gòu)，最后在omnetpp.ini文件中編寫相應的網(wǎng)絡設置參數(shù)。其中，定義了200個節(jié)點在邊界為200 m×200 m的區(qū)域中進行1 000輪仿真測試。TDMA時序表幀設為5，則簇頭節(jié)點和BS節(jié)點進行5次通信后，網(wǎng)絡重新進行分簇。另外，網(wǎng)絡中節(jié)點的分布是通過隨機數(shù)的生成而實現(xiàn)的，但OMNeT++中為了保證每次仿真的可重復性，在定義網(wǎng)絡拓撲的NED文件中，沒有設置隨機數(shù)種子的函數(shù)，要避免偽隨機數(shù)的情況，就需要在omnetpp.ini文件中手動設置隨機數(shù)種子。如下述代碼所述，設置了兩個隨機數(shù)種子，分別為13和9

num-rngs=2，seed-0-mt=13，seed-1-mt=9

2.2 仿真結(jié)果

如圖2所示，分別為LEACH算法和SNACH算法在第5輪時簇頭的分布情況，可以看出在LEACH算法中，3個簇頭節(jié)點承擔了網(wǎng)絡中大部分節(jié)點的數(shù)據(jù)收集及傳輸任務，而另3個簇頭節(jié)點則“集中”在了一起，只承擔了一小部分的節(jié)點數(shù)據(jù)收集及傳輸任務，簇頭節(jié)點分布十分不均勻。而SNACH算法可以看出處于骨干節(jié)點網(wǎng)絡帶上的簇頭節(jié)點分布十分均勻，6個簇頭節(jié)點分擔了網(wǎng)絡中的數(shù)據(jù)收集及傳輸任務，使得網(wǎng)絡中能耗更加均衡。

圖2 LEACH和SNACH算法第5輪拓撲對比

如圖3所示，分別是LEACH算法和SNACH算法在第454輪時的拓撲情況，實驗將死亡節(jié)點標記為黑色，可以看出，此時LEACH算法網(wǎng)絡中已有50 %以上的節(jié)點死亡，并且隨機產(chǎn)生的6個簇頭節(jié)點都集中在了網(wǎng)絡的上半部分。而SNACH算法在454輪時，只有一個節(jié)點死亡。

圖3 LEACH和SNACH算法第454輪拓撲對比

如圖4所示，BS處于不同位置時，仿真網(wǎng)絡存活節(jié)點進行了對比。

圖4 1000輪仿真網(wǎng)絡存活節(jié)點對比

BS節(jié)點坐標為(100,100)時，SNACH算法與LEACH算法進行了1 000輪的仿真實驗?？梢钥闯?，LEACH算法在第152輪時開始出現(xiàn)節(jié)點死亡的現(xiàn)象，在第445輪時網(wǎng)絡中50 %的節(jié)點已經(jīng)死亡，從第645輪開始，剩余節(jié)點數(shù)驟降，又經(jīng)過4輪運行之后，剩余節(jié)點穩(wěn)定在3個直到1 000輪仿真結(jié)束。反觀SNACH算法，運行到第452輪才有節(jié)點開始死亡，之后剩余節(jié)點一直均勻減少，直到1 000輪仿真結(jié)束時，仍有28個節(jié)點存活。SNACH算法的網(wǎng)絡生存周期遠遠高于LEACH算法，網(wǎng)絡中節(jié)點開始死亡的時間比LEACH算法多197 %。BS節(jié)點坐標為(0,0)時，SNACH算法與LEACH算法進行了1 000輪的仿真實驗?？梢钥闯?，LEACH算法和SNACH算法分別在第89輪和第286輪時開始出現(xiàn)節(jié)點死亡的現(xiàn)象，網(wǎng)絡中節(jié)點開始死亡的時間SNACH算法比LEACH算法多221%。BS節(jié)點坐標為(250,100)時，同樣SNACH算法與LEACH算法進行了1 000輪的仿真實驗。可以看出LEACH算法和SNACH算法分別在第95輪和第299輪時開始出現(xiàn)節(jié)點死亡的現(xiàn)象，網(wǎng)絡中節(jié)點開始死亡的時間SNACH算法比LEACH算法多214 %。

3 結(jié)束語

本文在整個網(wǎng)絡中提取骨干節(jié)點并進行擴展，得到一個簇頭的備選集合，其核心為利用集合中的節(jié)點輪替充當簇頭。其優(yōu)點在于將簇頭節(jié)點均勻的分布在網(wǎng)絡中，降低了簇頭的“壓力”，減小了節(jié)點能耗，從而延長了整個網(wǎng)絡的壽命。在后續(xù)研究中，本算法還將進一步完善。