蘇峰

摘要：傳統(tǒng)的無線傳感器網(wǎng)絡(luò)（WSN）節(jié)點受到供電資源的束縛，能耗問題是網(wǎng)絡(luò)中考慮的關(guān)鍵問題，而面向電能監(jiān)測的無線傳感器網(wǎng)絡(luò)側(cè)重于網(wǎng)絡(luò)的穩(wěn)定性和健壯性。無線傳感器網(wǎng)絡(luò)路由機制的好壞決定了傳輸路徑的優(yōu)劣，直接影響到整個網(wǎng)絡(luò)的能量消耗和通信效率。文章分析了2種典型的分簇路由協(xié)議，詳細闡述了PEGASIS協(xié)議的原理，分析了PEGASIS算法的優(yōu)缺點，指出該算法存在的主要問題：延時問題和單鏈對網(wǎng)絡(luò)的影響。針對該問題提出了PEGASIS的改進算法PEGASIS-I，介紹了該算法的原理和實現(xiàn)過程，并對改進算法進行仿真實驗，得出的結(jié)論在時延和單鏈問題上得到了很大的改善。

關(guān)鍵詞：WSN；電能監(jiān)測；路由協(xié)議；PEGASIS-I

傳統(tǒng)的移動Ad hoc網(wǎng)是以節(jié)點為中心的網(wǎng)絡(luò)，而WSN是以數(shù)據(jù)為中心的網(wǎng)絡(luò)。WSN并不需要維護網(wǎng)絡(luò)中任何2個節(jié)點之間的路由，它僅僅需要維護傳感器節(jié)點與匯聚節(jié)點（Sink）之間的路由。傳感器節(jié)點的資源受到電源和計算能力的限制，節(jié)點數(shù)量較多，采集信息的冗余度較大使得移動自組網(wǎng)（MANET）的許多路由協(xié)議標準無法直接應用到WSN中。在無線傳感器自組織網(wǎng)絡(luò)中，傳感器節(jié)點以多跳的方式傳輸?shù)絊ink點，此過程需要對網(wǎng)絡(luò)的路由機制進行選擇，而路由機制的好壞決定了傳輸路徑的優(yōu)劣，直接影響到整個網(wǎng)絡(luò)的能量消耗和通信效率。

路由協(xié)議的設(shè)計要綜合考慮多種性能指標。無論是平面路由還是分簇路由，多數(shù)路由協(xié)議通常只考慮能量約束。傳統(tǒng)的無線傳感器網(wǎng)絡(luò)采用電池供電，節(jié)能是無線傳感器網(wǎng)絡(luò)的一個關(guān)鍵問題，本系統(tǒng)采用電源供電雖然不存在能量有限的問題，但隨著應用范圍的擴大節(jié)點的數(shù)量劇增也應考慮盡可能地降低能耗。不同的傳感數(shù)據(jù)的緊急性不同，例如發(fā)生火災時溫度數(shù)據(jù)更加緊急，對傳送的服務(wù)質(zhì)量要求則更高。當網(wǎng)絡(luò)規(guī)模較大和節(jié)點數(shù)量眾多時，節(jié)點的加入和退出使得WSN網(wǎng)絡(luò)拓撲結(jié)構(gòu)頻繁變化，因此魯棒性和可擴展性也是評價路由協(xié)議好壞的重要指標。

1.WSN中幾種典型的分簇路由協(xié)議

對于已有的路由協(xié)議的研究成果，按照網(wǎng)絡(luò)的拓撲結(jié)構(gòu)可以將WSN路由協(xié)議分為平面路由協(xié)議和分簇路由協(xié)議。典型的平面路由算法有DD，SAR，SPIN，Romor等。平面路由的優(yōu)點是簡單，易擴展，無需進行結(jié)構(gòu)維護，具有良好的健壯性，而缺點則是網(wǎng)絡(luò)中無管理節(jié)點，信息傳輸量大導致占用通信資源較大，以至于網(wǎng)絡(luò)動態(tài)反應不靈敏。分簇路由協(xié)議就是將傳感節(jié)點分簇，簇內(nèi)通信由簇頭節(jié)點進行數(shù)據(jù)融合來減少傳輸信息量，最后將簇內(nèi)所有節(jié)點的數(shù)據(jù)傳送給匯聚節(jié)點。分簇路由協(xié)議將節(jié)點分簇使得拓撲管理方便，簇內(nèi)節(jié)點只發(fā)送數(shù)據(jù)給簇頭使得能量利用高效、數(shù)據(jù)融合節(jié)約了通信資源，這些優(yōu)點使得分簇路由成為當前研究的重點。

1.1LEACH協(xié)議

LEACH協(xié)議（Low Energy Adaptive Clustering Hierarchy）的實現(xiàn)分為成簇階段和數(shù)據(jù)傳輸階段。每輪中，相鄰的節(jié)點動態(tài)地形成簇，隨機的選擇簇頭節(jié)點；然后簇內(nèi)節(jié)點把數(shù)據(jù)發(fā)給簇頭，經(jīng)數(shù)據(jù)融合后發(fā)送給基站節(jié)點。簇內(nèi)節(jié)點按照時多分址TDMA向簇頭發(fā)送數(shù)據(jù)；各簇間簇頭采用碼多分址CDMA競用通道，競用通道成功的簇頭將融合后的數(shù)據(jù)發(fā)送給基站節(jié)點。隨機選舉的簇頭使得節(jié)點能耗均衡，采用一跳通信傳輸時延較小，數(shù)據(jù)聚合減少了通信量。缺點在于離Sink較遠的節(jié)點采用大功率通信耗費能量。

1.2PEGASIS協(xié)議

與其他樹形結(jié)構(gòu)路由協(xié)議不同，PEGASIs（Power Efficient Gathering in Sensor Information System）采用鏈狀結(jié)構(gòu)連接，解決了LEACH協(xié)議中產(chǎn)生重疊區(qū)域的問題。在一輪中，采用貪心算法，每個傳感器節(jié)點只需和距離自己最近的鄰居節(jié)點進行通信，鏈中節(jié)點在每輪通信中輪流作鏈首節(jié)點（chain head），鏈首發(fā)送數(shù)據(jù)傳輸指令給鏈尾，鏈尾再通過鄰居節(jié)點傳輸數(shù)據(jù)給鏈首，鏈首將接收的信息進行數(shù)據(jù)融合，當所有節(jié)點與鏈首通信后鏈首將數(shù)據(jù)傳送給sink，再進行新一輪的通信。采用鏈結(jié)構(gòu)的好處是不需要維護簇的結(jié)構(gòu)和記錄簇成員數(shù)量，只需要知道上下級就可以了，而且在功耗方面PEGASIS比LEACH省近3倍左右。PEGASIS算法僅選擇一個節(jié)點與Sink通信，利用數(shù)據(jù)融合，延長了網(wǎng)絡(luò)的生命期。但鏈中遠距離的節(jié)點數(shù)據(jù)傳輸?shù)交竟?jié)點的時間延遲會很大，而且單一的鏈首可能會成為整個網(wǎng)絡(luò)的瓶頸。

2.PEGASIS算法的具體描述

2.1PEGASIS網(wǎng)絡(luò)模型

（1）基站節(jié)點位置不變并應具有足夠的能量。（2）網(wǎng)絡(luò)中所有的節(jié)點都是靜止的。（3）網(wǎng)絡(luò)中所有節(jié)點能夠彼此通信，且都有足夠的能量能與基站直接通信，同時需要知道其他節(jié)點的位置。（4）網(wǎng)絡(luò)中所有節(jié)點都具有相同的性質(zhì)和功能，都可以進行壓縮、去冗余等數(shù)據(jù)融合并且能量有限。

2.2成鏈階段

在成鏈過程中，采用貪心算法的原理。貪心算法是從初始解向目標逼近的過程，每一次逼近都盡可能求出最優(yōu)的解，總是作出當前最好的選擇。首先選擇距離基站節(jié)點最遠的節(jié)點作為鏈尾，然后鏈尾比較網(wǎng)絡(luò)中離自己最近的節(jié)點加入到鏈中，節(jié)點依次加入直到加入鏈首，鏈首即為“首領(lǐng)節(jié)點”通過輪流擔當?shù)姆绞?，最終鏈首將融合后的數(shù)據(jù)發(fā)送給基站，至此完成一輪的成鏈過程（見圖1）。

2.3數(shù)據(jù)傳輸階段

一輪中，通過貪婪算法成鏈選舉出“首領(lǐng)節(jié)點”后，首領(lǐng)節(jié)點與基站進行通信的過程就是數(shù)據(jù)傳輸階段。數(shù)據(jù)傳輸過程可以使用令牌（Token）和時隙2種傳輸方式。假設(shè)網(wǎng)絡(luò)中只有5個節(jié)點，編號分別設(shè)為IJl，L2，L3，L4，L5，在本輪中選定L3為“首領(lǐng)節(jié)點”，令牌傳輸過程是首領(lǐng)節(jié)點L3向鏈中發(fā)送令牌，讓它通過L2傳播到端點L1，數(shù)據(jù)的傳播方向與令牌相反，當L3接收到融合后的返回數(shù)據(jù)，再向另一端L5發(fā)送令牌，當兩端的數(shù)據(jù)都到達后，首領(lǐng)節(jié)點將數(shù)據(jù)發(fā)送給基站節(jié)點，則本輪結(jié)束。時隙傳輸方式與令牌傳輸令牌不同，要求鏈上所有節(jié)點都保持同步傳輸。