胡君

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

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

1 引言

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

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

2 相關(guān)工作

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

2.1 LEACH算法描述

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

2.2 存在問題

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

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

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

3 LEACH算法改進

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

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

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

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

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

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

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

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

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

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

Erec（k）= Eunit*k （2）

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

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

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

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

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

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

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

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

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

Step4：每個節(jié)點計算出自己的候選簇頭能量指標H，

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

Step5：每個節(jié)點計算出候選簇頭中轉(zhuǎn)通信能耗指標，

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

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

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

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

Step7：改進的LEACH簇頭閥值計算公式如下：

4 仿真實驗及結(jié)論

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

若隨機生成100，150，200……個傳感器節(jié)點，仿真實驗結(jié)果如下：

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

[參考文獻]

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

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

[3]田煒，楊震.新的位置感知分簇算法[J].通信學(xué)報，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.