基于簇頭選擇的移動(dòng)傳感網(wǎng)拓?fù)淇刂扑惴ㄑ芯?

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

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

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

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

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

分簇算法產(chǎn)生的層次型拓?fù)渚哂泻芏鄡?yōu)點(diǎn)，可以減少通信負(fù)載和節(jié)點(diǎn)能耗、平衡負(fù)載、延長網(wǎng)絡(luò)壽命和增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性等，因此分簇算法非常適合大規(guī)模的無線傳感網(wǎng)。

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

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

2 NACA算法

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

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

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

2.1 初次簇頭選擇算法

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

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

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

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

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

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

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

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

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

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

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

在每個(gè)HP時(shí)間內(nèi)，每個(gè)移動(dòng)節(jié)點(diǎn)vi計(jì)算下面的函數(shù)值:

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

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

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

對(duì)于任意節(jié)點(diǎn)vi，如果其有m個(gè)相鄰節(jié)點(diǎn)，相鄰節(jié)點(diǎn)是選擇接收到的信號(hào)強(qiáng)度相比較大的m個(gè)節(jié)點(diǎn)，他就要計(jì)算m個(gè)值，通過計(jì)算m個(gè)(xi)相對(duì)0的二階矩從而得到節(jié)點(diǎn)vi相對(duì)m個(gè)鄰節(jié)點(diǎn)的平均相對(duì)移動(dòng)速率:

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

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

2.2.2 簇的維護(hù)過程

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

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

3 實(shí)例分析

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

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

圖2 初次簇頭選擇

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

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

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

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

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

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

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

4 結(jié)束語

分簇拓?fù)淇刂剖谴貎?nèi)傳感器節(jié)點(diǎn)將信息傳輸給簇頭，簇頭節(jié)點(diǎn)將信息融合，然后傳送給Sink節(jié)點(diǎn)。NACA算法首先采用了最小ID改進(jìn)的算法進(jìn)行簇頭的選擇，快捷有效的進(jìn)行了第一次簇頭選擇。之后的過程中簇頭更改只在簇內(nèi)進(jìn)行，減少了信息的交換數(shù)量。每個(gè)簇頭節(jié)點(diǎn)都有個(gè)信息表進(jìn)行節(jié)點(diǎn)之間的維護(hù)，節(jié)點(diǎn)可以進(jìn)行隨時(shí)的擴(kuò)充。更換簇頭兼顧了能量、速度等因素，簇頭能保持較長時(shí)間，網(wǎng)絡(luò)拓?fù)浣Y(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ò)中基于方向性天線的分布式拓?fù)淇刂扑惴ǎ跩］.Journal of Software，2007，18(6):1308－1318.

［6］胡剛，謝東梅，昊元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究和改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，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í)能量有效策略的研究［J］.傳感技術(shù)學(xué)報(bào)，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ìn)［J］.傳感技術(shù)學(xué)報(bào)，2008，21(7):1202－1206.

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