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

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

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

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

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

1 現有分簇算法分析

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

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

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

2 NACA算法

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

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

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

2.1 初次簇頭選擇算法

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

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

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

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

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

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

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

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

2.2 網絡維護過程

2.2.1 網絡維護過程

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

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

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

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

如果這個度量的值是一個較大的負數，那么節點離開的速度就很快。反之，節點之間的距離則相對穩定。

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

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

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

2.2.2 簇的維護過程

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

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

3 實例分析

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

圖1 節點初始分布

圖2 初次簇頭選擇

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

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

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

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

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

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

圖3 網絡生命周期圖

4 結束語

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

［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.