仇多利，卓翔芝，羅婷婷

(1.淮北師范大學(xué) 管理學(xué)院，安徽 淮北 235000;2.淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000)

基于分層簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議

仇多利1，卓翔芝1，羅婷婷2

(1.淮北師范大學(xué) 管理學(xué)院，安徽 淮北 235000;2.淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000)

在無線傳感器網(wǎng)絡(luò)技術(shù)中，路由技術(shù)是研究的熱點.本文分析經(jīng)典分簇路由算法LEACH協(xié)議的不足，提出一種基于分層簇路由協(xié)議LEACH－L.該算法把無線傳感器網(wǎng)絡(luò)覆蓋區(qū)域依據(jù)普通節(jié)點據(jù)匯聚節(jié)點的遠近將傳感區(qū)域分成大小不等的層，在層內(nèi)進行分簇，并依據(jù)能量因子參數(shù)優(yōu)選簇首.仿真結(jié)果表明，該算法能有效地減少能量損耗，延長網(wǎng)絡(luò)的生存周期.

無線傳感器網(wǎng)絡(luò);分層簇;路由協(xié)議;仿真

隨著微電子技術(shù)的發(fā)展，傳感器技術(shù)也朝著微型化、低功耗、多功能的方向快速發(fā)展，正廣泛應(yīng)用于社會的各個領(lǐng)域.無線傳感器網(wǎng)絡(luò)由分布在需求區(qū)域內(nèi)眾多的傳感器節(jié)點組成，協(xié)作地采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對象的信息，并發(fā)送給匯聚節(jié)點.但由于傳感器節(jié)點的能量是有限的，因此，在設(shè)計無線傳感器網(wǎng)絡(luò)時，都以低能耗作為首要考慮因素，在涉及到的眾多技術(shù)中，無線傳感器網(wǎng)絡(luò)路由協(xié)議是研究的熱點之一.

無線傳感器網(wǎng)絡(luò)路由協(xié)議技術(shù)主要分為平面路由協(xié)議和多層路由協(xié)議.平面路由協(xié)議主要有洪泛協(xié)議、SPN協(xié)議、DD協(xié)議，典型的分層路由協(xié)議主要有TEEN、SOP、LEACH.相比于平面路由協(xié)議，分層路由協(xié)議通過將傳感器節(jié)點組織成簇的結(jié)構(gòu).LEACH是分層路由協(xié)議中最早提出的分簇路由算法，但是LEACH協(xié)議是通過等概率隨機循環(huán)算法選取簇首，并沒有考慮到簇首的分布密度，并且簇間路由采用一跳通訊，節(jié)點的能耗較高.現(xiàn)在研究的主要熱點集中在對現(xiàn)有路由協(xié)議的改進，以提高網(wǎng)絡(luò)生命期.本文擬對LEACH協(xié)議存在的問題進行研究并進行改進，提出一種基于分層簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH－L.

1 LEACH存在的問題

LEACH協(xié)議工作過程主要分兩個階段:第一階段是成簇階段.在成簇階段，每個節(jié)點都產(chǎn)生一個在0到1之間的隨機數(shù)，并將此隨機數(shù)與節(jié)點成為簇頭節(jié)點的百分數(shù) T(n)進行比較，如果隨機數(shù)小于 T(n)，則該節(jié)點即當選為簇頭節(jié)點，如果大于 T(n)，則為普通節(jié)點，則等待簇頭節(jié)點的廣播.T(n)采用如下公式計算:

簇頭節(jié)點確定后，即廣播自己成為簇頭節(jié)點，等待非簇頭節(jié)點的加入.非簇頭節(jié)點會接收到若干簇頭節(jié)點的廣播，會選擇距離自己最近的簇頭節(jié)點告知相應(yīng)簇頭，加入相應(yīng)簇，所有節(jié)點加入完畢后，完成簇的建立.第二階段即為穩(wěn)定數(shù)據(jù)傳輸階段.在所有節(jié)點加入相應(yīng)簇之后，簇頭節(jié)點使用TDMA為簇內(nèi)成員分配時隙，成員節(jié)點接收時隙后即進入休眠狀態(tài)等待自己的時隙發(fā)送數(shù)據(jù).簇頭節(jié)點接收到所有數(shù)據(jù)后，進行數(shù)據(jù)融合消除冗余數(shù)據(jù)后再發(fā)送給SINK結(jié)點.

以上情況都是在理想狀況下的，在實際應(yīng)用中，LEACH存在以下不足:1.因為網(wǎng)絡(luò)規(guī)模的不同和節(jié)點分布情況是隨機的，不是均勻的，在該協(xié)議中并沒有考慮節(jié)點分布密度不均的情況，因此一個較好的 p值是十分難確定的.2.由于采用單跳通信，因此該協(xié)議并不適合較大規(guī)模的無線傳感器網(wǎng)絡(luò).3.各個結(jié)點在理想狀態(tài)下，原則上成為簇首的次數(shù)是相等的.而由于實際網(wǎng)絡(luò)并不是理想狀況，隨著網(wǎng)絡(luò)的運行，各個結(jié)點的能量消耗肯定不一樣，這就導(dǎo)致了在后期的簇首選擇中，有可能會由于某個節(jié)點的能量太少而加速過早的死掉，將極大的減少網(wǎng)絡(luò)的生命期.最重要的一點是在LEACH中，除一輪的簇首選舉都是相對獨立的，沒有太大的關(guān)聯(lián)，唯一的關(guān)聯(lián)就是在一個周期 r－1輪次中已經(jīng)成為簇首的節(jié)點不能再成為節(jié)點.

2 LEACH－L算法描述及分析

基于LEACH算法存在的問題和分布式傳感器網(wǎng)絡(luò)的特點，本文提出一種基于分層簇的改進型LEACH LEACH－L.該算法主要從成簇空間進行劃分，把節(jié)點分步空間劃分成若干大小不等的帶狀區(qū)域進行區(qū)域內(nèi)成簇.另外，對LEACH中的輪次之外進行補充，加入更高層次的循環(huán)，形成圖1所示的輪次.

其中，形成簇分層的外層輪次包含若干次并且遠大于形成簇首和穩(wěn)定數(shù)據(jù)傳輸輪次，在內(nèi)部輪次中，穩(wěn)定數(shù)據(jù)傳輸時間要遠大于形成簇首時間.

在文獻[3]中提出計算最優(yōu)簇頭數(shù)的思想.在本文的算法中把最優(yōu)簇頭數(shù)的計算控制在帶狀區(qū)域內(nèi)，在文獻[4]中，提出負載平衡因子.在本文算法中我們把負載平衡因子加入到簇頭的選舉當中以提高網(wǎng)絡(luò)的生命周期.LEACH－L算法主要分為3個階段:

1)分層階段.在分層階段，所有節(jié)點都是初始狀態(tài)，在開始工作之后首先向SINK節(jié)點廣播一條報告信息.SINK節(jié)點在收到所有節(jié)點的報告信息之后可得知最遠節(jié)點距自己的距離(假設(shè)節(jié)點可以根據(jù)發(fā)射功率計算出距離)，并根據(jù)如下公式得到層次數(shù) l:

式中 dmax和 dmin分別代表節(jié)點到匯聚節(jié)點的最大距離和最小距離，L代表最大層次數(shù)，R是網(wǎng)絡(luò)規(guī)模因子得到層數(shù)信息后，SINK結(jié)點廣播告知各節(jié)點所屬層次.

2)形成簇首階段.確定層數(shù)之后，SINK結(jié)點將層次編號信息發(fā)送給所有節(jié)點，此時，節(jié)點可知自己所屬層次.各個節(jié)點得知自己所屬層次后，廣播hello信息，可以得到層內(nèi)節(jié)點的度信息，根據(jù)文獻[3]中公式得到最優(yōu)簇頭數(shù)，

并根據(jù)文獻[6]確定簇首.

3)穩(wěn)定數(shù)據(jù)傳輸階段.在此階段，采用多跳式路由到達匯聚節(jié)點.圖2為算法執(zhí)行后形成的網(wǎng)絡(luò)圖.

3 仿真分析和結(jié)論

基于LEACH協(xié)議和LEACH－L協(xié)議，使用opnet分別進行仿真.仿真環(huán)境為1 000＊1 000的區(qū)域內(nèi)分布150個網(wǎng)絡(luò)節(jié)點，節(jié)點的通信范圍為130，仿真結(jié)果如圖3所示.

LEACH－L在形成分層之后，在距離閥值之內(nèi)的使用單挑通信和匯聚節(jié)點通信.超出閥值的使用多跳通信通過相鄰層的匯聚節(jié)點發(fā)送采集的信息到匯聚節(jié)點，所以在通信方式上比LEACH協(xié)議全部采用單跳通信所損耗的能量要少.另外，通過分層以及最優(yōu)簇頭數(shù)的計算，使LEACH－L協(xié)議在一定程度上較大地提高無線傳感器網(wǎng)絡(luò)的生命周期.

今后進一步的研究工作:因為傳感器的數(shù)量和分布的空間不確定，一個較好的分層數(shù)難以確定.這里做一個簡單的思考，假設(shè)節(jié)點空間基本為平面，區(qū)域為 k，傳感器節(jié)點數(shù)為 n，可以計算得到單位空間 k/n，再根據(jù)dmax、dmin和網(wǎng)絡(luò)規(guī)模因子 R，可以研究如何得到最優(yōu)的層次數(shù)公式.另外，在本論文中，在分層的時候并沒有考慮到剩余節(jié)點的能量，也可以把節(jié)點的剩余能量考慮進去，形成分層的層數(shù).

[1]李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機學(xué)報，2007，30(1):29.

[2]于飛，郭靜，胡繼珍.一種無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究與仿真[J].青島科技大學(xué)學(xué)報:自然科學(xué)版，2011，32(1):32.

[3]王江濤，楊庚，陳生壽.基于最優(yōu)簇頭數(shù)的無線傳感器網(wǎng)絡(luò)安全LEACH路由協(xié)議[J].南京郵電大學(xué)學(xué)報:自然科學(xué)版，2008，28(3):28－29.

[4]劉志東，唐智靈，曾麗珍.基于負載平衡因子的傳感器網(wǎng)絡(luò)路由算法研究[J].微計算機信息:測控自動化，2009，25(5－1): 150－151.

[5]戴世瑾，李樂民.高能量有效的基于分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機應(yīng)用研究，2010，27(6):2 201－2 203.

[6]SCHURGERSC，SRIVASTAVA M B.Energy efficient routing in wireless sensor networks[C]∥Proceedings of the IEEE Military Communications Conference(MILCOM)，McLean，VA，2001:3572361.

[7]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application－specific protocol architecture for wireless micro sensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660－670.

Abstract:In the wireless sensor network，the focus of research is routing technology.The Leach's shortcomings were analyzed in this paper，a routing protocol(Leach－L)based on hierarchical cluster was proposed.According to the distance of node to the sink node，LEACH－L divided the wsn's area into some layer，which was the ranging in size from the distance.The simulation results indicated that the Leach－L protocol could efficiently save the energy consumption and prolong the wireless sensor network lifetime.

Key words:wireless sensor networks;layered cluster;routing protocol;simulation

Wireless Sensor Networks Routing Protocol Based on Layered－Cluster

QIU Duo-li1，ZHUO Xiang-zhi1，LUO Ting-ting2
(1.School of Management，Huaibei Normal University，235000，Huaibei，Anhui，China;
2.School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China)

TP 393

A

2095－0691(2012)03－0068－03

2012－03－29

教育部人文社科研究一般項目(10YJC630427);淮北師范大學(xué)青年基金項目(700570)

仇多利(1981－ )，男，安徽淮北人，碩士，研究方向:計算機網(wǎng)絡(luò).