一種改進的分簇路由算法

羅力源，施偉斌

(上海理工大學 光電信息與計算機工程學院，上海 200093)

0 引言

無線傳感器網絡（Wireless Sensor Networks，簡稱WSN）是一種分布式傳感網，它由大量的節點組成，這些節點中又包含有大量的傳感器、數據處理單元和數據模塊，圖1是無線傳感器網絡典型的體系結構圖[1]。其中，傳感器之間的通信通過無線的方式進行，而節點之間的通信則是通過自組織的方式構成網絡來實現。這些節點能夠實現的功能主要包括傳感、對收到信號的處理和實現無線通信等。它們是信息包的發起者，同時也是信息包的轉發者，通過網絡自組織和多跳路由，將數據向網關發送[2]。

圖1 無線傳感器網絡通信體系結構圖Fig.1 Wireless sensor network communication architecture diagram

WSNs網絡的節點以Ad-Hoc方式進行通信，每個節點都可以充當路由的角色，并且每個節點都具備動態搜索、定位和回復連接的能力。WSNs節點在通信過程中可能會受到外因或內因導致消息無法完整接收[3]。其中，外因一般有窄帶干擾、同頻干擾和鄰道干擾等，內因則有信道競爭失敗和消息緩存溢出等。這些干擾會導致原消息數據傳輸的不完整或傳輸誤碼增多，同時這些干擾所導致的丟包都影響著兩個節點之間的鏈路健壯性。當兩個節點之間的發生連續丟包時，它們之間的通信可靠性會持續下降，這時無論發送任何數據都不能確保其接收的可靠性；同時在這種非可靠的情況下，信源節點單播的數據對于信宿節點來說也并非絕對可達，所以應盡量減少非可靠兩節點間的數據收發，以減少WSNs節點的能耗，最終達到延長網絡生存時間的目的[4]。

1 多跳低功耗自適應分簇協議（MHLEACH）

為將 WSNs 中節點采集到的數據轉發到數據處理節點，一個有效的方法就是將網絡中的節點按照某種特性分成多簇網絡結構。在各簇內，則再按一定規則選舉出簇首（Cluster Head）節點，讓它們維護一些必要的路由信息[5]。除簇首節點外，一般葉子（Leaf）節點的功能比較簡單，只需將數據消息發送至簇首，經由簇首來轉發這些數據消息，典型的簇樹形拓撲結構如圖2。

圖2 典型的多跳自適應分簇協議拓撲演示圖Fig.2 Topology of a typical multi-hop adaptive clustering protocol

從圖中可以看到有5個簇首，其中除A、B、C三個葉子節點單跳地向網關（BS）發送數據外，還有D、E 節點以多跳轉發的方式向網關（BS）傳遞信息。概括地說，葉子節點對于簇首節點的拓撲是星形網絡結構，而簇首對于簇首之間則類似于一種樹形網絡結構，采用這種拓撲結構并實現自組網的多跳分簇協議我們稱之為多跳低功耗自適應分簇協議（MHLEACH）。然而大量實驗表明，MHLEACH路由協議讓深度較深的節點在其鄰居表中找出一深度最淺的簇首來作為轉發節點，但這可能并不能搜索到一條到網關過程中最小通信代價的路徑[6]。這是因為一個處在較深處的葉子或簇首節點的鄰居表中可能會找到多個簇首在深度上都一樣最淺的節點，這時葉子節點要如何選擇簇首作為轉發就成為一個值得考慮的問題，一旦選擇的多跳路徑會加重通信的代價，則會對網絡可靠性造成致命的影響[7]。另外，僅憑深度來作為選擇轉發節點的方法也會隨機地使部分些簇首負載過大，導致單一節點能量消耗過快，無法達到網絡可生存時間的最優化。

2 基于鏈路質量估計的能量均衡路由協議

（1）基本原理

本文的主要內容，就是設計了基于能量均衡與鏈路質量估計的轉發簇首選擇算法（Energy with Link Quality Cluster Head Election, ELQECHE）。轉發簇首的選擇將同時參考葉子和簇首節點的信號強度與鏈路質量估計來作為評價通信可靠性的指標之一[8]。

鏈路質量評估是獲得穩定路由選擇的一種重要參照，所以研究并充分利用動態網絡中鏈路的連接狀態能夠有效維持整個網絡的可靠性，同時還能均衡到整個網絡的能耗[9]。

ELQECHE 協議將評估鏈路質量的計算公式定義為：

上式中， Inqulityi [ k]代表節點i在第k個周期時所算出的鏈路質量，而ALPHA是協議賦予的一個固定權重值，最后的PRR代表消息數據從信源到信宿被成功接收的消息接收率[10]。消息接收率一般被定義為接收消息與全部消息之比，即：

觀察式（1），鏈路質量Inqulity顯然是隨著消息接收率的變化而變化的，且還與消息接收率成正比，所以式（1）能有效地反映出節點與鄰居之間的鏈路“健壯性”，即傳輸可靠性。

本 ELQECHE 轉發協議使用的鏈路估計模塊

是LnqulityP，本模塊是在模仿4 bit鏈路估計器的功能上簡化設計而成，僅保留針對網絡層的 Compare和 Pin位的部分功能，并最后計算出鏈路質量的功能。鏈路質量的計算過程主要依賴于統計數據包和路由包的接收成功率（PRR）。

圖3 基于PRR統計的鏈路估計器Fig.3 Link estimator based on PRR statistics

（2）分簇路由算法ELQECHE

式（1）能有效地評估當前節點到鄰居的鏈路質量，但為得到式（2）中消息成功接收的數量（Received Packets），節點必須在每次接收到消息時把數據包或路由中的序列號seqNo存進另一個全局表結構中[11]，稱為接收率估計表（PRREstTable），其結構如下圖。

圖4 ELQECHE的接收率估計表Fig.4 ELQECHE reception rate estimation table

在右圖中，nodeId是鄰居節點地址，rcvcnt和failcnt分別是接收成功的和接收失敗的消息數量；lastseqMH和lastseqRP則分別代表最近一次收到數據包或路由包時，記錄數據包或路由包中所攜帶的序列號。

每當節點接收到MHMessage或RoutePacket消息后，鏈路估計器會根據消息的類型把接收率估計表（PPREstTable）中的lastseqMH或lastseqRP同接收消息中的seqNo比較；若它們連續遞增則rcvcnt加1，否則failcnt加1。則式（2）消息接收率PRR的計算公式應改為：

將式（3）應用到式（1）中，其實測的計算結果使鏈路質量的變化區間在[0,241]內，其值越高代表鏈路質量越高，相對應的通信有效性也就越好[12]。將該Inqulityi保 存到鄰居表內對應節點中，則每當節點需要查找轉發路由時，鄰居表中保存的鏈路質量就可作為是否選為轉發簇首節點評判標準之一。

本文中，ELQECHE算法在消息接收后對消息的處理過程如圖5所示。

圖5 ELQECHE的消息接收過程Fig.5 ELQECHE message receiving process

當節點對接收自鄰居的路由消息（RoutePacket）或單播數據消息（MHMessa ge）分別進行消息處理后，這些消息還會經由LnqulityP模塊最終計算出該鄰居節點的鏈路質量。經LnqulityP鏈路質量估計改進的選擇轉發簇首的流程如圖6。

對于鄰居表內有簇首的情況，首先遍歷到鄰居表中簇首節點中的最小深度 minHeadDepth 和葉子節點中的最小深度minLeafDepth。然后根據鄰居表內是否存在簇首來決定是通過選擇簇首來成為轉發簇首還是通過篩選葉子來成為臨時簇首。

若鄰居表內有簇首，則首先篩選出其中深度為minHeadDepth的簇首集合 minH，其次繼續按條件遍歷 minH集合找出滿足信號強度等級>4且電壓>3/4倍平均電壓條件的簇首，然后通過 LnqulityP模塊計算出到滿足上述條件簇首的鏈路質量，最后選擇其中鏈路質量最大的一個簇首來做為上層轉發的簇首節點。

圖6 ELQECHE算法的轉發簇首選擇流程Fig.6 Cluster selection process based on ELQECHE algorithm

但若是鄰居表內沒有簇首或路由查找次數超過限制時，則只能通過請求葉子成為簇首。首先篩選出其中深度為minLeafDepth的葉子節點集合minL，其次篩選出minL集合中滿足信號強度等級>4且電壓>3/4倍平均電壓條件的葉子，然后通過LnqulityP模塊計算出到滿足上述條件葉子的鏈路質量，最后在其中找到一個鏈路質量最大的葉子節點為將被請求成為簇首的對象。

3 實驗結果與分析

MHLeach和ELQECHE路由協議的平均電壓走勢如圖7所示，兩種協議的網絡初始平均電壓均為2.65 V，節點的平均電壓在網絡運行過程中逐漸遞減。當網絡總運行大約 23小時后，MHLeach網絡的節點會全部消亡；但對于ELQECHE協議，則需要運行大于25小時的時間，才能使節點全部消亡。

圖8分別反應了采用MHLeach和ELQECHE協議時全網各節點的死亡時間。可看到ELQECHE協議運行 13個小時后才出現死亡節。對比MHLeach的實驗結果，可知用ELQECHE協議（圖8左）比用MHLeach協議（圖8右）晚出現首個死亡節點8個小時左右，延長約160%的網絡生存時間。這充分證明ELQECHE算法能夠進一步地延長原MHLeach協議網絡生存時間的能力。

圖7 電壓平均走勢圖Fig.7 Average voltage chart

圖8 MHLeach（左）和ELQECHE（右）節點生存時間Fig.8 MHLeach (left) and ELQECHE(right) node lifetime

圖9 代表MHLeach和ELQECHE協議數據包總傳輸數據量（單位/byte）。從圖中可以看出ELQECHE協議在數據發送總量上較 MHLeach協議增加83.92%。說明傳輸可靠性的提升也直接提升可發送數據的總量。

圖9 MHLeach（左）和ELQECHE（右）傳輸數據總量Fig.9 Total amount of data transmitted by MHLeach (left) and ELQECHE (right)

4 結束語

本問介紹了基于MHLeach協議改進的ELQECHE算法，實驗表明ELQECHE協議能夠根據網絡中節點的數目和位置順利成簇，簇首能夠接收成員節點發送的數據，基站也能夠接收各簇首發送的數據。網絡中節點能夠按照算法要求選擇各自的下一跳節點，實現簇間數據轉發。

通過分析實驗結果可知，ELQECHE協議使網絡生存能力得到提升，較MHLeach協議而言延長約160%左右的生存時間。其二，ELQECHE協議使分簇路由協議的傳輸可靠性得到提升，令丟包數減少29.75%。最后，較均衡的傳輸特性使ELQECHE將原分簇路由協議的發送數據總量提高約83.92%。在下一步的學習中可以在ELQECHE上開展雙向鏈路質量估計的研究以進一步保證該協議的傳輸可靠性。