基于能量的無線傳感器網(wǎng)絡(luò)高效路由算法分析

彭易波，劉安豐，趙 軍

1.中南大學(xué)軟件學(xué)院，湖南長沙 410083

2.湖南文理學(xué)院計算機(jī)學(xué)院，湖南常德 415000

基于能量的無線傳感器網(wǎng)絡(luò)高效路由算法分析

彭易波1,2，劉安豐1，趙 軍1

1.中南大學(xué)軟件學(xué)院，湖南長沙 410083

2.湖南文理學(xué)院計算機(jī)學(xué)院，湖南常德 415000

無線傳感器網(wǎng)絡(luò)節(jié)點能量有限，如何提高節(jié)點能耗效率降低能耗開銷是傳感器設(shè)計中的首要考慮的問題。本文分析了無線傳感器的體系結(jié)構(gòu)，并從路由協(xié)議入手，分析了幾種典型的路由算法，闡述了算法能量高效的思想。

無線傳感器；能量；協(xié)議；算法

隨著微電子技術(shù)、無線通信技術(shù)、計算機(jī)網(wǎng)絡(luò)技術(shù)和傳感器技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)成為近年來信息技術(shù)領(lǐng)域的一個研究熱點，國內(nèi)外許多高校和科研機(jī)構(gòu)都對其展開了研究。

無線傳感器網(wǎng)絡(luò)是由大量低成本、低功耗體積微小的傳感器節(jié)點組成，它們被部署在監(jiān)測區(qū)域內(nèi)，通過無線通信方式形成一個多跳的自組織網(wǎng)絡(luò)。其目的是監(jiān)測、采集、處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的數(shù)據(jù)，通過傳感器節(jié)點間的協(xié)作將信息發(fā)給觀察者。

由于傳感器節(jié)點體積小、成本低、可直接部署在監(jiān)控區(qū)域等諸多特點，無線傳感器網(wǎng)絡(luò)的應(yīng)用范圍非常廣泛，可用于軍事應(yīng)用、工業(yè)監(jiān)控、環(huán)境監(jiān)測、醫(yī)療監(jiān)護(hù)、智能家居、倉庫管理、交通控制等方面，具有廣闊的市場應(yīng)用前景，因而該技術(shù)被稱為21世紀(jì)最重要和最有影響的技術(shù)之一。

1 無線傳感器網(wǎng)絡(luò)與無線傳感器節(jié)點

1.1 無線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)

無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)通常由無線傳感器節(jié)點(Sensor node)、匯聚節(jié)點(Sink)、互聯(lián)網(wǎng)或者通信衛(wèi)星、管理節(jié)點等部分組成。大量無線傳感器節(jié)點被隨機(jī)部署在監(jiān)測區(qū)域，傳感器節(jié)點間通過自組織的方式形成網(wǎng)絡(luò)，每個節(jié)點既可以采集數(shù)據(jù)，又可以處理數(shù)據(jù)。單個傳感器節(jié)點采集到的數(shù)據(jù)通過“多跳”的方式將數(shù)據(jù)傳遞到匯聚節(jié)點，匯聚節(jié)點通過互聯(lián)網(wǎng)或者通信衛(wèi)星到達(dá)管理節(jié)點傳遞給觀察者，實現(xiàn)觀察者和傳感器之間的通信。

1.2 無線傳感器網(wǎng)絡(luò)的主要特點

1）低功耗、低成本、體積小、集成度高。相對于傳統(tǒng)的傳感器網(wǎng)絡(luò)節(jié)點來說，當(dāng)前的無線傳感器節(jié)點更強(qiáng)調(diào)傳感器節(jié)點的低功率、低成本、微型化和高集成度等特點。雖然目前一些商用的傳感器節(jié)點的指標(biāo)還未達(dá)到要求，但卻代表了今后的發(fā)展方向。

2）節(jié)點數(shù)量多，分布范圍廣。由于無線傳感器節(jié)點間傳遞數(shù)據(jù)的距離有限，所以在監(jiān)測區(qū)域內(nèi)需要布置大量的節(jié)點。通過這些節(jié)點的部署，可以獲得區(qū)域內(nèi)比較完整的信息或者同一區(qū)域內(nèi)的多維信息，這些信息經(jīng)過處理后，可以提高信息獲取的準(zhǔn)確度。

3）自組織網(wǎng)絡(luò)。由于傳感器節(jié)點通常采用隨機(jī)部署，其節(jié)點位置和相鄰位置不能預(yù)先確定，而且節(jié)點可能由于能量耗盡或者其他因素導(dǎo)致失效，再加之一些節(jié)點可能由于移動以及采用（休眠調(diào)度）機(jī)制導(dǎo)致網(wǎng)絡(luò)節(jié)點處于動態(tài)變化之中，所以無線傳感器網(wǎng)絡(luò)為適應(yīng)這些變化，只能采用自組織網(wǎng)絡(luò)形式。

4）傳感器節(jié)點能量有限。無線傳感器節(jié)點的能量一般由能量有限的電池提供，而且不可更換。由于傳感器節(jié)點一般都是隨機(jī)部署在特殊環(huán)境當(dāng)中，體積微小，電源能量有限，而一旦大部分無線傳感器網(wǎng)絡(luò)節(jié)點中的電池能量消耗完，傳感器網(wǎng)絡(luò)就會癱瘓，無法正常工作。

5）使用數(shù)據(jù)融合的技術(shù)。在傳統(tǒng)的傳輸網(wǎng)絡(luò)(如Internet)中，網(wǎng)絡(luò)層提供點到點的報文轉(zhuǎn)發(fā)以實現(xiàn)數(shù)據(jù)的分組傳輸，數(shù)據(jù)傳輸完成后，數(shù)據(jù)會完整的從源節(jié)點傳遞到目的地點。而無線傳感器網(wǎng)絡(luò)不同，它只是為了采集到感知區(qū)域的有效信息，數(shù)據(jù)在逐次傳輸?shù)倪^程中會被不斷的修改融合，只需有效數(shù)據(jù)匯集到Sink節(jié)點，用以減少數(shù)據(jù)傳遞過程中的能量消耗，以延長節(jié)點和傳感器網(wǎng)絡(luò)的生存期。

1.3 無線傳感器節(jié)點的結(jié)構(gòu)

典型的無線傳感器節(jié)點通常包括數(shù)據(jù)采集模塊、數(shù)據(jù)處理模塊、無線通信模塊和供電模塊等。數(shù)據(jù)采集模塊主要負(fù)責(zé)監(jiān)控區(qū)域內(nèi)數(shù)據(jù)的采集；數(shù)據(jù)處理模塊主要負(fù)責(zé)存儲和處理本節(jié)點采集到的數(shù)據(jù)和其它節(jié)點發(fā)來的數(shù)據(jù)；無線通信模塊主要負(fù)責(zé)與其它節(jié)點通信；供電模塊負(fù)責(zé)為其它模塊提供電能，保證其正常工作。當(dāng)然，不同的應(yīng)用場合，可能包含其它部件，如移動器等。

2 無線傳感器網(wǎng)絡(luò)能量分析

無線傳感器網(wǎng)絡(luò)跟傳統(tǒng)的無線通信網(wǎng)絡(luò)（如蜂窩移動網(wǎng)和MANET，移動自組網(wǎng)）不同，傳統(tǒng)的無線網(wǎng)絡(luò)節(jié)點的能量可以很方便的通過基站或者其它設(shè)備供給，所以研究重點在于如何提高通信的服務(wù)質(zhì)量(QoS)上。而無線傳感器網(wǎng)絡(luò)是一種無基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，其節(jié)點能量有限，不可補(bǔ)充，所以如何提高無線傳感器網(wǎng)絡(luò)的能量效率成為了研究傳感器網(wǎng)絡(luò)的重點之一。

無線傳感器網(wǎng)絡(luò)由許多個結(jié)構(gòu)相同或者相似的節(jié)點組成，每個節(jié)點包含數(shù)據(jù)采集、數(shù)據(jù)處理、無線通信、電源供應(yīng)4個模塊。實驗數(shù)據(jù)表明，數(shù)據(jù)采集和數(shù)據(jù)處理所消耗的能量都很低，絕大部分能量消耗在無線通信模塊。無線通信模塊有4種狀態(tài)，即發(fā)送、接受、空閑和睡眠狀態(tài)。空閑狀態(tài)是指無線傳感器在無線信道中，既不發(fā)送也不接受信息。睡眠狀態(tài)指無線傳感器處于不工作狀態(tài)。在4種狀態(tài)中，發(fā)送狀態(tài)能量消耗最大，空閑狀態(tài)和接受狀態(tài)相當(dāng)，略小于發(fā)送狀態(tài)，在睡眠狀態(tài)下，能量最小。

提高無線傳感器網(wǎng)絡(luò)的生命周期，就必須提高其能量的利用效率，而提高能量使用效率在于設(shè)計良好的高效的路由協(xié)議，降低數(shù)據(jù)發(fā)送和傳輸過程中的能耗，提高傳感器節(jié)點的能量利用率，從而提高整個無線傳感器網(wǎng)絡(luò)的生命周期。

3 無線傳感器路由協(xié)議分類

無線傳感器路由協(xié)議解決的是數(shù)據(jù)的傳輸，是無線傳感器網(wǎng)絡(luò)的核心，路由協(xié)議的性能決定了整個網(wǎng)絡(luò)的性能。從功能上來講，無線傳感器路由協(xié)議的主要設(shè)計目標(biāo)是在滿足應(yīng)用需求的同時盡量降低網(wǎng)絡(luò)開銷，提高節(jié)點和整個網(wǎng)絡(luò)的使用壽命。

根據(jù)目前典型的協(xié)議，可以將無線傳感器的路由協(xié)議劃分為兩大類：一是以數(shù)據(jù)為中心的路由協(xié)議；一是基于分簇的路由協(xié)議。

3.1 以數(shù)據(jù)為中心的路由協(xié)議

以數(shù)據(jù)為中心的路由協(xié)議，是專門為無線傳感器網(wǎng)絡(luò)設(shè)計的，它以感知到的數(shù)據(jù)的屬性命名，對相同屬性的數(shù)據(jù)在傳輸過程中進(jìn)行融合，減少無線傳感器網(wǎng)絡(luò)中榮譽(yù)數(shù)據(jù)的傳輸。這類協(xié)議是最早、最有影響力的一類協(xié)議。這類協(xié)議上比較典型的算法有兩種。一類是基于信息協(xié)商的路由算法(SPIN,Sensor Protocol for Information Negotiation)，另一類是定向擴(kuò)散路由算法(DD,Directed Diffusion)。

3.1.1 SIPN路由算法

SIPN路由協(xié)議是一種以數(shù)據(jù)為中心的自適應(yīng)路由協(xié)議，它根據(jù)相鄰節(jié)點感知的相似數(shù)據(jù)，通過過網(wǎng)絡(luò)節(jié)點間協(xié)商的方式過濾掉了傳輸過程中的冗余數(shù)據(jù)，從而減少了數(shù)據(jù)傳輸(包含發(fā)送和接受)過程中的能量消耗。

SPIN協(xié)議通過節(jié)點間的協(xié)商，很好的解決了數(shù)據(jù)的內(nèi)爆和重疊問題，而且不需要了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的路由協(xié)議，幾乎不受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的影響，因而也適合在節(jié)點可以移動的無線傳感器網(wǎng)絡(luò)中使用。

3.1.2 DD算法

定向擴(kuò)散協(xié)議算法(DD,Directed Diffusion)是一種基于查詢的路由算法，是有別于傳統(tǒng)路由算法的一種基于數(shù)據(jù)相關(guān)的路由算法。在傳感器網(wǎng)絡(luò)，Sink節(jié)點(匯聚節(jié)點)周期地通過廣播的方式播撒一種稱為“興趣”的數(shù)據(jù)，告訴網(wǎng)絡(luò)中節(jié)點它需要收集什么樣的信息，在播撒“興趣”信息的同時，也建立起來了普通節(jié)點到Sink節(jié)點的路徑。Sink節(jié)點在所有的路由線路中，選擇一條作為最優(yōu)路徑，后續(xù)的數(shù)據(jù)就沿著這條路徑進(jìn)行信息的傳輸，從而避免了節(jié)點數(shù)據(jù)的重復(fù)傳遞，能夠有效的節(jié)省節(jié)點的能量，減輕無線信道的負(fù)荷，提高節(jié)點間帶寬的利用率。

DD算法通過廣播“興趣” 信息的方式建立起傳感器節(jié)點到Sink節(jié)點的路由，需要利用Sink節(jié)點完成對普通節(jié)點的查詢，因而不適合用于大規(guī)模的傳感器網(wǎng)絡(luò)和拓?fù)浣Y(jié)構(gòu)頻繁變化的傳感器網(wǎng)絡(luò)。

3.2 基于分簇的路由協(xié)議

基于分簇的路由協(xié)議的路由協(xié)議實際上是一種層次結(jié)構(gòu)的路由協(xié)議，整個網(wǎng)絡(luò)被劃分為許多簇，每個簇都有一個簇頭和多個簇成員。這些簇頭間形成高一級網(wǎng)絡(luò)，它們直接跟Sink節(jié)點通信。簇頭負(fù)責(zé)本簇內(nèi)簇成員節(jié)點的管理，并負(fù)責(zé)簇內(nèi)節(jié)點數(shù)據(jù)的收集和融合，同時還負(fù)責(zé)簇間數(shù)據(jù)的轉(zhuǎn)發(fā)。分簇路由的特點是擴(kuò)展性好，可適用于大規(guī)模的無線傳感器網(wǎng)絡(luò)。典型的基于分簇協(xié)議的算法有LEACH和PEGASIS

3.2.1 LEACH算法

LEACH (Low-Energy Adaptive Clustering Hierarchy)算法是MIT的Chandrakasan等人提出的基于WSN的低功耗自適應(yīng)路由算法，其基本思想是傳感器網(wǎng)絡(luò)以循環(huán)的方式隨機(jī)選擇簇頭，將網(wǎng)絡(luò)能量負(fù)載平衡到每一個傳感器節(jié)點當(dāng)中。非簇頭節(jié)點以就近原則加入相應(yīng)簇頭，非簇頭節(jié)點將采集到的數(shù)據(jù)直接發(fā)給簇頭，再由簇頭節(jié)點將接受到的數(shù)據(jù)進(jìn)行融合后轉(zhuǎn)發(fā)給Sink節(jié)點，從而達(dá)到減少傳輸數(shù)據(jù)量，降低網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)整體生存時間的目的。

LEACH算法平衡了節(jié)點的能量負(fù)載，提高了網(wǎng)絡(luò)的生存周期，但是它無法保證簇頭節(jié)點能覆蓋整個網(wǎng)絡(luò)，即有可能出現(xiàn)簇頭節(jié)點集中出現(xiàn)在某個區(qū)域，某些區(qū)域不存在簇頭節(jié)點，從而導(dǎo)致部分區(qū)域無法被無線網(wǎng)絡(luò)覆蓋。

3.2.2 PEGASIS算法

PEGASIS (Power-Efficient Gathering in Sensor Information System)算法是對LEACH算法的優(yōu)化，為了避免頻繁選舉簇頭的通信開銷，PEGASIS將所有節(jié)點連成一條鏈，鏈中只有一個節(jié)點充當(dāng)簇頭，而且簇頭節(jié)點在鏈中順序游走，實現(xiàn)節(jié)點的能耗平衡。每當(dāng)有傳感器節(jié)點電源耗盡，鏈就更新一次，從而保證了網(wǎng)絡(luò)的覆蓋和能耗的減少。

4 結(jié)論

無線傳感器網(wǎng)絡(luò)是個能量有限的無線網(wǎng)絡(luò)，其設(shè)計過程中首先要考慮的是生命周期的問題。如何延長傳感器網(wǎng)絡(luò)的使用壽命，降低網(wǎng)絡(luò)節(jié)點開銷，提高節(jié)點能量效率是傳感器網(wǎng)絡(luò)部署的重點。除了上述借助高效的路由協(xié)議算法外，還應(yīng)該考慮設(shè)計出高效低耗的電源或者可反復(fù)使用的電源（如光能電源等），這樣就可以從根本上解決無線傳感器網(wǎng)絡(luò)能量有限的問題。

[1] 李德英，等.無線傳感器網(wǎng)絡(luò)能量高效綜述[J].北京：計算機(jī)科學(xué)，2008，11.

[2] 崔莉，等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2005，4.

[3] 李曉維.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京：北京理工大學(xué)出版社，2007.

[4] 孫利民，李建中.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[5] 姚蘭，等.無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究和仿真[J].中國工控信息網(wǎng)，2005，7.

TP301.6

A

1674-6708（2010）18-0116-02