梅馮陽

摘 要：為了更高效地利用無線傳感器網(wǎng)絡(luò)節(jié)點的能量，均衡網(wǎng)絡(luò)能耗，文中提出了一種基于泰森圖的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法。該算法首先利用泰森圖劃分區(qū)域原理對區(qū)域內(nèi)所有節(jié)點進(jìn)行分簇，然后基于查詢報文獲取最小跳數(shù)的多徑路由發(fā)現(xiàn)機(jī)制進(jìn)行多路徑搜索，搜索過程充分考慮了路徑最大剩余能量、最小路由跳數(shù)和最近傳輸距離等因素，最后選出滿足條件的最優(yōu)路徑，完成源目的節(jié)點間的信息傳輸。仿真結(jié)果表明，該算法能有效地均衡網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)使用期限。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；泰森圖；查詢報文；分簇路由

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2016）08-00-04

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由一定數(shù)量的傳感器組成的智能無線網(wǎng)絡(luò)系統(tǒng)[1]，它以無線通信的方式連接各傳感器節(jié)點[2]，起到實時監(jiān)測和采集數(shù)據(jù)的作用。無線傳感器網(wǎng)絡(luò)協(xié)議一直都是這個領(lǐng)域研究的熱點。由于傳感器節(jié)點能量十分有限，分布區(qū)域位置復(fù)雜，設(shè)計能均衡網(wǎng)絡(luò)能耗、延長使用壽命和提供快捷實時的數(shù)據(jù)服務(wù)協(xié)議也就成了重點。

LEACH （ Low Energy Adaptive Clustering Hierarchy，LEACH） 是最早提出的低功耗自適應(yīng)基于分簇的路由協(xié)議[3]，它隨機(jī)選擇簇頭，讓每一個節(jié)點都有機(jī)會當(dāng)選為簇頭，從而平衡了網(wǎng)絡(luò)能耗。但在LEACH算法中，產(chǎn)生簇首的過程沒有將節(jié)點自身的剩余能量計算在內(nèi)，某個簇頭可能因為能量很低無法擔(dān)任數(shù)據(jù)傳輸任務(wù)，因此該算法不利于網(wǎng)絡(luò)的能耗均衡。另外在LEACH算法中，簇首與匯聚節(jié)點間采用單跳數(shù)據(jù)傳輸，傳輸距離較遠(yuǎn)的節(jié)點能耗自然比較大，致使網(wǎng)絡(luò)能量不能高效利用[4，5]。

針對LEACH算法的不足，文獻(xiàn)[6，7]提出了對簇首選舉時的門限值T（n）進(jìn)行改進(jìn)，這在一定程度上提高了高能量節(jié)點成為簇首的概率，有利于網(wǎng)絡(luò)能量的平衡。Lindsey S.等人在LEACH的基礎(chǔ)上提出了PEGASIS協(xié)議[8]，但該協(xié)議的前提是每一個節(jié)點都能夠與Sink節(jié)點直接通信，這就限制了網(wǎng)絡(luò)范圍，擴(kuò)展性較差。文獻(xiàn)[9]提出了一種非均勻分簇的多跳路由協(xié)議EEUC，該協(xié)議的優(yōu)點是考慮到了簇首均衡能耗的情況，平衡了網(wǎng)絡(luò)能耗，源節(jié)點與匯聚節(jié)點之間采用多跳的方式傳輸數(shù)據(jù)，避免直接通信造成能量耗損過快。但該協(xié)議在簇的生成階段涉及到簇間距離的限制，過程控制比較復(fù)雜。后來又有基于粒子群[9]的非均勻分簇算法和基于蟻群[10，11]的分簇算法，但他們的設(shè)計過程也都相對復(fù)雜。

本文對LEACH及PEGASIS協(xié)議進(jìn)行分析，針對LEACH和PEGASIS協(xié)議在簇頭選擇以及數(shù)據(jù)傳輸過程中的不足，提出一種基于泰森圖分簇的路由算法，該算法在分簇階段采用泰森圖的區(qū)域劃分原理進(jìn)行分簇，避免了傳統(tǒng)分簇算法遇到的問題，在簇間路由階段采用基于報文查詢的機(jī)制獲取最優(yōu)傳輸路徑，從而在網(wǎng)絡(luò)能耗均衡方面相較優(yōu)良，能夠延長網(wǎng)絡(luò)的使用期限。

1 泰森圖分簇算法

1.1 泰森圖介紹

泰森圖是為解決這類問題而產(chǎn)生的幾何圖形[12]：平面中假設(shè)有n個點，給定任意點p，對于其他任意一點q，求距離p比距離q更近的點的幾何。

若只有兩個點p和q，作他們連線的垂直平分線，在平分線任意一側(cè)的任意點c（假設(shè)在p點一側(cè)），則cp的距離比cq距離近，而c點若在q一側(cè)，則cq距離比cp距離近。

若現(xiàn)有一集合P{A，B，C，D，E}，此時的劃分過程是：把所有點連接成凸或凹多邊形，是凸多邊形則在凸多邊形內(nèi)任意找一點，如果是凹多邊形，則在凹的方向找一點補(bǔ)齊使之成為凸多邊形，鏈接所有點成為不相交的三角形，作三角形各邊的垂直平分線，所有平分線組成的幾何圖形就是一個簡單的泰森圖，如圖1所示。

將上圖由各三角形各邊垂直平分線劃分的區(qū)域圖形稱之為泰森圖，P{A，B，C，D，E}成為泰森圖母點幾何，根據(jù)劃分規(guī)則可以計算得到，在一個泰森圖小區(qū)域內(nèi)任意一點，它距離這個區(qū)域的母點的距離比距離其它區(qū)域內(nèi)母點的距離都近。

1.2 基于泰森圖原理分簇

1.2.1 最優(yōu)簇頭數(shù)

簇頭數(shù)量過少將導(dǎo)致整個區(qū)域內(nèi)劃分后的區(qū)域過于稀疏，其中很多簇頭收集本簇內(nèi)的數(shù)據(jù)量將會變大。簇頭數(shù)量過多，傳輸跳數(shù)隨之變多，易耗損能量。因此，簇頭數(shù)目應(yīng)加以限制，研究表明，最優(yōu)簇頭數(shù)所占總結(jié)點數(shù)量在7%～12%之間比較合適，本文采用公式（1）確定最優(yōu)簇頭的數(shù)量。

平面區(qū)域內(nèi)任意節(jié)點n產(chǎn)生的（0，1）區(qū)間的隨機(jī)值δ（n）與閾值T（n）比較，如果滿足δ（n）

通過以上對簇頭節(jié)點隨機(jī)數(shù)選取的改進(jìn)可以看出，公式（1～2）中當(dāng)E（n）值比平均水平低的幅度越大，節(jié)點n越難被選為簇頭，從而均衡了節(jié)點的區(qū)域能量，保障了網(wǎng)絡(luò)的能量均衡。

1.2.3 分簇及成簇

依據(jù)最優(yōu)簇頭數(shù)和簇頭選舉機(jī)制，我們選出了K簇頭，將其作為母點，構(gòu)建整個區(qū)域的泰森圖。構(gòu)建完畢后，得到分簇的結(jié)果，每個以簇首為母點的區(qū)域就是一個簇。

分簇完成后，需規(guī)劃其成員節(jié)點。依據(jù)泰森圖幾何區(qū)域劃分原理可以看出，在每個以簇首為母點的多邊形區(qū)域內(nèi)，成員節(jié)點距離簇首比距離其他任意簇首的距離都近，因此，我們就將處在這個多邊形區(qū)域內(nèi)的點劃分到這個簇內(nèi)。

泰森圖分簇此時可以看到它的優(yōu)點：

（1）分簇以及成簇過程容易。知道簇首節(jié)點的相對位置和簇頭數(shù)量即可分簇，分簇完成后，成簇也完成了，處在以簇首為母點的多邊形內(nèi)的節(jié)點都是成員節(jié)點。

（2）實現(xiàn)動態(tài)劃分，避免分簇不均勻。第一次分簇的結(jié)果是在最初確定簇頭數(shù)的基礎(chǔ)上確定的，它確保整個環(huán)境最優(yōu)的K個節(jié)點先當(dāng)選為簇首，雖然會造成簇頭在某一區(qū)域擁擠或稀疏的情況，但泰森圖是基于動態(tài)分簇的過程，在經(jīng)過一段時間后簇首由于失效產(chǎn)生新的簇首，整個區(qū)域就再根據(jù)新的簇首進(jìn)行區(qū)域劃分，經(jīng)歷若干次劃分后，就可以避免簇頭分布不均勻的情況。

1.3 簇內(nèi)路由

1.3.1 簇首備份

為防止頻繁地選舉簇頭，造成數(shù)據(jù)傳輸中斷，故引入簇首備份機(jī)制，在成簇階段完成后即可進(jìn)行簇首備份工作，簇首備份工作主要是在簇首節(jié)點里備份一個最優(yōu)成員節(jié)點作為下一任簇首。備份簇首選舉公式由公式（3）確定：

在公式（3）中，Nib表示鄰居節(jié)點的數(shù)量，鄰居節(jié)點越多，則該節(jié)點就越能聯(lián)系更多的節(jié)點完成數(shù)據(jù)通信；dc表示簇首與備份簇首的距離，距離越近，則越有可能成為備份簇首，新形成的泰森圖不會變化太多；a、b和c三個參數(shù)分別表示剩余能量，Nib和1/dc所占權(quán)重取決于 實際情況中考慮成為備份簇首的因素。

1.3.2 簇內(nèi)路由過程

分簇完成后即可實現(xiàn)簇內(nèi)數(shù)據(jù)的傳輸，簇成員節(jié)點發(fā)送消息報文給簇首告知要加入簇，簇首保存簇成員節(jié)點信息，采用 TDMA方式為簇成員節(jié)點進(jìn)行時隙分配。簇成員節(jié)點采集數(shù)據(jù)后在自己的時間片內(nèi)將數(shù)據(jù)傳輸給簇首，簇首將所有成員節(jié)點數(shù)據(jù)進(jìn)行綜合處理（融合或者壓縮等），最后一并轉(zhuǎn)發(fā)給其他簇首，直到傳輸給匯聚節(jié)點。

2 簇間路由建立

針對LEACH算法單跳傳輸?shù)娜毕?，本文采用的方法是進(jìn)行多跳傳輸， 簇頭將各自簇內(nèi)節(jié)點發(fā)來的數(shù)據(jù)融合，然后發(fā)給下一跳路由，數(shù)據(jù)經(jīng)過多個路由最終發(fā)到匯聚節(jié)點。進(jìn)行多跳傳輸必然涉及到跳數(shù)多少的問題，跳數(shù)多和路徑上剩余能量少都會影響到能耗均衡。因此本文采用一種基于報文查詢更新節(jié)點跳數(shù)值從而獲取Sink節(jié)點到目標(biāo)節(jié)點最小跳數(shù)的路徑路由機(jī)制，該機(jī)制不同于泛洪機(jī)制，泛洪是所有節(jié)點都接收報文消息，而基于查詢的報文規(guī)定只允許簇頭節(jié)點接收查詢報文，其他非簇頭節(jié)點可以自動根據(jù)報文頭部信息拒絕接收。

成簇機(jī)制完成后，進(jìn)入路由發(fā)現(xiàn)過程。由Sink節(jié)點發(fā)起報文查詢，網(wǎng)絡(luò)中的其他節(jié)點開始檢查是否接收此查詢報文，只有簇首會接收此報文信息，否則不接受。簇首節(jié)點接收到查詢報文后，會依據(jù)報文中的跳數(shù)數(shù)據(jù)跟自身原本存儲的跳數(shù)作對比，根據(jù)此比值結(jié)果做相應(yīng)操作。當(dāng)所有簇首節(jié)點完成報文查詢后，便更新了自己原本保存的跳數(shù)值，同時也保存了鄰居節(jié)點信息，最小跳數(shù)路徑發(fā)現(xiàn)過程結(jié)束。路由發(fā)現(xiàn)階段涉及的查詢報文結(jié)構(gòu)由幀序號、源節(jié)點ID、能量值、目的節(jié)點ID和轉(zhuǎn)發(fā)跳數(shù)組成。節(jié)點的路由表結(jié)構(gòu)包括路由序號、下一跳節(jié)點ID、下一跳節(jié)點地址和下一跳節(jié)點剩余能量。

具體的路由發(fā)現(xiàn)過程是：協(xié)議中的所有節(jié)點都有唯一的標(biāo)識號ID，初始化Sink節(jié)點的跳數(shù)為0，其余節(jié)點的跳數(shù)設(shè)為極大值。Sink節(jié)點向網(wǎng)絡(luò)廣播查詢報文，只有簇頭節(jié)點能接收到查詢報文數(shù)據(jù)，其他非簇頭節(jié)點自動丟棄該報文。當(dāng)鄰居簇頭節(jié)點接收到查詢數(shù)據(jù)包時，將數(shù)據(jù)包中的跳數(shù)值加l作為新跳數(shù)值與自身存儲跳數(shù)值相比較，若新跳數(shù)值小于原先存儲的跳數(shù)值，則用新值替換原存儲值；將數(shù)據(jù)包中的跳數(shù)值換作新值，并且用自己節(jié)點的ID號替換原來報文信息中的節(jié)點標(biāo)識號ID。把Sink節(jié)點添加到自己的路由表中。然后依據(jù)節(jié)點信息修改查詢報文的內(nèi)容，將信息包中的hop值加1，信息包中原本保存有上一個節(jié)點為止所有節(jié)點的剩余能量總和值，將這個總和值加上當(dāng)前節(jié)點剩余能量構(gòu)成一個新的總剩余能量值，之后將新的總剩余能量及其自身ID寫入消息包中，繼續(xù)廣播此查詢消息。反之不作任何處理。其它節(jié)點都做上述同樣的處理，此過程持續(xù)下去，因此每個節(jié)點均建立了到Sink節(jié)點的最小跳數(shù)路徑并記憶了各條路徑的剩余能量總和值。

當(dāng)一個簇頭節(jié)點到匯聚節(jié)點有多條相同的最小跳數(shù)時，比較這幾條路徑的總剩余能量，選擇能量最高的作為最終路徑。因此最后選擇的路徑是跳數(shù)最少路徑上總能量最高的。路徑發(fā)現(xiàn)過程結(jié)束后，數(shù)據(jù)沿反向路徑傳輸?shù)絽R聚節(jié)點。

2.1 簇間數(shù)據(jù)傳遞

在簇間，簇首節(jié)點起到傳遞數(shù)據(jù)的作用，根據(jù)路由表將數(shù)據(jù)發(fā)送到下一跳節(jié)點，直到匯聚節(jié)點。整個數(shù)據(jù)傳遞階段完成。

2.2 路由更新

路由更新會在下面兩種情形下進(jìn)行：

（1）路徑上新的簇首形成。

（2）某些簇失去作用，需重新確定路徑。

2.2.1 路徑上新的簇首形成

當(dāng)一輪數(shù)據(jù)傳輸完畢后選舉一個新的節(jié)點擔(dān)任簇首，新的簇首選舉后它將向路徑上游前一個路由節(jié)點發(fā)送自身節(jié)點信息，以保持整條路徑暢通及整條路徑跳數(shù)最少，雖然不能保證整條路徑能量最優(yōu)，但避免了頻繁的報文查詢機(jī)制。

2.2.2 某些簇失去作用

當(dāng)某個簇內(nèi)所有節(jié)點剩余能量均不足時，那么將這個簇劃分為失效簇，之前經(jīng)過這個簇的路徑將失去聯(lián)通。在這種情況下，目前采取的做法是重新啟動查詢報文機(jī)制，形成一條新的路由路徑，完成數(shù)據(jù)傳輸。

3 算法仿真及分析

現(xiàn)在對LEACH及本文提出的協(xié)議進(jìn)行仿真對比實驗，仿真工具為NS2，仿真環(huán)境為150 m×150 m區(qū)域隨機(jī)位置的300個節(jié)點，假設(shè)所有節(jié)點初始能量相同，忽略數(shù)據(jù)丟包、延遲、節(jié)點自然壞掉等因素。

圖2所示為相同時間內(nèi)節(jié)點死亡個數(shù)，在開始的一段時間內(nèi)，網(wǎng)絡(luò)消耗的能量不多，存活死亡數(shù)大致相當(dāng)，越到后面本文提出的算法越體現(xiàn)出了其優(yōu)越性，相比較LEACH算法而言，該算法在能量均衡方面做得更好，延長了網(wǎng)絡(luò)使用壽命，死亡節(jié)點更少，有更多的節(jié)點存活下來。從圖3中更可以直觀地看到，在開始階段根據(jù)報文查詢最優(yōu)路徑的過程中消耗了部分能量，使得其剩余總能量幾乎和LEACH相同，但是最優(yōu)路徑只是在開始階段啟用，到后面，本文算法在能耗均衡方面就比其它兩個算法做得好，總剩余能量總比LEACH算法多，可節(jié)省能量。經(jīng)實驗結(jié)果分析可得出結(jié)論：新算法相比LEACH算法而言，在均衡網(wǎng)絡(luò)能耗和延長網(wǎng)絡(luò)使用壽命方面發(fā)揮了一定作用。

4 結(jié) 語

本文算法先根據(jù)泰森圖分簇，在選出的簇首的基礎(chǔ)上，基于報文查詢機(jī)制搜索跳數(shù)最小、能量最優(yōu)的多跳路徑，之后在最優(yōu)路徑上傳輸數(shù)據(jù)至匯聚節(jié)點。最后在NS2環(huán)境下與LEACH算法進(jìn)行對比試驗分析，仿真結(jié)果表明，本文算法比LEACH算法在能耗均衡方面做的更好，可以有效延長網(wǎng)絡(luò)的生命期。

參考文獻(xiàn)

[1] IF Akyildiz，W Su，Y Sankarasubramanian，et al. Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.

[2] R Xiao，WU Guozheng.A survey on routing in wireless sensor net-works [J].Progress in N atural Science，2007，17（3）：261-269 .

[3] Heinzelman W R.Energy-efficient communication protocol for wireless micro sensor networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Maui： IEEE，2000： 3005-3014.

[4] Weiya W ang，Weibing Li，Dongdong Chen，et a1.Ant colony based rounting algorithm for Multi_Sink[C].WRI World Congresson，2009：423- 429.

[5] Azim，Islam.Hybrid LEACH：A relay node based low energy adaptive clustering hierarchy for wireless sensor networks[C].M alaysia International Conference on，2009：911-916 .

[6] Hou Guofeng，Tang K.W.Evaluation of LEACH protocol subject to different traffic models [C].COIN-NGNCON 2006.Hyatt R egency jeju，Korea，2006：281-283.

[7] Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks wireless communications[J].IEEE Transactions on Wireless

Communications，2002，1（4）：660-670.

[8] I Shukla，N eghanathan.PEGASIS：power-efficient gathering in sensor information system[C].In：Proceedings of the IEEE Aerospace Conference.Montana：IEEE Aerospace and Electronic Systems Society，2 002：1125-1130 .

[9] Fuad Bajaber，Irfan Awan.EECPL：Energy Effcient Clustering Protocol to Enhance Lifetime of Wireless Sensor Network[J].J Ambient Intell Human Computing，2010，1（4）：229-238.

[10] 鄒杰，史常瓊，姬文燕，等.基于粒子群優(yōu)化的非均勻分簇路由算法[J].計算機(jī)應(yīng)用，2012，32（3）：131-133.

[11] DORIG0 M，BONABEAU E，THERAUIAZ G. Inspiration for optimization from social insect behavior[J].Nature，2000：39-42.

[12] 易琳.基于共形幾何代數(shù)的多維統(tǒng)一Voronoi算法及其應(yīng)用研究[D].南京：南京師范大學(xué)，2011.