基于多跳中繼轉發的簇頭拓撲維護算法研究

初肇群

(大連國際機場集團有限公司 遼寧大連 116000)

無線傳感器網絡節點間的通信耗能，在傳感器所有耗能中占比最大，是對整個無線傳感器網絡進行降低耗能的關鍵性因素。在層次型拓撲結構的傳感器網絡內，簇頭不單單具備信息轉發功能，同時還具備信息中繼轉發功能，從能耗方面來說，相較于正常節點來說，電能損耗要多出不少。在實際應用過程中，簇頭與匯聚節點，兩者之間的數據傳輸與接收，通常狀態下，憑借簇頭之間的數據實施中繼轉發工作，絕大多數能耗也是在簇頭節點和匯聚節點之間的通信。除此之外，假設無線傳感器簇頭在實施數據轉發任務時，存在大于等于兩個節點同時接收的情況，轉發數據會產生冗余的現象，以至于造成能耗增加，同時，這個范圍內的信道競爭也會出現一定程度上的沖突，從而讓能耗進一步提升。基于此，通過一定的拓撲控制方法，能夠讓節點在實施數據傳輸任務過程中，找到唯一的下一跳節點，能夠科學合理地減少數據冗余以及信道競爭，所產生的能耗增加的情況，從而在一定程度上增加網絡的生命周期。假設可以在源數據簇頭之間和匯聚節點搭建出一條能耗較少鏈路，就能夠有效降低簇頭的能耗。而且通過強制性地選擇能耗較低鏈路，既能夠將信息數據傳輸至匯聚節點，又能夠將能耗有效減少。

因此，如何科學合理地降低并減少簇頭的能耗，以及如何維護簇頭的拓撲結構是該文對無線傳感器網絡的層次拓撲控制研究的核心。與匯聚節點之間的間隔范圍模型以及信息中繼轉發的能耗模型，找到簇頭及匯聚節點在進行信息傳輸任務時的最佳跳數，讓節點之間的消耗進一步減少，以達到減少能耗目的。該文就提出了一種基于多跳中繼轉發的拓撲維護算法，試著根據源簇頭節點之后，基于距離和節點的剩余能量選擇合適的簇頭節點，建立源數據簇頭節點和匯聚節點間的最佳鏈路，實現周期性的簇頭拓撲維護。

1 基于距離的節點能耗模型

無線傳感器網絡拓撲控制的最終設計目標，就是要充分、科學、有效地保障數據傳輸的有效性與可靠性。簇頭是進行數據轉發的核心，且會頻繁地進行工作，以至于出現能耗過大，能量非常容易消耗殆盡的情況。

假設節點轉發1Byte的數據到距離節點d，能夠說明網絡節點傳輸數據的能耗是：

節點接收1Byte數據的能耗是：

在上述式中，Eee位傳遞以及接收電路的電能耗損；ε為發送放大電路的電能耗損；α為路徑損失指數。假設在進行數據轉發時，傳輸距離低于某個閥值，則α=12，功率放大損耗使用自由空間模型，ε=εfs。假設轉發距離≥某個閥值時，α=4，功率放大損耗使用多路徑衰減模型，ε=εamp。

單跳通信在一般情況下是說：不會憑借其他節點實施信息的中繼轉發，而是直接與目標節點實施信息傳輸，比如：我們經常見到的蜂窩移動通信（GSM），也可以稱為“直接通信”；多跳通信通常來說，需要憑借其他節點進行數據中轉至目標節點，也就是我們常說的“間接通信”，間接通信普遍應用于自組織的、無設備基礎的通信網絡[1]。在無線傳感器網絡中，單跳通信傳輸中，節點轉發Byte 數據所耗費的能量是Ext，路徑損失指數在一般情況下是最高的，即α=4。在多跳通信的過程中，節點傳輸Byte 數據所需要的能耗，如下式：E=Etx+∑(Erx+Etx)，路徑損失指數一般狀態下能夠用式（2）進行表示。

假如，從一個單獨的簇頭節點，到SINK之間的傳輸距離，用D來進行表示，數據通過n跳的節點，進行數據轉發，到第i跳的傳輸距離，可以用di進行表示，則把1比特單位的數據，從簇頭節點傳輸至SINK節點的全部能量耗損，能夠用下式進行表示：

對上式求導，E′(n)=0，E(n)取最小值，得出：

能夠得到最優跳數：

所以，能量消耗最小的平均每一跳的傳輸距離為：

數據轉發的運作原理，是作用于通信電能耗損的關鍵性成因，通過計算全部的傳輸與數據傳輸能耗之間的聯系，能夠計算出最好、最優秀的中繼跳數，可以通過式（4）～式（6）進行表示，每一跳的最好的數據傳輸距離可以通過式（4）～式（7）進行表示，因此，上述計算公式，為處理數據多跳中繼轉發運作原理提供了科學合理的模型基礎[2]。

2 數據多跳中繼轉發的簇頭維護算法

從傳感器大范圍使用的角度下進行分析，因簇頭和匯聚節點兩者之間的數據傳輸距離在大多數情況下會較長，故兩者之間一般情況下會使用多跳通信之法，這樣一來，能夠在一定程度上降低能耗。不過，使用這種辦法會出現能耗非常不平衡的狀況，從距離上進行分析：和匯聚節點之間距離較近的簇頭，經常會出現負載過重情況，以至于造成能耗大幅度增加，從而造成網絡生命周期縮短的情況，這種情況稱為“熱區”問題[3]。

綜上所述，在進行無線傳感器網絡拓撲算法設計時，需要優先考慮系統的能耗問題，把科學、合理降低使用能耗以及能量使用的有效性當作核心因素。

2.1 算法的設計

在對節點能量模型進行仔細認真的調查研究之后，獲取到基于傳輸距離長短的模型。且認定，兩個網絡節點之間的距離，恰好是能耗最低的單條最優秀最有效的轉發距離是dopt，則能夠把簇頭與匯聚節點通信傳輸的所耗費的能量減到最少。基于此，能夠在簇頭節點進行數據傳輸時，通知下一簇內的節點按照其如今所剩的能量多少以及最短的傳輸距離，選舉出新的簇頭，公式如下。

按照節點i的權數w的值，會不會在如今簇內的節點中最接近1，來確定其能不能當選當前簇的新簇頭。

2.2 算法的實現

層次型結構是使用分簇算法把網絡節點進行劃分，分別劃分成簇頭以及簇成員。簇頭組成一個骨干網，整個網絡的信息傳輸，主要是憑借簇頭來進行傳輸的。分簇內的數據主要是通過簇節點進行搜集，搜集到的數據發送給簇頭，簇頭把搜集到的數據實施處理、融合，最后簇頭將處理好的數據進行轉發[4]。

按照權數w，基于多跳中繼轉發的簇頭維護算法描述具體如下。

2.2.1 拓撲初始化

按照原來的算法實施分簇操作，首先選出符合條件的簇頭，下一步，正常節點傳輸數據到簇內，全部的節點分別劃分成為正常、簇頭以及匯聚節點。下一步進行數據的搜集，所搜集的數據包含如今節點的能量多少，簇頭與匯聚節點兩者之間距離的大小。

2.2.2 重新選舉簇頭

當探測到簇頭節點無法工作時，按照權數：w，調查研究SINK節點的傳輸距離長短，以及節點自己剩下能量的多少，重新選出新的簇頭。按照權數：w，從頭開始選舉出新的簇頭，進行信息傳輸任務，同時要考慮到最低能耗以及均衡，重新建立拓撲結構。

2.2.3 拓撲通知

在簇頭重新選舉完成之后，簇內節點傳輸信息和新簇頭之間實施通信，取得確認通知，同時按照和簇頭之間的距離，以獲取到和節點之間的傳輸距離大小，下一步進行功率的調整，從而獲取到合理有效的通信距離大小以及最少的能耗[5]。

2.2.4 拓撲維護

根據此類拓撲算法，分階段、分批次地對簇頭節點重新實施選舉工作，或者對通信鏈接斷開的簇頭實施拓撲維護操作，從而獲得中繼轉發最有效、最合理的轉發距離。

3 模擬實驗分析

通過MATLAB 仿真程序對多跳中繼轉發的簇頭拓撲維護算法實施仿真研究。為避免過于繁瑣，拓撲在開始的設計過程的算法，通常狀態下采取的是LEACH 算法，最終，此類算法在電能耗損方面以及網絡生命周期方面，與LEACH算法在各種應用模擬環境下實施比較[6]。

3.1 實驗場景設計

考慮到LEACH算法的多種模擬應用環境，該次實驗場景的設計采用兩種模擬應用環境，來實施仿真性實驗。

第一種是在100 m×100 m的范圍內放置100個節點，Sink 節點的坐標在（50,50）；第二種是在800 m×800 m 的范圍內放置800 個節點，Sink 節點的坐標在(400,400)，此外，其他參數如表1仿真模擬參數所示。

為了讓實驗的最終結果更加科學合理，在參數的設置方面，和LEACH 基本一樣。網絡假設如下：（1）Sink 節點方位不變，并且只存在單個Sink 節點；（2）發射功率能夠進行調整；節點在部署完成以后靜止；（3）節點本身具備相關的計算能力，能夠計算出dopt；（4）簇內的任意兩個節點之間的通信是相互的，簇與簇兩者之間的數據傳輸與接收，只可以通過簇頭來實施。不過，Sink能夠與簇頭實施直接的數據傳輸與接收，相較于傳輸距離比較長地簇頭，能夠通過多跳轉發實施數據交互；（5）權重因子α=0.4，β=0.6。

3.2 結果的實現

分別對兩個模擬環境進行網絡節點的隨機撒布，并形成簇，劃分為簇頭節點和普通節點，形成的voronoi圖。不論是在范圍較廣的區域，還是范圍較小的區域，隨機形成的簇頭都很不平均，簇頭與Sink節點的數據交互都顯得非常的不便。根據圖1和圖2可知，分別是兩個模擬環境下的節點平均耗能情況的展示。從圖1能夠發現，拓撲維護算法在使用能耗方面，與LEACH相比要低，關鍵性因素是新算法的多跳中繼傳輸，是以最優傳輸距離為前提實施傳輸的。

圖1 100 m×100 m的仿真場景下節點死亡情況

圖2 800 m×800 m的仿真場景下節點死亡情況

除此之外，由圖1 和圖2 可知，另外一種情況也能夠說明新算法比LEACH 在控制電能損耗方面要好。新算法在小面積的仿真場景下，多跳中繼轉發的特點沒有辦法得到全面的施展，通過圖1能夠了解到，新算法在開始的時候，死亡的節點數量的時間，相較LEACH 要快要多，不過，從一起死亡的角度上進行觀察，了解到LEACH的節點死亡個數較于新算法要多出不少和快出不少。基于此，新算法的能耗特性在較大的模擬環境下能夠更好地體現出來。

權重因子α，β不同取值情況時，節點死亡情況。選舉簇頭時節點所剩余能量，在權數中占比越高，說明節點的平均能量保持得越優秀，因此可以清楚地了解到：選舉簇頭時的能量，相較于減少整個網絡的能量消耗是一個極為關鍵的因素。不過隨著模擬仿真環境方位的逐步拓展，節點數量的迅速提升，在簇頭選舉公式內，所剩余能量權數越大，節點所剩余的平均能量也就越高。

4 結語

針對拓撲維護的簇頭重新選舉，提出了一種以能量和節點距離綜合考慮的數據中繼轉發的簇頭維護算法。仿真證明該算法有效節約了節點工作耗能，達到了節點能量均衡的效果，優化了網絡拓撲結構，延長了網絡生命期。