無線傳感器網(wǎng)絡(luò)中基于位置信息的低能耗路由算法

胡君

摘 要：許多研究表明，優(yōu)秀的分簇路由算法能夠有效的延長(zhǎng)傳感器網(wǎng)絡(luò)的使用時(shí)間。在分析典型的分簇路由算法LEACH存在問題的基礎(chǔ)上，提出了基于位置信息的低能耗路由算法，該算法在LEACH算法的簇頭選取機(jī)制上進(jìn)行了改進(jìn)，綜合考慮了位置和能量等信息，仿真實(shí)驗(yàn)表明，新算法較LEACH算法能更好的降低能耗，均衡網(wǎng)絡(luò)能量，延長(zhǎng)網(wǎng)絡(luò)使用時(shí)間。

關(guān)鍵詞：傳感器網(wǎng)絡(luò)；簇頭；位置信息；節(jié)能

1 引言

無線傳感器網(wǎng)絡(luò)可以靈活方便的部署于高危或不適于人類生存的地區(qū)收集、處理和發(fā)送監(jiān)測(cè)數(shù)據(jù)。因此在軍事、民用等領(lǐng)域有著十分廣泛的應(yīng)用。傳感器節(jié)點(diǎn)攜帶的電子設(shè)備都需要通過其電池來進(jìn)行供電。由于傳感器網(wǎng)絡(luò)部署的特殊環(huán)境及網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量極大，因此電池能源往往得不到及時(shí)有效的補(bǔ)充，導(dǎo)致部分節(jié)點(diǎn)因能量耗盡無法工作，造成監(jiān)測(cè)黑洞或者通訊盲點(diǎn)。上述原因使得在能量受限的條件下延長(zhǎng)傳感器網(wǎng)絡(luò)工作時(shí)間成為研究人員關(guān)注的熱點(diǎn)[1][2]。傳感器網(wǎng)絡(luò)在得不到能量補(bǔ)充時(shí)只 能通過降低網(wǎng)絡(luò)能耗來有效延長(zhǎng)使用時(shí)間。而優(yōu)秀的傳感器網(wǎng)絡(luò)路由算法往往可以通過縮短節(jié)點(diǎn)通信距離，減少通信數(shù)據(jù)量等方式降低節(jié)點(diǎn)的工作能耗，從而延長(zhǎng)傳感器網(wǎng)絡(luò)的工作時(shí)間。

本文提出了一種基于位置信息的低能耗路由算法，在LEACH算法選取簇頭的基礎(chǔ)上，綜合考慮傳感器節(jié)點(diǎn)與其它節(jié)點(diǎn)的相對(duì)位置，剩余能量及承擔(dān)與基站通信的工作量等相關(guān)要素，使得簇的拓?fù)浣Y(jié)構(gòu)更加合理，簇頭節(jié)點(diǎn)能耗更低，網(wǎng)絡(luò)能耗更加均衡，有效的延長(zhǎng)了傳感器網(wǎng)絡(luò)的工作時(shí)長(zhǎng)。

2 相關(guān)工作

目前，已有許多分簇路由算法[3][4]被提出，其中Heinzelman等人提出的LEACH算法[5]是最具代表性和里程碑意義的。

2.1 LEACH算法描述

LEACH算法主要通過隨機(jī)選擇聚類首領(lǐng)，平均分擔(dān)中繼通信業(yè)務(wù)來實(shí)現(xiàn)。同時(shí)LEACH定義了“輪”（Round）的概念，針對(duì)每個(gè)節(jié)點(diǎn)n設(shè)定了一個(gè)閥值T（n），每輪開始時(shí)，節(jié)點(diǎn)自動(dòng)產(chǎn)生一個(gè)0到 1之間的隨機(jī)數(shù)，如果隨機(jī)數(shù)小于閾值，節(jié)點(diǎn)就當(dāng)選簇頭，并向周圍廣播其簇頭消息，其余節(jié)點(diǎn)根據(jù)接收到的簇頭廣播信息選擇距離自己最近的簇加入。

2.2 存在問題

⑴LEACH算法選取簇頭時(shí)沒有考慮成簇后，該簇頭在簇中的位置。如果選取的簇頭位于簇結(jié)構(gòu)的邊緣位置，則簇頭較位于簇結(jié)構(gòu)中心位置的簇頭要耗費(fèi)更多的能量。

⑵由于簇頭能量消耗遠(yuǎn)比一般節(jié)點(diǎn)大。因此在選取簇頭時(shí)，應(yīng)該盡可能選取剩余能量較多的節(jié)點(diǎn)。而LEACH算法沒有考慮節(jié)點(diǎn)能量問題。

⑶LEACH算法沒有考慮到部署區(qū)域中靠近基站的簇頭將承擔(dān)比一般簇頭更多的數(shù)據(jù)匯聚和轉(zhuǎn)發(fā)工作，能量消耗也更加快的問題。應(yīng)該在這類區(qū)域中選取更多的簇頭，這樣有利于控制每個(gè)簇的規(guī)模，減少簇頭簇內(nèi)能量消耗，均衡能耗。

3 LEACH算法改進(jìn)

3.1 無線傳感器網(wǎng)絡(luò)體系設(shè)定

為了算法描述的清晰，做以下假設(shè)：

⑴所有節(jié)點(diǎn)經(jīng)部署在邊長(zhǎng)為L(zhǎng)的正方形區(qū)域；

⑵傳感器節(jié)點(diǎn)部署后節(jié)點(diǎn)位置保持不變；

⑶傳感器節(jié)點(diǎn)能量受限，且具有GPS定位系統(tǒng)，能確定自己的位置坐標(biāo)；

⑷每個(gè)節(jié)點(diǎn)都是同構(gòu)的，具有相同的初始能量、通信及感知半徑，并能監(jiān)測(cè)自身的剩余能量；

⑸傳感器節(jié)點(diǎn)可以通過多跳的方式與基站BS進(jìn)行通訊，基站可以對(duì)所有傳感器節(jié)點(diǎn)進(jìn)行廣播。

本文使用以下關(guān)于通訊距離和通訊數(shù)據(jù)量的傳感器節(jié)點(diǎn)發(fā)送、接收能耗模型：

Esend（k，d）=Eunit*k+Eamp*k*d2 （1）

其中Esend（k，d）表示節(jié)點(diǎn)發(fā)送k字節(jié)大小的數(shù)據(jù)包到距離為d的目標(biāo)節(jié)點(diǎn)所需耗費(fèi)的能量，Eunit為發(fā)送單位自己的能耗，Eamp為電氣特性參數(shù)。

Erec（k）= Eunit*k （2）

Erec（k）表示節(jié)點(diǎn)接收數(shù)據(jù)的能耗關(guān)于數(shù)據(jù)量K的函數(shù)。

3.2 簇頭選取閥值的優(yōu)化

在傳感器節(jié)點(diǎn)部署后第一輪成簇的時(shí)候，基站對(duì)所有節(jié)點(diǎn)廣播自己的位置坐標(biāo)（xBS，yBS）及傳感器部署區(qū)域的坐標(biāo)。

以后每輪節(jié)點(diǎn)簇頭閥值計(jì)算步驟為：

Step1：各節(jié)點(diǎn)根據(jù)基站的坐標(biāo)計(jì)算出自己距離靠近基站一側(cè)的部署邊界的距離DNi（第1輪計(jì)算）；

Step2：所有節(jié)點(diǎn)Ni{i∈I|1≤i≤n，n∈N}以通訊半徑r向周邊節(jié)點(diǎn)廣播Msg_location，其中包括自己的坐標(biāo)，節(jié)點(diǎn)編號(hào)；

Step3：節(jié)點(diǎn)Ni根據(jù)收到的其它節(jié)點(diǎn)信息計(jì)算出它的候選簇頭聚合性指標(biāo)G。

假設(shè)節(jié)點(diǎn)Ni收到M個(gè)其它節(jié)點(diǎn)發(fā)出的廣播。其中，Nj∈M，dist（Ni，Nj）表示節(jié)點(diǎn)Ni到另一個(gè)節(jié)點(diǎn)Nj的直線距離。

W值越大，則表示Ni節(jié)點(diǎn)如果成為簇頭，其越靠近簇結(jié)構(gòu)的中心位置，應(yīng)該優(yōu)先成為簇頭。

Step4：每個(gè)節(jié)點(diǎn)計(jì)算出自己的候選簇頭能量指標(biāo)H，

其中，Ecur表示節(jié)點(diǎn)當(dāng)前能量，Einit表示節(jié)點(diǎn)初始能量，H值越大表示節(jié)點(diǎn)能量越多，成為簇頭的幾率應(yīng)該較高。

Step5：每個(gè)節(jié)點(diǎn)計(jì)算出候選簇頭中轉(zhuǎn)通信能耗指標(biāo)，

F值越大，則表示節(jié)點(diǎn)越靠近距離基站一側(cè)邊界，其承擔(dān)的轉(zhuǎn)發(fā)通信工作也越多，應(yīng)該具有更高的成為簇頭的幾率，其中XA，XD，為部署區(qū)域靠近基站一側(cè)邊界的兩個(gè)頂點(diǎn)的橫坐標(biāo)。

Step6：根據(jù)式（4）、（5）、（6）可以得到閥值公式綜合改進(jìn)指標(biāo)，

Q=α*w+β*H+γ*F （6）

其中，α、β、γ均為權(quán)值調(diào)節(jié)參數(shù)，并可以保證P∈[0，1]。

Step7：改進(jìn)的LEACH簇頭閥值計(jì)算公式如下：

4 仿真實(shí)驗(yàn)及結(jié)論

為了驗(yàn)證基于位置信息的低能耗路由算法（EELIRG）性能，使用matlab對(duì)LEACH算法和EELIRG算法進(jìn)行了仿真。傳感器節(jié)點(diǎn)部署在范圍為200CM*200CM的矩形區(qū)域，節(jié)點(diǎn)初始能量為1J。部署區(qū)域靠近基站的一側(cè)兩定點(diǎn)坐標(biāo)為（300，300），（300，100），基站坐標(biāo)為（500，200），Eunit=50nJ/bit，Eamp=100pJ/bit/m2， α、β、γ分別取0.4，0.3，0.3。

若隨機(jī)生成100，150，200……個(gè)傳感器節(jié)點(diǎn)，仿真實(shí)驗(yàn)結(jié)果如下：

橫坐標(biāo)為部署的節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)為采用LEACH算法或EELIRG算法時(shí)成簇的輪數(shù)（即網(wǎng)絡(luò)的使用時(shí)間），可以看出，傳感器網(wǎng)絡(luò)采用EELIRG算法比采用LEACH算法的使用時(shí)間延長(zhǎng)了50%左右。仿真實(shí)驗(yàn)表明，EELIRG算法能比LEACH算法更有效地降低與均衡網(wǎng)絡(luò)的能量消耗，從而可以使傳感器網(wǎng)絡(luò)的生命周期在LEACH算法的基礎(chǔ)上有較大提高。

[參考文獻(xiàn)]

[1]趙昕，張新.基于博弈論的無線傳感器網(wǎng)絡(luò)簇間路由選擇算法[J].計(jì)算機(jī)應(yīng)用，2013，33（7）：1813–1815.

[2]戴菲菲，等.改進(jìn)K-ACO無線傳感器網(wǎng)絡(luò)的分簇路由算法[J].傳感器與微系統(tǒng)，2013，32（8）：135–138.

[3]田煒，楊震.新的位置感知分簇算法[J].通信學(xué)報(bào)，2010，31（3）：25–30.

[4]王剛，等.無線傳感器網(wǎng)絡(luò)中簇首選擇算法研究[J].通信技術(shù)，2010，43（8）：35–40.

[5]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].In：Proc.of the 33rd Annual Hawaii Intl Conf.on System Sciences.Maui：IEEE Computer Society，2000.3005-3014.