無線傳感器網(wǎng)絡(luò)基于泰森圖分簇的路由算法

梅馮陽

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

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

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

0 引 言

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

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

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

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

1 泰森圖分簇算法

1.1 泰森圖介紹

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

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

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

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

1.2 基于泰森圖原理分簇

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

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

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

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

1.2.3 分簇及成簇

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

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

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

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

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

1.3 簇內(nèi)路由

1.3.1 簇首備份

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

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

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

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

2 簇間路由建立

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

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

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

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

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

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

2.2 路由更新

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

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

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

2.2.1 路徑上新的簇首形成

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

2.2.2 某些簇失去作用

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

3 算法仿真及分析

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

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

4 結(jié) 語

本文算法先根據(jù)泰森圖分簇，在選出的簇首的基礎(chǔ)上，基于報(bào)文查詢機(jī)制搜索跳數(shù)最小、能量最優(yōu)的多跳路徑，之后在最優(yōu)路徑上傳輸數(shù)據(jù)至匯聚節(jié)點(diǎn)。最后在NS2環(huán)境下與LEACH算法進(jìn)行對(duì)比試驗(yà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ì)算機(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.