羅力源，施偉斌

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

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，簡稱WSN）是一種分布式傳感網(wǎng)，它由大量的節(jié)點組成，這些節(jié)點中又包含有大量的傳感器、數(shù)據(jù)處理單元和數(shù)據(jù)模塊，圖1是無線傳感器網(wǎng)絡(luò)典型的體系結(jié)構(gòu)圖[1]。其中，傳感器之間的通信通過無線的方式進行，而節(jié)點之間的通信則是通過自組織的方式構(gòu)成網(wǎng)絡(luò)來實現(xiàn)。這些節(jié)點能夠?qū)崿F(xiàn)的功能主要包括傳感、對收到信號的處理和實現(xiàn)無線通信等。它們是信息包的發(fā)起者，同時也是信息包的轉(zhuǎn)發(fā)者，通過網(wǎng)絡(luò)自組織和多跳路由，將數(shù)據(jù)向網(wǎng)關(guān)發(fā)送[2]。

圖1 無線傳感器網(wǎng)絡(luò)通信體系結(jié)構(gòu)圖Fig.1 Wireless sensor network communication architecture diagram

WSNs網(wǎng)絡(luò)的節(jié)點以Ad-Hoc方式進行通信，每個節(jié)點都可以充當路由的角色，并且每個節(jié)點都具備動態(tài)搜索、定位和回復(fù)連接的能力。WSNs節(jié)點在通信過程中可能會受到外因或內(nèi)因?qū)е孪o法完整接收[3]。其中，外因一般有窄帶干擾、同頻干擾和鄰道干擾等，內(nèi)因則有信道競爭失敗和消息緩存溢出等。這些干擾會導(dǎo)致原消息數(shù)據(jù)傳輸?shù)牟煌暾騻鬏斦`碼增多，同時這些干擾所導(dǎo)致的丟包都影響著兩個節(jié)點之間的鏈路健壯性。當兩個節(jié)點之間的發(fā)生連續(xù)丟包時，它們之間的通信可靠性會持續(xù)下降，這時無論發(fā)送任何數(shù)據(jù)都不能確保其接收的可靠性；同時在這種非可靠的情況下，信源節(jié)點單播的數(shù)據(jù)對于信宿節(jié)點來說也并非絕對可達，所以應(yīng)盡量減少非可靠兩節(jié)點間的數(shù)據(jù)收發(fā)，以減少WSNs節(jié)點的能耗，最終達到延長網(wǎng)絡(luò)生存時間的目的[4]。

1 多跳低功耗自適應(yīng)分簇協(xié)議（MHLEACH）

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

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

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

2 基于鏈路質(zhì)量估計的能量均衡路由協(xié)議

（1）基本原理

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

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

ELQECHE 協(xié)議將評估鏈路質(zhì)量的計算公式定義為：

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

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

本 ELQECHE 轉(zhuǎn)發(fā)協(xié)議使用的鏈路估計模塊

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

圖3 基于PRR統(tǒng)計的鏈路估計器Fig.3 Link estimator based on PRR statistics

（2）分簇路由算法ELQECHE

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

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

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

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

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

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

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

當節(jié)點對接收自鄰居的路由消息（RoutePacket）或單播數(shù)據(jù)消息（MHMessa ge）分別進行消息處理后，這些消息還會經(jīng)由LnqulityP模塊最終計算出該鄰居節(jié)點的鏈路質(zhì)量。經(jīng)LnqulityP鏈路質(zhì)量估計改進的選擇轉(zhuǎn)發(fā)簇首的流程如圖6。

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

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

圖6 ELQECHE算法的轉(zhuǎn)發(fā)簇首選擇流程Fig.6 Cluster selection process based on ELQECHE algorithm

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

3 實驗結(jié)果與分析

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

圖8分別反應(yīng)了采用MHLeach和ELQECHE協(xié)議時全網(wǎng)各節(jié)點的死亡時間?？煽吹紼LQECHE協(xié)議運行 13個小時后才出現(xiàn)死亡節(jié)。對比MHLeach的實驗結(jié)果，可知用ELQECHE協(xié)議（圖8左）比用MHLeach協(xié)議（圖8右）晚出現(xiàn)首個死亡節(jié)點8個小時左右，延長約160%的網(wǎng)絡(luò)生存時間。這充分證明ELQECHE算法能夠進一步地延長原MHLeach協(xié)議網(wǎng)絡(luò)生存時間的能力。

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

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

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

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

4 結(jié)束語

本問介紹了基于MHLeach協(xié)議改進的ELQECHE算法，實驗表明ELQECHE協(xié)議能夠根據(jù)網(wǎng)絡(luò)中節(jié)點的數(shù)目和位置順利成簇，簇首能夠接收成員節(jié)點發(fā)送的數(shù)據(jù)，基站也能夠接收各簇首發(fā)送的數(shù)據(jù)。網(wǎng)絡(luò)中節(jié)點能夠按照算法要求選擇各自的下一跳節(jié)點，實現(xiàn)簇間數(shù)據(jù)轉(zhuǎn)發(fā)。

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