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

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

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

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

1 現有分簇算法分析

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

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

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

2 NACA算法

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

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

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

2.1 初次簇頭選擇算法

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

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

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

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

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

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

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

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

2.2 網絡維護過程

2.2.1 網絡維護過程

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

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

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

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

如果這個度量的值是一個較大的負數，那么節(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ā)現此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的值)信號，當某個簇頭發(fā)現一個節(jié)點的CID為自己，此節(jié)點檢查本簇成員，原本不在自己的簇內部成員表中，若不大于上限，則將此節(jié)點加入表中，給那個節(jié)點發(fā)送確認信號，否則發(fā)送拒絕信號［12］。當那個節(jié)點收到了確認信號，則將此節(jié)點CID改成那個簇節(jié)點;否則選收到的信號量小一點，試試能不能加入。

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

3 實例分析

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

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

圖2 初次簇頭選擇

表1 初次分簇選擇相關信息

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

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

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

表2 第一、二次分簇相關信息表

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

圖3 網絡生命周期圖

4 結束語

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

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，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網絡中基于方向性天線的分布式拓撲控制算法［J］.Journal of Software，2007，18(6):1308－1318.

［6］胡剛，謝東梅，昊元忠.無線傳感器網絡路由協議LEACH的研究和改進［J］.傳感技術學報，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］姜華，鄭春雷，劉海濤.無線傳感網中鏈路級能量有效策略的研究［J］.傳感技術學報，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］杜向黨，李亦洋，石秀華.無線傳感器網絡基于類的簇頭選擇算法改進［J］.傳感技術學報，2008，21(7):1202－1206.

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