一種改進(jìn)的分簇路由算法

羅力源，施偉斌

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

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，簡稱WSN）是一種分布式傳感網(wǎng)，它由大量的節(jié)點(diǎn)組成，這些節(jié)點(diǎn)中又包含有大量的傳感器、數(shù)據(jù)處理單元和數(shù)據(jù)模塊，圖1是無線傳感器網(wǎng)絡(luò)典型的體系結(jié)構(gòu)圖[1]。其中，傳感器之間的通信通過無線的方式進(jìn)行，而節(jié)點(diǎn)之間的通信則是通過自組織的方式構(gòu)成網(wǎng)絡(luò)來實(shí)現(xiàn)。這些節(jié)點(diǎn)能夠?qū)崿F(xiàn)的功能主要包括傳感、對收到信號(hào)的處理和實(shí)現(xiàn)無線通信等。它們是信息包的發(fā)起者，同時(shí)也是信息包的轉(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é)點(diǎn)以Ad-Hoc方式進(jìn)行通信，每個(gè)節(jié)點(diǎn)都可以充當(dāng)路由的角色，并且每個(gè)節(jié)點(diǎn)都具備動(dòng)態(tài)搜索、定位和回復(fù)連接的能力。WSNs節(jié)點(diǎn)在通信過程中可能會(huì)受到外因或內(nèi)因?qū)е孪o法完整接收[3]。其中，外因一般有窄帶干擾、同頻干擾和鄰道干擾等，內(nèi)因則有信道競爭失敗和消息緩存溢出等。這些干擾會(huì)導(dǎo)致原消息數(shù)據(jù)傳輸?shù)牟煌暾騻鬏斦`碼增多，同時(shí)這些干擾所導(dǎo)致的丟包都影響著兩個(gè)節(jié)點(diǎn)之間的鏈路健壯性。當(dāng)兩個(gè)節(jié)點(diǎn)之間的發(fā)生連續(xù)丟包時(shí)，它們之間的通信可靠性會(huì)持續(xù)下降，這時(shí)無論發(fā)送任何數(shù)據(jù)都不能確保其接收的可靠性；同時(shí)在這種非可靠的情況下，信源節(jié)點(diǎn)單播的數(shù)據(jù)對于信宿節(jié)點(diǎn)來說也并非絕對可達(dá)，所以應(yīng)盡量減少非可靠兩節(jié)點(diǎn)間的數(shù)據(jù)收發(fā)，以減少WSNs節(jié)點(diǎn)的能耗，最終達(dá)到延長網(wǎng)絡(luò)生存時(shí)間的目的[4]。

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

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

圖2 典型的多跳自適應(yīng)分簇協(xié)議拓?fù)溲菔緢DFig.2 Topology of a typical multi-hop adaptive clustering protocol

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

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

（1）基本原理

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

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

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

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

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

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

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

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

（2）分簇路由算法ELQECHE

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖8 MHLeach（左）和ELQECHE（右）節(jié)點(diǎn)生存時(shí)間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é)議改進(jìn)的ELQECHE算法，實(shí)驗(yàn)表明ELQECHE協(xié)議能夠根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目和位置順利成簇，簇首能夠接收成員節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，基站也能夠接收各簇首發(fā)送的數(shù)據(jù)。網(wǎng)絡(luò)中節(jié)點(diǎn)能夠按照算法要求選擇各自的下一跳節(jié)點(diǎn)，實(shí)現(xiàn)簇間數(shù)據(jù)轉(zhuǎn)發(fā)。

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