基于分布式聚類的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸方法研究

丁忠祥 楊彥紅

(北京印刷學(xué)院信息工程學(xué)院,北京 102600)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是由大量靜止或移動的傳感器以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò),以協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對象的信息,并最終把這些信息發(fā)送給網(wǎng)絡(luò)的所有者[1]。無線傳感器節(jié)點(diǎn)通常部署在一些危險的或者人們不能輕易抵達(dá)的地方,執(zhí)行環(huán)境監(jiān)測任務(wù),例如化工廠的管道狀態(tài)監(jiān)測,森林中的環(huán)境監(jiān)控等,都有著廣泛的應(yīng)用前景[2]。

由于無線傳感器節(jié)點(diǎn)存儲能力、計(jì)算能力和傳輸能力受限,且通常是用微型電池提供能量,面對電池能量有限且運(yùn)行在惡劣甚至危險的自然環(huán)境中能量難以補(bǔ)充的問題,怎樣提高網(wǎng)絡(luò)中節(jié)點(diǎn)能量的有效利用率,延長無線傳感器網(wǎng)絡(luò)的生命周期,是非常重要的問題。另外網(wǎng)絡(luò)中的節(jié)點(diǎn)受各種因素的影響,集中式算法往往需要較長的時間去獲取網(wǎng)絡(luò)狀態(tài),而分布式的算法具有更好的適應(yīng)性和可擴(kuò)展性,因此研究一種分布式的聚類方法,使得節(jié)點(diǎn)聚類成簇,減少網(wǎng)絡(luò)的無線通信次數(shù),兼顧數(shù)據(jù)傳輸?shù)脱舆t的要求,使得網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)能耗均衡,達(dá)到延長整個網(wǎng)絡(luò)的生命周期的目的。

LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)中經(jīng)典的聚類協(xié)議,在節(jié)點(diǎn)內(nèi)部生成一個隨機(jī)數(shù)與當(dāng)前的閾值進(jìn)行比較,實(shí)現(xiàn)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的選擇[3]。若隨機(jī)數(shù)小于閾值,則節(jié)點(diǎn)成為簇頭節(jié)點(diǎn);非簇頭節(jié)點(diǎn)選擇最近的一個簇頭節(jié)點(diǎn)作為自身簇頭;閾值隨網(wǎng)絡(luò)的聚類次數(shù)不斷變化。在LEACH協(xié)議的基礎(chǔ)上,Manjeshwar等人提出了TEEN協(xié)議[4]。當(dāng)節(jié)點(diǎn)將采集的數(shù)據(jù)大于設(shè)置的Hard Threshold和Soft Threshold時,數(shù)據(jù)才會被發(fā)送出去,大大減少了網(wǎng)絡(luò)中需要傳輸?shù)臄?shù)據(jù)。Lindsey等人提出了PEGASIS協(xié)議,根據(jù)部署節(jié)點(diǎn)間的距離,產(chǎn)生一條數(shù)據(jù)傳輸鏈,隨機(jī)選擇鏈中的一個節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)[5]。Quan Wang等人提出了EECSR壓縮感知算法,通過備份簇頭降低轉(zhuǎn)換簇頭的開銷,從而降低網(wǎng)絡(luò)電量消耗[6]。Xiang等人提出了一種利用壓縮傳感數(shù)據(jù)的方法實(shí)現(xiàn)任意無線傳感器能量效率和恢復(fù)保真度的數(shù)據(jù)聚集方案[7]。

1 數(shù)據(jù)傳輸理論模型

無線傳感器網(wǎng)絡(luò)部署按照隨機(jī)概率散布在一個范圍確定的區(qū)域內(nèi),除基站外,所有節(jié)點(diǎn)都是對等的,通過自組織(Ad-hoc)的方式形成一個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。節(jié)點(diǎn)的發(fā)送功率決定了節(jié)點(diǎn)傳輸?shù)姆秶?在本文中假定所有節(jié)點(diǎn)都可以通過增大電量的方式和基站進(jìn)行直接通信,但是為了降低功耗采用了聚類傳輸模型來提高網(wǎng)絡(luò)的性能,以下將從傳輸模型、電量消耗模型和性能評價指標(biāo)進(jìn)行表述。

1.1 無線傳感器網(wǎng)絡(luò)聚類傳輸模型

假定網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)都直接向基站發(fā)送數(shù)據(jù),當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較大時,將會產(chǎn)生信道爭用的情況,大量的信息傳輸會發(fā)生碰撞從而使網(wǎng)絡(luò)無法正常地工作。因此采用聚類的方式,將節(jié)點(diǎn)劃分為不同的區(qū)域,如圖1所示,每個節(jié)點(diǎn)是一個小圓點(diǎn),將網(wǎng)絡(luò)范圍劃分成若干區(qū)域,在圖中用虛線劃分不同的區(qū)域,使得每個區(qū)域的節(jié)點(diǎn)數(shù)盡可能相同。每個區(qū)域內(nèi)選取一個簇頭節(jié)點(diǎn),在圖1中以黑色的小圓點(diǎn)表示。簇頭節(jié)點(diǎn)負(fù)責(zé)收集自己區(qū)域內(nèi)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù),在節(jié)點(diǎn)內(nèi)部將采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)的聚合,然后通過簇頭節(jié)點(diǎn)直接發(fā)送給基站(圖中左下角黑色小方塊)。簇內(nèi)節(jié)點(diǎn)進(jìn)行通信時,可以降低發(fā)送功率,減少簇與簇之間的干擾,同時還可以增加節(jié)點(diǎn)工作壽命。

圖1 聚類傳輸模型示意圖

1.2 電量消耗模型

傳感器節(jié)點(diǎn)在感測、接收和傳輸數(shù)據(jù)時消耗能量。不同的運(yùn)行方式對傳感器節(jié)點(diǎn)的能耗影響較大。一般來說,傳感器節(jié)點(diǎn)有四種模式,即空閑、發(fā)送、接收和休眠模式。然而,大部分能量消耗在傳輸和接收數(shù)據(jù)上。Shih等人在2002年的Mobicom會議上指出,傳感器的大部分能量消耗在通信模塊中,而在睡眠模式下的能量消耗通?？梢院雎圆挥?jì)[8]。因此,在降低通信成本的前提下,可以大大提高能源利用率。

本文采用一階無線傳輸模型[3,6]來描述節(jié)點(diǎn)傳輸?shù)哪芎?即向距離為d的節(jié)點(diǎn)傳輸一個k-bit大小的數(shù)據(jù)包需要消耗的能量為:

接收這個數(shù)據(jù)需要消耗的能量為:

其中,Eelec是節(jié)點(diǎn)無線通訊消耗的能量,εamp是信號放大器消耗的能量。

由于在測試的過程中,各個算法依據(jù)初始條件的設(shè)置,所發(fā)送的數(shù)據(jù)包的大小的差異并不大,因此在本論文的仿真過程中假定k為固定值。當(dāng)簇頭節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)時,距離是能量消耗的主要影響的變量。

1.3 性能評價指標(biāo)

在傳感器網(wǎng)絡(luò)中,網(wǎng)絡(luò)的性能包括低延遲,抗干擾、低功耗等,存在不同的計(jì)算公式和評價指標(biāo)。在本文中將采用以下性能評價指標(biāo)并給出計(jì)算依據(jù)。

(1)存活節(jié)點(diǎn)數(shù)量

存活節(jié)點(diǎn)數(shù)量(Number of Available Nodes)是統(tǒng)計(jì)網(wǎng)絡(luò)中可以運(yùn)行的節(jié)點(diǎn)的數(shù)量。在網(wǎng)絡(luò)運(yùn)行的時刻t,節(jié)點(diǎn)v的電池電量vele大于正常工作的電池電量最小閾值Emin,則認(rèn)為該節(jié)點(diǎn)v是存活的。

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

網(wǎng)絡(luò)生命周期(Network Lifetime)是表示網(wǎng)絡(luò)從開始運(yùn)行到結(jié)束的周期。網(wǎng)絡(luò)開始運(yùn)行開始記為時刻t1。當(dāng)節(jié)點(diǎn)中所有的節(jié)點(diǎn)不是存活狀態(tài)或以一定比例存活節(jié)點(diǎn)數(shù)量的時刻為t2。網(wǎng)絡(luò)生命周期則是t1和t2的差值。

(3)平均最大數(shù)據(jù)延遲

平均最大數(shù)據(jù)延遲(AverageMaximumData Delay)是表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)據(jù)達(dá)到基站的平均最大延遲。一個節(jié)點(diǎn)v周期性產(chǎn)生數(shù)據(jù)包p1,p2,…,pn。產(chǎn)生這些數(shù)據(jù)包的時間分別為Gp1,Gp2, … ,Gpn。這些數(shù)據(jù)包達(dá)到基站的時間分別為Rp1, Rp2, … ,Rpn,則節(jié)點(diǎn)的最大數(shù)據(jù)延遲vdelay是時間差值的最大值。

對于全網(wǎng)來說就是所有節(jié)點(diǎn)的最大數(shù)據(jù)延遲的平均值為:

2 基于分布式聚類的數(shù)據(jù)傳輸方法

本文提出了一種基于分布式聚類的數(shù)據(jù)傳輸方法,無線傳感器網(wǎng)絡(luò)周期性的進(jìn)行工作,每個周期分為節(jié)點(diǎn)聚類階段和穩(wěn)定傳輸階段。在節(jié)點(diǎn)聚類階段,傳感器節(jié)點(diǎn)采用剩余電量聚類算法(Residual Electricity Clustering Algorithm, RECA)選取合適的簇頭節(jié)點(diǎn),使得網(wǎng)絡(luò)中的節(jié)點(diǎn)被劃分成各個分簇中;在穩(wěn)定傳輸階段,簇內(nèi)節(jié)點(diǎn)將采集到的數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn),簇頭節(jié)點(diǎn)再將接收到的數(shù)據(jù)傳輸?shù)交局小?/p>

2.1 節(jié)點(diǎn)聚類過程

節(jié)點(diǎn)進(jìn)入聚類階段時,產(chǎn)生一個廣播隨機(jī)數(shù)定時器,觸發(fā)時間事件后,節(jié)點(diǎn)廣播自己的節(jié)點(diǎn)信息,其中節(jié)點(diǎn)信息不限于自己的剩余電量。其他時隙節(jié)點(diǎn)處于接收狀態(tài),接收其它節(jié)點(diǎn)的廣播信息,以獲取周圍節(jié)點(diǎn)的最新狀態(tài)。再等待廣播消息一段時間后,節(jié)點(diǎn)將按照下一節(jié)中描述的RECA過程,先對周圍鄰居節(jié)點(diǎn)的狀態(tài)進(jìn)行分析,從中選擇一個合適的節(jié)點(diǎn)作為自身的簇頭節(jié)點(diǎn)。當(dāng)一個節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)或者簇內(nèi)節(jié)點(diǎn)數(shù)量發(fā)生變化時,節(jié)點(diǎn)需要重新廣播自己簇內(nèi)節(jié)點(diǎn)信息。

節(jié)點(diǎn)聚類周期結(jié)束后,網(wǎng)絡(luò)中所有的節(jié)點(diǎn)被劃分在各個分簇當(dāng)中。每個分簇中的非簇頭節(jié)點(diǎn)在感知周圍的環(huán)境信息后,將信息發(fā)送給簇頭節(jié)點(diǎn);簇頭節(jié)點(diǎn)將自身的感知信息與接收到的其他節(jié)點(diǎn)的感知信息進(jìn)行聚合,并發(fā)送給基站。

2.2 剩余電量聚類算法

剩余電量聚類算法是一種節(jié)點(diǎn)根據(jù)周圍鄰居節(jié)點(diǎn)的狀態(tài)信息(包括是否為簇頭節(jié)點(diǎn)、剩余電量、簇內(nèi)節(jié)點(diǎn)數(shù)量等信息),從中選取出一個簇頭節(jié)點(diǎn),完成聚類的方法。節(jié)點(diǎn)開始聚類時,周圍鄰居節(jié)點(diǎn)有以下兩種狀態(tài):

(1)鄰居節(jié)點(diǎn)中沒有簇頭節(jié)點(diǎn)

如圖2中a所示,節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)中沒有簇頭節(jié)點(diǎn),則建立新的簇,并比較節(jié)點(diǎn)A與周圍鄰居節(jié)點(diǎn)的剩余電量。假設(shè)節(jié)點(diǎn)A的剩余電量最多,則節(jié)點(diǎn)A改變自身狀態(tài),成為新分簇的簇頭節(jié)點(diǎn),廣播自己新的狀態(tài)信息,如圖2中b所示。假設(shè)鄰居節(jié)點(diǎn)B的剩余電量最多,則節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送入簇請求包;節(jié)點(diǎn)B在收到請求包后,改變自身狀態(tài),成為新分簇的簇頭節(jié)點(diǎn),廣播自己新的狀態(tài)信息,將節(jié)點(diǎn)A加入自己的簇內(nèi),并回復(fù)應(yīng)答包;節(jié)點(diǎn)A收到應(yīng)答包后,確認(rèn)加入分簇成功后,將節(jié)點(diǎn)B設(shè)為自己的簇頭節(jié)點(diǎn),如圖2中c所示。

圖2 簇頭形成的過程類別情況

(2)鄰居節(jié)點(diǎn)中有簇頭節(jié)點(diǎn)

如圖3中a所示,節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)中有簇頭節(jié)點(diǎn),分別為簇頭節(jié)點(diǎn)B、C、D、E。節(jié)點(diǎn)A依次向周圍分簇的簇頭節(jié)點(diǎn)發(fā)送入簇請求包,直到成功加入一個分簇。簇頭節(jié)點(diǎn)在收到入簇請求包后,若簇內(nèi)節(jié)點(diǎn)個數(shù)未達(dá)到最大值,則入簇成功,簇頭節(jié)點(diǎn)將節(jié)點(diǎn)A加入簇內(nèi);若簇內(nèi)節(jié)點(diǎn)個數(shù)達(dá)到最大值,則入簇失敗。簇頭節(jié)點(diǎn)向節(jié)點(diǎn)A發(fā)送應(yīng)答包,告知其入簇結(jié)果。假設(shè)節(jié)點(diǎn)A向簇頭節(jié)點(diǎn)D發(fā)出入簇請求后加入分簇成功,則節(jié)點(diǎn)A將簇頭節(jié)點(diǎn)D設(shè)為自己的簇頭節(jié)點(diǎn),如圖3中b所示。

圖3 節(jié)點(diǎn)加入周圍簇過程

RECA偽代碼如算法1所示。算法的輸入為node、neighbor、maxMembers,分別代表的是進(jìn)行聚類的節(jié)點(diǎn)編號、周圍鄰居節(jié)點(diǎn)的集合和簇內(nèi)最大成員數(shù)。算法的輸出為true,即聚類完成。首先,將節(jié)點(diǎn)node設(shè)為當(dāng)前剩余電量最多的節(jié)點(diǎn)(行2、3)。隨后開始對所有鄰居節(jié)點(diǎn)進(jìn)行遍歷(行4),若i所代表的鄰居節(jié)點(diǎn)是簇頭節(jié)點(diǎn)且簇內(nèi)的節(jié)點(diǎn)數(shù)量小于簇內(nèi)最大成員數(shù)(行5、6),則節(jié)點(diǎn)node將其i所代表的節(jié)點(diǎn)設(shè)為簇頭節(jié)點(diǎn)(行8),i所代表的節(jié)點(diǎn)的簇內(nèi)節(jié)點(diǎn)個數(shù)加一(行9),節(jié)點(diǎn)node聚類完成(行9);若i所代表的鄰居節(jié)點(diǎn)不是簇頭節(jié)點(diǎn)(行11),則將其剩余電量與當(dāng)前最大剩余電量對比,如果i所代表的鄰居節(jié)點(diǎn)的剩余電量大于當(dāng)前剩余電量最多的節(jié)點(diǎn)(行12),則i所代表的鄰居節(jié)點(diǎn)被視為當(dāng)前剩余電量最多的節(jié)點(diǎn)(行13、14)。若遍歷完所有鄰居節(jié)點(diǎn)后,未能完成聚類,則將當(dāng)前剩余電量最多的節(jié)點(diǎn)設(shè)為的簇頭節(jié)點(diǎn),其簇內(nèi)節(jié)點(diǎn)數(shù)加一(行18、19),節(jié)點(diǎn)node將其設(shè)置自身的簇頭節(jié)點(diǎn)(行20),聚類完成(行21)。

算法1 分布式節(jié)點(diǎn)聚類方法輸入:node節(jié)點(diǎn)號,neighbor鄰居節(jié)點(diǎn)集合,maxMembers簇內(nèi)最大成員數(shù)輸出:聚類結(jié)果1: function selectClusterHead(node,neighbor,maxMembers)2: maxEnergy ← node.energy 3: maxEnergyNode ← node 4: for each i ∈neighbor do 5: if i.isClusterHead then 6: if i.membersNum < maxMembers then 7: node.clusterHead ← i 8: i.membersNum++9: return true 10: end if 11: else 12: if i.energy > maxEnergy then 13: maxEnergy ← i.energy 14: maxEnergyNode ← i 15: end if 16: end if 17: end for 18: maxEnergyNode.isClusterHead ← true 19: maxEnergyNode. membersNum++20: node.clusterHead ← maxEnergyNode 21: return true 22: end function

3 算法測試驗(yàn)證

3.1 測試環(huán)境描述

為了將RECA和其他算法進(jìn)行比較,使用java實(shí)現(xiàn)了RECA、LEACH、TEEN和PEGASIS。表1給出了在仿真測試時,網(wǎng)絡(luò)的相關(guān)參數(shù)。網(wǎng)絡(luò)范圍是指節(jié)點(diǎn)散布的平面空間范圍,這里全部的算法都是100*100。網(wǎng)絡(luò)節(jié)點(diǎn)個數(shù)是網(wǎng)絡(luò)中初始化的節(jié)點(diǎn)個數(shù),這里假設(shè)節(jié)點(diǎn)個數(shù)是100。從這兩個條件可以看出,網(wǎng)絡(luò)基本上是屬于一種稀疏狀態(tài),因此在廣播鄰居信息、節(jié)點(diǎn)信息和簇信息時,發(fā)生碰撞的概率并不大,可以依靠重傳機(jī)制予以避免。數(shù)據(jù)生成周期是節(jié)點(diǎn)每隔一定時間就獲取一次傳感的數(shù)據(jù),這里假定所有算法的模擬測試中都是每隔30個時隙產(chǎn)生一個數(shù)據(jù)。節(jié)點(diǎn)聚類周期設(shè)置的都是1000個時隙,也就是1000個時隙之后要重新選取簇頭。簇內(nèi)最大節(jié)點(diǎn)數(shù)限制了一個簇內(nèi)所擁有的簇內(nèi)成員,RECA中規(guī)定不超過5個。LEACH和TEEN都需要設(shè)置網(wǎng)絡(luò)簇頭節(jié)點(diǎn)的百分比,這里我們設(shè)定的是0.2,在RECA中簇頭節(jié)點(diǎn)的百分比也近似是這個比例。初始能量是節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行前的最大電量,隨著發(fā)送和接收,能量值逐漸降低。

表1 網(wǎng)絡(luò)運(yùn)行參數(shù)

3.2 測試結(jié)果與分析

本文對所有協(xié)議進(jìn)行100次的仿真實(shí)驗(yàn),TEEN協(xié)議采用的是hard模式。結(jié)果如下:

圖4為各協(xié)議在仿真時,節(jié)點(diǎn)存活數(shù)量隨時間變化情況對比圖。在存活節(jié)點(diǎn)數(shù)量為100的時候,RECA的生命周期最長。LEACH協(xié)議在進(jìn)行簇頭節(jié)點(diǎn)選擇的時候,依賴于節(jié)點(diǎn)生成的隨機(jī)數(shù),存在有簇頭節(jié)點(diǎn)數(shù)量過多或過少、簇頭節(jié)點(diǎn)分布不均勻的問題,導(dǎo)致一些節(jié)點(diǎn)能量消耗較快而過早死亡。TEEN協(xié)議在LEACH的基礎(chǔ)上增加了Hard Threshold和Soft Threshold,減少了節(jié)點(diǎn)發(fā)送的數(shù)據(jù)量,但仍然存在同樣的問題。PEGASIS協(xié)議將所有節(jié)點(diǎn)連成一條鏈,位于鏈的中間區(qū)域的節(jié)點(diǎn)需要進(jìn)行大量的數(shù)據(jù)轉(zhuǎn)發(fā)工作,加劇了節(jié)點(diǎn)的死亡。

圖4 存活節(jié)點(diǎn)數(shù)量對比

圖5為各協(xié)議在仿真時,基站收到的信息量隨時間變化情況對比圖。圖中可以看出,在網(wǎng)絡(luò)運(yùn)行相同時間的情況下,采用RECA時,基站接收的信息量最大。LEACH協(xié)議在網(wǎng)絡(luò)運(yùn)行前期與RECA的信息發(fā)送量大致相同,但隨著網(wǎng)絡(luò)中存活節(jié)點(diǎn)的減少,需要發(fā)送信息的也在減少。TEEN協(xié)議主要是通過減少信息的發(fā)送來延長網(wǎng)絡(luò)的生命,因此基站接收的信息量較少。PEGASIS協(xié)議同樣由于節(jié)點(diǎn)的大量死亡,信息發(fā)送量減少。

圖5 基站接收的信息量對比

圖6為各協(xié)議在仿真時,網(wǎng)絡(luò)平均最大數(shù)據(jù)延遲對比圖。RECA相比于其他聚類協(xié)議,有著較低的平均最大數(shù)據(jù)延遲,節(jié)點(diǎn)的感知數(shù)據(jù)能較快發(fā)送到基站中。LEACH協(xié)議的平均最大數(shù)據(jù)延遲達(dá)到2000以上,PEGASIS的延遲更大。因此,RECA具有高效的傳輸性能。

圖6 平均最大數(shù)據(jù)延遲對比

4 總結(jié)

無線傳感器網(wǎng)絡(luò)的分布式數(shù)據(jù)高效傳輸一直以來都影響大規(guī)模網(wǎng)絡(luò)部署應(yīng)用。本論文在以剩余電量作為重要的指標(biāo)在聚類階段完成選取簇頭和形成簇的過程,提出了基于分布式聚類的數(shù)據(jù)傳輸方法。通過仿真測試,該方法數(shù)據(jù)延遲非常低,網(wǎng)絡(luò)生命周期達(dá)平均水平,網(wǎng)絡(luò)整體電池消耗速率均勻,能夠高效地進(jìn)行數(shù)據(jù)傳輸。