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

彭易波，劉安豐，趙 軍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 無(wú)線傳感器節(jié)點(diǎn)的結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

以數(shù)據(jù)為中心的路由協(xié)議，是專門為無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)的，它以感知到的數(shù)據(jù)的屬性命名，對(duì)相同屬性的數(shù)據(jù)在傳輸過(guò)程中進(jìn)行融合，減少無(wú)線傳感器網(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é)點(diǎn)感知的相似數(shù)據(jù)，通過(guò)過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)間協(xié)商的方式過(guò)濾掉了傳輸過(guò)程中的冗余數(shù)據(jù)，從而減少了數(shù)據(jù)傳輸(包含發(fā)送和接受)過(guò)程中的能量消耗。

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

3.1.2 DD算法

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

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

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

基于分簇的路由協(xié)議的路由協(xié)議實(shí)際上是一種層次結(jié)構(gòu)的路由協(xié)議，整個(gè)網(wǎng)絡(luò)被劃分為許多簇，每個(gè)簇都有一個(gè)簇頭和多個(gè)簇成員。這些簇頭間形成高一級(jí)網(wǎng)絡(luò)，它們直接跟Sink節(jié)點(diǎn)通信。簇頭負(fù)責(zé)本簇內(nèi)簇成員節(jié)點(diǎn)的管理，并負(fù)責(zé)簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的收集和融合，同時(shí)還負(fù)責(zé)簇間數(shù)據(jù)的轉(zhuǎn)發(fā)。分簇路由的特點(diǎn)是擴(kuò)展性好，可適用于大規(guī)模的無(wú)線傳感器網(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ù)載平衡到每一個(gè)傳感器節(jié)點(diǎn)當(dāng)中。非簇頭節(jié)點(diǎn)以就近原則加入相應(yīng)簇頭，非簇頭節(jié)點(diǎn)將采集到的數(shù)據(jù)直接發(fā)給簇頭，再由簇頭節(jié)點(diǎn)將接受到的數(shù)據(jù)進(jìn)行融合后轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)，從而達(dá)到減少傳輸數(shù)據(jù)量，降低網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)整體生存時(shí)間的目的。

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

3.2.2 PEGASIS算法

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

4 結(jié)論

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

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

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

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

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

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

TP301.6

A

1674-6708（2010）18-0116-02