基于簇頭選擇的移動傳感網(wǎng)拓撲控制算法研究*

章 韻，宋汝蕓，陳 志，2，3，* ，扈羅全，岳文靜

1.南京郵電大學(xué)計算機學(xué)院，南京 210003; 2.南京大學(xué)計算機軟件新技術(shù)國家重點實驗室，南 京 210093; 3.江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，南京 210003; 4.寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點實驗室，南京210003; 5. 蘇州出入境檢驗檢疫局 江蘇蘇州 ，215104)

無線傳感器網(wǎng)絡(luò)［1］是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點通過無線通信方式形成的一個多跳自組織網(wǎng)絡(luò)，可應(yīng)用于軍事、環(huán)境監(jiān)測和預(yù)報、健康護理、智能家居等領(lǐng)域，已成為計算機與通信領(lǐng)域的一個研究熱點。針對無線傳感器網(wǎng)絡(luò)能量受限的特點，要想設(shè)計能量高效的MAC協(xié)議、路由協(xié)議等，必須要設(shè)計優(yōu)化的網(wǎng)絡(luò)拓撲控制機制［2］，以提高MAC和路由協(xié)議的效率，減少干擾和系統(tǒng)吞吐量，為數(shù)據(jù)融合、目標定位等奠定基礎(chǔ)。

移動傳感網(wǎng)［3］是一類節(jié)點可以移動的無線傳感器網(wǎng)絡(luò)，可應(yīng)用于監(jiān)測野生動物的生活、追蹤病人的心跳情況等?，F(xiàn)階段移動傳感網(wǎng)研究集中于拓撲控制技術(shù)、路由技術(shù)、定位技術(shù)等，研究較多的是一個節(jié)點或幾個節(jié)點移動的情況。由于在某些情況下，如檢測大樓某些地方可能有大量有毒物質(zhì)，需較多節(jié)點不斷移動感應(yīng)信息，本文研究的是較多節(jié)點移動情況下，移動傳感網(wǎng)分簇拓撲控制算法。

1 現(xiàn)有分簇算法分析

分簇算法產(chǎn)生的層次型拓撲具有很多優(yōu)點，可以減少通信負載和節(jié)點能耗、平衡負載、延長網(wǎng)絡(luò)壽命和增強網(wǎng)絡(luò)的可擴展性等，因此分簇算法非常適合大規(guī)模的無線傳感網(wǎng)。

HD(Highest Degree)算法［4］選取具有最高度數(shù)(即具有最多鄰居節(jié)點)的節(jié)點作為簇頭。該算法的優(yōu)點在于網(wǎng)絡(luò)中簇的數(shù)目較少，從而減少了分組投遞的時延。但是，當(dāng)節(jié)點移動性較強時，簇頭更新的頻率會急劇上升，簇結(jié)構(gòu)變化較快，會引起大量維護開銷。最小ID分簇算法是一種簡單的分簇算法［5］，該算法給每個節(jié)點分配一個全網(wǎng)唯一的ID，每個節(jié)點和相鄰一跳的節(jié)點比較ID，選出相鄰節(jié)點中具有最小ID的節(jié)點作為簇頭節(jié)點。最小ID算法優(yōu)點是計算簡單，實現(xiàn)方便，算法收斂較快。但是，沒有考慮節(jié)點移動性、能量消耗等因素?，F(xiàn)階段較多將最小ID算法進行各方面的改進，但是多數(shù)只是強調(diào)某一個方面，局限性較大。分簇算法中，簇的大小也是一個很重要的考慮因素。WCA(Weighted Clustering Algorithm)［6］算法，預(yù)先指定一個簇所擁有的理想的成員個數(shù)Q，讓每個簇個數(shù)接近于Q。在選舉簇頭的時候綜合考慮簇內(nèi)節(jié)點個數(shù)、節(jié)點的移動性、節(jié)點距其一跳鄰居的距離和以及節(jié)點擔(dān)當(dāng)簇頭的時間等四個因素，算法選舉具有最小權(quán)重的節(jié)點擔(dān)當(dāng)簇頭。缺點是分簇過程開始前必須事先知道所有的權(quán)值，信息轉(zhuǎn)發(fā)開銷較大。

在綜合考慮能量、速度、簇內(nèi)限制等因素下，本文在最小ID算法和權(quán)值算法的基礎(chǔ)上，提出了一種新的分簇算法NACA(New Adaptive Clustering Algorithm)。該算法首先運用改進的最小ID算法選擇簇頭節(jié)點，在簇的維護過程中，使用的是類似權(quán)值算法在簇內(nèi)部進行簇頭選擇及更換。

2 NACA算法

最小ID算法引言中已經(jīng)介紹，針對最小ID分簇算法的不足，一種最小ID改進算法［7］被提出。該算法考慮了節(jié)點的移動性和能量消耗，使節(jié)點能量消耗更均衡，但是該算法沒有控制簇成員的數(shù)量，NACA算法改進文獻［7］的算法，在簇頭選擇中綜合考慮能量、速度和簇的大小。

基本假設(shè)和前提 ①移動節(jié)點都在區(qū)域內(nèi)隨機的移動，都為普通傳感器節(jié)點。②一定范圍內(nèi)有一個Sink即匯聚節(jié)點，此范圍內(nèi)的移動節(jié)點都可以接受到Sink節(jié)點的信號。Sink專門收集簇頭節(jié)點或者網(wǎng)關(guān)節(jié)點的信息，然后將信息融合，最后將信息經(jīng)過網(wǎng)絡(luò)傳輸?shù)娇刂浦行?，Sink節(jié)點保持固定狀態(tài)。③所有節(jié)點都具有相同的初始能量供應(yīng)e，每個普通傳感器節(jié)點的發(fā)射功率相同。

NACA算法將整個分簇過程分為初次簇頭選擇和簇的維護過程，在簇的維護過程中的簇頭的選擇采用新的算法。

2.1 初次簇頭選擇算法

利用最小ID分簇算法成簇快速、簡單、高效的優(yōu)點，NACA算法將最小ID算法改進，添加了簇頭對成員的限制，快捷又有效的完成了初次簇頭的選擇。

下面提出一新概念，響應(yīng)率。響應(yīng)率即所有傳感器節(jié)點傳送自己的ID，之后節(jié)點都收到鄰居節(jié)點的ID號，在所有包括自己節(jié)點在內(nèi)的ID號中選擇最小的，作為預(yù)簇頭節(jié)點(如果本身最小就不用傳)，傳送給那個預(yù)簇頭節(jié)點告訴之。下面給出兩個公式:

Li是節(jié)點vi的響應(yīng)率，Niy是節(jié)點vi收到的自己為預(yù)設(shè)簇頭節(jié)點的數(shù)量，Nin是節(jié)點vi的鄰居節(jié)點總數(shù)。

K是加入原簇的成功率，No是預(yù)設(shè)簇頭與最終簇頭相同的節(jié)點數(shù)，N是總節(jié)點數(shù)。

網(wǎng)絡(luò)初始化時，為每個節(jié)點分配標識符ID，保證其ID是全網(wǎng)唯一的。在傳感器節(jié)點傳遞信號然后算出自己的響應(yīng)率后，將自己的響應(yīng)率傳送給預(yù)簇頭節(jié)點，預(yù)簇頭節(jié)點比較下自己的響應(yīng)率，如果最大，將鄰居節(jié)點的響應(yīng)率從小到大排列將前g(g＜=m)［8］，存儲為自己的簇內(nèi)成員，然后給這幾個發(fā)送信號，告訴它們已經(jīng)加入本簇。

網(wǎng)絡(luò)開始時記下時間t1，每個結(jié)點計算完響應(yīng)率，亮下黃色的燈，最后一個亮黃燈的時間記下時間t2，t=t2－t1，Tt=1.5t。節(jié)點如果不是在鄰居節(jié)點中響應(yīng)率最大，第二位或者是第三位的話，過了Tt時間還是沒有收到預(yù)簇頭的信號，這時發(fā)送自己為簇頭節(jié)點信號，并將本來預(yù)設(shè)本節(jié)點為簇頭的那些節(jié)點設(shè)為成員，給這些節(jié)點發(fā)送信息。

節(jié)點在Tt時間內(nèi)收到預(yù)簇頭的信號，則將預(yù)簇頭標志改為簇頭。如果Tt時間還沒有收到預(yù)簇頭的信息，但是收到了鄰居的的某個節(jié)點的簇頭信息，申請加入此簇，那個簇頭如果收到了這個信號，再檢查下簇內(nèi)數(shù)量，如果在m內(nèi)的話，可以加入，將此節(jié)點加入表中，發(fā)送確認信息。過Tm(Tm=2Tt)時間都沒有收到任何簇頭信息，則將本節(jié)點設(shè)為簇頭，將信息發(fā)送出去。

傳感器節(jié)點每隔一定時間發(fā)送信號給Sink節(jié)點，Sink節(jié)點將接到信號的節(jié)點和信號的大小存儲在表中，然后將這個表傳遞給標識是簇頭的節(jié)點，簇頭節(jié)點收到這個表，可以查出自己是不是可以直接將信息傳遞給Sink節(jié)點，如果自己不能直接傳遞信息給簇頭，檢查表中是否有本簇成員的節(jié)點，有并選信號最大的，將之設(shè)為網(wǎng)關(guān)節(jié)點。如果沒有本簇的成員，則選某個相鄰的可以連接的簇頭節(jié)點做為本簇的網(wǎng)關(guān)節(jié)點。

2.2 網(wǎng)絡(luò)維護過程

2.2.1 網(wǎng)絡(luò)維護過程

在每個Hello Period(HP)［9］后每個簇內(nèi)部重新選擇新的簇頭。在每個HP時間內(nèi)，每個節(jié)點連續(xù)發(fā)送2個speed信號(包含節(jié)點ID和CID，有一個特殊值表明特殊信號)給周圍其他節(jié)點，每個節(jié)點可以根據(jù)連續(xù)接收的兩個speed信號強度判斷某個節(jié)點是離自己越近或者越遠，將越近的標示出來，計算出數(shù)量是N。

在每個HP時間內(nèi)，每個移動節(jié)點vi計算下面的函數(shù)值:

Evi=1－Ecurvi/Eini，Ecurvi指節(jié)點vi當(dāng)前剩余電池電量，Eini為初始能量［10］。Mvi代表 HP 時間內(nèi)vi節(jié)點相對于其相鄰節(jié)點的平均相對移動速度，G=1/N。

假設(shè)接收節(jié)點能夠檢測出接收信號的功率，通過度量從同一個發(fā)送者接收兩個連續(xù)信號強度［8］，就可以知道相對穩(wěn)定性了，其相對移動性度量定義為［11］:

如果這個度量的值是一個較大的負數(shù)，那么節(jié)點離開的速度就很快。反之，節(jié)點之間的距離則相對穩(wěn)定。

對于任意節(jié)點vi，如果其有m個相鄰節(jié)點，相鄰節(jié)點是選擇接收到的信號強度相比較大的m個節(jié)點，他就要計算m個值，通過計算m個(xi)相對0的二階矩從而得到節(jié)點vi相對m個鄰節(jié)點的平均相對移動速率:

Mvi越小說明vi相對于其鄰節(jié)點的移動性越低，相反，Mvi越大表示其相對鄰節(jié)點的移動性越高。相對于其他的計算，平均相對移動速率的計算是簡單的。

每個移動節(jié)點vi把Wvi值和自己的ID號和CID傳給自己的簇頭，簇頭節(jié)點發(fā)現(xiàn)此CID與自己相同，把信息記錄下。在HP時間后，簇頭把收集來的Wvi，選擇Wvi最小的作為簇頭，如果Wvi值相同，隨機選擇其中一個作為簇頭節(jié)點。

2.2.2 簇的維護過程

在每相隔T1(相對時間比較短)，簇頭節(jié)點發(fā)送hello信號。普通節(jié)點可能會收到其他簇頭節(jié)點的hello信號，先存儲下來，過T2時間，把這幾個信號大小(包括原簇頭)比較，試探選收到的最大信號的簇頭為本CID(若還是原簇頭信號最大，則不用修改)，暫時不修改CID，發(fā)送request(my_ID，my_CID，還包含一個標識request的值)信號，當(dāng)某個簇頭發(fā)現(xiàn)一個節(jié)點的CID為自己，此節(jié)點檢查本簇成員，原本不在自己的簇內(nèi)部成員表中，若不大于上限，則將此節(jié)點加入表中，給那個節(jié)點發(fā)送確認信號，否則發(fā)送拒絕信號［12］。當(dāng)那個節(jié)點收到了確認信號，則將此節(jié)點CID改成那個簇節(jié)點;否則選收到的信號量小一點，試試能不能加入。

每隔T3，簇頭節(jié)點檢查自己簇成員，如果某個簇成員最后一次的hello信號(或者是發(fā)送信息給簇頭)已經(jīng)離現(xiàn)在有T4，則將此節(jié)點從簇成員表中刪除。

3 實例分析

將20個傳感器節(jié)點隨機的布置在寬度為10 m×10 m的正方形廣場上，傳感器的傳輸距離是3 m，采用隨機移動方式。節(jié)點初始分布如圖1，節(jié)點很隨機的散布在區(qū)域中。第一次用最小ID改進的算法之后的拓撲圖形如圖2。表1是初次分簇的簇頭選擇相關(guān)信息。

圖1 節(jié)點初始分布

圖2 初次簇頭選擇

表1 初次分簇選擇相關(guān)信息

圖1是網(wǎng)絡(luò)初始分布，在用NACA算法的初次分簇算法后，節(jié)點的分布圖2中可以看出網(wǎng)絡(luò)的簇頭分布比較均勻，簇內(nèi)成員數(shù)合理。表1是用NACA算法的式(1)、式(2)計算出來的，K是加入原簇的成功率，從表中可以看出，在簇內(nèi)成員限制下，節(jié)點加入預(yù)設(shè)簇頭的概率比較高，從而減少了算法時間，使得網(wǎng)絡(luò)有較快較好的收斂性。

在相同的條件下，將NACA算法和HD算法、WCA算法進行比較，網(wǎng)絡(luò)的生命周期是以節(jié)點死亡數(shù)目在80%時網(wǎng)絡(luò)的持續(xù)時間。

表2是三種算法在第一、二次分簇后的相關(guān)信息的比較。從表中數(shù)據(jù)可以看出HD算法沒有考慮速度因素，所以在節(jié)點移動中的簇頭選擇則要消耗相對較多能量，某個節(jié)點可能一直擔(dān)當(dāng)簇頭節(jié)點，節(jié)點死亡率相對比較高。WCA算法中的簇頭選擇的計算較多，能量消耗較大。NACA算法考慮的是相對鄰節(jié)點的速度，兼顧能量，在第二次分簇后沒有一個節(jié)點死亡。

表2 第一、二次分簇相關(guān)信息表

圖3是在不同移動速度下的網(wǎng)絡(luò)生命周期對比圖。在靜止的狀態(tài)下(速度為0m/s)，三種算法的生命期相差不大。HD算法選擇簇頭條件簡單，所以與NACA初次算法計算量相似。隨著速度的增加，WCA算法隨著速度越來越大，交換的信息越來越多，導(dǎo)致改變較大。HD算法在節(jié)點移動時為了找到簇頭，需要發(fā)送大量信息，導(dǎo)致生命周期下降明顯，但是隨著速度增加，HD算法的選擇條件還是一樣，所以之后改變不大。NACA算法進行一次快速的簇頭選擇后，在簇維護過程中，由于簇頭節(jié)點的選擇只在簇的內(nèi)部，兼顧節(jié)點的移動、能量等因素，選擇的簇頭可以保持相對較長的時間，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)改變不會太大，隨著速度的增加，生命周期只是呈現(xiàn)緩慢的下降。

圖3 網(wǎng)絡(luò)生命周期圖

4 結(jié)束語

分簇拓撲控制是簇內(nèi)傳感器節(jié)點將信息傳輸給簇頭，簇頭節(jié)點將信息融合，然后傳送給Sink節(jié)點。NACA算法首先采用了最小ID改進的算法進行簇頭的選擇，快捷有效的進行了第一次簇頭選擇。之后的過程中簇頭更改只在簇內(nèi)進行，減少了信息的交換數(shù)量。每個簇頭節(jié)點都有個信息表進行節(jié)點之間的維護，節(jié)點可以進行隨時的擴充。更換簇頭兼顧了能量、速度等因素，簇頭能保持較長時間，網(wǎng)絡(luò)拓撲結(jié)構(gòu)改變較少，網(wǎng)絡(luò)具有較長的生命周期。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.120－250.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.An Application—Specific Protocol Architecture for Wireless Microsens or Networks［C］//IEEE Transactions on Wireless Comrnunications，2002，1(4):660－670.

［3］Howard A，Mataric M J，Sukhatme G S.Mobile Sensor Network Deployment Using Potential Fields:A Distributed Scalable Solution to the Area Coverage Problem，Proc.Int.Conf.Distributed Autonomous Robotic Systems，pp.299－308，2002.

［4］Zhao L，Lloyd E L.The Impact of Clustering in Distributed Topology Control［C］//Proc.of CIC’06(WORLDCOMP)June 2006，pp.21－27.

［5］賀鵬，李建東，陳彥輝.Ad Hoc網(wǎng)絡(luò)中基于方向性天線的分布式拓撲控制算法［J］.Journal of Software，2007，18(6):1308－1318.

［6］胡剛，謝東梅，昊元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究和改進［J］.傳感技術(shù)學(xué)報，2007，20(6):1391－1396.

［7］Chatterjee M，Das S，Turgut D.WCA:A Weighted Clustering Algorithm for Mobile Ad hoc Network［J］.Journal of Cluster Computing，2005，5:193－204.

［8］Xu Kai-xin，Hong Xiao-yan，Gerla M.An Ad Hoc Network with Mobile Backbones［C］//IEEE International Conference on Communications，2002－05.

［9］姜華，鄭春雷，劉海濤.無線傳感網(wǎng)中鏈路級能量有效策略的研究［J］.傳感技術(shù)學(xué)報，2006，19(6):2738－2742.

［10］Zhao L，Lloyd E L.Distributed Topology Control for Stationary and Mobile Ad Hoc Networks［C］//Proc.IEEE MASS’06，October 2006.

［11］杜向黨，李亦洋，石秀華.無線傳感器網(wǎng)絡(luò)基于類的簇頭選擇算法改進［J］.傳感技術(shù)學(xué)報，2008，21(7):1202－1206.

［12］程偉明，周新運.一個用于Ad Hoc網(wǎng)絡(luò)的分簇方法［J］.計算機學(xué)報，2005(5):864－869.