一種帶有可控閾值參數(shù)的分簇路由優(yōu)化算法

孫澤宇,閻 奔,聶雅琳,2,劉保羅,2,賈馥謙,來純曉

(1.洛陽理工學院 計算機與信息工程學院,河南 洛陽 471023;2.洛陽市農(nóng)牧業(yè)智能傳感網(wǎng)重點實驗室,河南 洛陽 471023;3.河南科技學院 信息工程學院,河南 新鄉(xiāng) 453003)

0 概述

傳感網(wǎng)是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點組成,通過無線通信方式形成的一個多跳的自組織網(wǎng)絡(luò)系統(tǒng),將邏輯上的信息世界與客觀上的物理世界相融合,改變了人類與自然界的交互方式。傳感網(wǎng)的應(yīng)用領(lǐng)域廣泛,如工農(nóng)業(yè)控制、智能醫(yī)療、智能物流、智能交通、搶險救災(zāi)及一些復(fù)雜的自然環(huán)境中[1-2]。在通常情況下,傳感器節(jié)點是由感知模塊、處理模塊、通信模塊和供電模塊組合而成,每個傳感器節(jié)點都兼顧數(shù)據(jù)傳輸與路由雙重功效[3-4]。傳感器節(jié)點除接收與發(fā)送數(shù)據(jù)之外,還可以對數(shù)據(jù)進行處理、存儲和融合等操作。傳感網(wǎng)是由大量傳感器節(jié)點隨機部署在監(jiān)測區(qū)域內(nèi),傳感器節(jié)點所采集的數(shù)據(jù)沿著路由所指定的方向以逐跳方式進行傳輸,直到達到匯聚節(jié)點。在傳輸過程中,數(shù)據(jù)可能被多個傳感器節(jié)點所接收并處理,當數(shù)據(jù)傳至匯聚節(jié)點后,匯聚節(jié)點對數(shù)據(jù)進行融合處理,再經(jīng)外網(wǎng)(互聯(lián)網(wǎng)或衛(wèi)星網(wǎng)絡(luò))將數(shù)據(jù)傳至管理節(jié)點,而后用戶可以通過管理節(jié)點向全網(wǎng)發(fā)布監(jiān)測信息和網(wǎng)絡(luò)配置信息。

數(shù)據(jù)融合的主要特點是去除冗余數(shù)據(jù),提高數(shù)據(jù)匹配精度,抑制網(wǎng)絡(luò)能量的快速消耗,以達到延長網(wǎng)絡(luò)生存周期的目的[5]。傳感器節(jié)點所采集的數(shù)據(jù)經(jīng)過數(shù)據(jù)融合后,其數(shù)據(jù)總量要小于原始數(shù)據(jù)總量之和,數(shù)據(jù)融合度越高,其數(shù)據(jù)匹配效果越好[6]。為進一步提高數(shù)據(jù)融合效率,減少數(shù)據(jù)融合后的誤差,需設(shè)計一種合理的路由選擇匹配方案。因此,本文提出一種帶有可控閾值參數(shù)的分簇路由優(yōu)化算法(Optimized Clustering Routing Algorithm with Controllable Threshold Parameters,CR-CTP)。

1 相關(guān)工作

分簇路由優(yōu)化算法得到國內(nèi)外諸多學者的重視,許多學者為此開展了大量研究。文獻[7]利用貪婪算法給出了相鄰節(jié)點之間最短路由的求解方法,以傳感器節(jié)點能量為研究對象,輪流使較高能量的節(jié)點作為簇首節(jié)點,最終將融合后的數(shù)據(jù)傳輸給基站。文獻[8]的基本思想是建立雙向路由鏈表,數(shù)據(jù)先沿著高級鏈表所指向的節(jié)點方向進行傳輸,當某一個節(jié)點出現(xiàn)故障時,查尋與故障節(jié)點較近的低級鏈表寫入高級鏈表當中,而后更新高級與低級鏈表完成路由選擇。文獻[9]利用路由鏈構(gòu)造一棵無向最小生成樹,通過簇內(nèi)中心節(jié)點的廣度優(yōu)先搜索得到一棵有向最小生成樹,而后利用遍歷算法對最小生成樹的所有節(jié)點進行路由選擇,最終得到簇內(nèi)所有節(jié)點的路由鏈表。文獻[10]將監(jiān)測區(qū)域劃分為若干個網(wǎng)格,以某個網(wǎng)格內(nèi)能量最高的節(jié)點充當簇首節(jié)點,由所有網(wǎng)格內(nèi)的簇首節(jié)點組成一條自由鏈路表,從而確定數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑。文獻[11]利用智能算法構(gòu)建最小生成樹,將簇內(nèi)節(jié)點能量最高的節(jié)點作為簇首節(jié)點,并以最小延時將數(shù)據(jù)發(fā)送給基站。在數(shù)據(jù)融合方面,利用簇內(nèi)成員節(jié)點自身位置信息和鄰居信息選擇上一層節(jié)點作為根節(jié)點以構(gòu)造能量均衡路由樹,最終達到全網(wǎng)能量均衡的目的。

文獻[12]通過概率模型構(gòu)建若干分簇集合,利用非線性函數(shù)關(guān)系給出傳感器節(jié)點與目標節(jié)點的最大連通集合,而后通過排序算法求解出集合中能量較高的節(jié)點充當簇首節(jié)點,并將所有集合中能量較高的節(jié)點存入鏈表中,從而獲得一條源節(jié)點到目的節(jié)點的最大連通數(shù)據(jù)融合數(shù)。文獻[13]以數(shù)據(jù)融合時間作為研究對象,給出一個基于局部數(shù)據(jù)融合信息的分布式路由算法。該算法可以為任意一棵生成樹建立最優(yōu)傳輸路徑,同時為任意一個傳感器節(jié)點指定數(shù)據(jù)時間間隙,優(yōu)化網(wǎng)絡(luò)資源。文獻[14]利用退火算法,通過傳感器節(jié)點剩余能量和數(shù)據(jù)相似性實現(xiàn)節(jié)點分簇。對于簇內(nèi)成員所采集的數(shù)據(jù)信息,則通過回歸模型獲取預(yù)測數(shù)據(jù),以此決定數(shù)據(jù)傳輸路徑。文獻[15]給出一種基于數(shù)據(jù)行為的分布式算法。該算法把靜態(tài)與動態(tài)成簇算法相融合對簇內(nèi)成員進行動態(tài)劃分,在一個周期內(nèi)所有簇內(nèi)成員節(jié)點均保持靜態(tài)。在若干個周期后,根據(jù)傳感器節(jié)點能量與歐氏距離關(guān)系,采用動態(tài)成簇方法對所有節(jié)點進行再次劃分,最終達到能量均衡的目的。文獻[16]利用傳感器節(jié)點感知能力的連續(xù)性和連通性等特性,提出多目標連續(xù)跟蹤算法。該算法通過簇間通信完成對移動目標的跟蹤,簇首節(jié)點將簇內(nèi)成員所采集的數(shù)據(jù)信息進行融合,最終由簇首節(jié)點轉(zhuǎn)發(fā)至基站。

在文獻[15-16]研究的基礎(chǔ)上,本文提出一種帶有可控閾值參數(shù)的分簇路由優(yōu)化算法。該算法借助蟻群算法,引入適應(yīng)度函數(shù)和啟發(fā)式函數(shù)可以更精準地選擇下一跳簇首的具體位置,完成網(wǎng)絡(luò)路由樹的建立與事件域節(jié)點的分布式成簇。利用可控閾值參數(shù)和變異系數(shù)對網(wǎng)絡(luò)路由所選擇最短路徑進行優(yōu)化,使得節(jié)點能量消耗較低的同時保證全網(wǎng)延時最小。通過全局信息素的更新策略抑制長鏈路的產(chǎn)生,達到均衡節(jié)點能量的目的,優(yōu)化網(wǎng)絡(luò)資源分配方案。該算法可以有效融合簇內(nèi)數(shù)據(jù),抑制全網(wǎng)冗余數(shù)據(jù)的生產(chǎn),均衡全網(wǎng)能量,進而延長網(wǎng)絡(luò)生存周期。

2 網(wǎng)絡(luò)模型建立與分析

2.1 基本假設(shè)

為方便研究,本文做以下假設(shè):

1)網(wǎng)絡(luò)初始時刻,所有節(jié)點呈現(xiàn)同構(gòu)形態(tài)且始終保持圓盤狀[17]。

2)感知半徑遠小于監(jiān)測區(qū)域邊長,即R(si)l,忽略邊界效應(yīng)。

3)全網(wǎng)中所有傳感器節(jié)點地位相同,通過定位算法可以計算出本地位置信息[18]。

4)任意傳感器節(jié)點都有唯一ID標識,并與時間保持同步。

5)在網(wǎng)絡(luò)工作階段,簇首節(jié)點能量高于其他節(jié)點能量。

6)傳感器節(jié)點之間以無線方式進行通信。

2.2 相關(guān)定義

定義1利用無向圖G=(V,E)描述網(wǎng)絡(luò)的拓撲結(jié)構(gòu),其中:VR2是歐氏距離平面上的傳感器節(jié)點集合,每個節(jié)點si表示一個傳感器節(jié)點;EV2是邊的集合,每條邊e=(si,sj)E且{si,sj}V;R(si)表示節(jié)點si的傳輸半徑,歐氏距離d(si,sj)≤R(si)。

定義2設(shè)H為簇首節(jié)點集合,稱為網(wǎng)絡(luò)支配集,記簇首節(jié)點為hi,hiH,HV。定義h(si)為節(jié)點si的簇首節(jié)點,sj{V-H},hiH,使得h(sj)=hi。

定義3定義hi的簇成員(Cluster Member,CM)集合為M(hi),∪?hi∈HM(hi)=V-H,對于Sj{V-H},如果d(sj,hi)小于sj到其他簇首的距離,則sjM(hi)。

定義4定義C(hi)={hi,M(hi)}為簇首節(jié)點,hi所在簇中所有節(jié)點的集合記為∪?hi∈HC(hi)=V。

定義5簇首之間負載平衡,即{[(1/k)-δ]≤[C(hi)/n]≤[(1/k)+δ]},δ是不平衡因子,依賴于簇首之間的實際負載能力。為均勻網(wǎng)絡(luò)能量,使得δ0。

2.3 網(wǎng)絡(luò)模型

分簇的目的是實現(xiàn)簇內(nèi)節(jié)點能量平衡,提高網(wǎng)絡(luò)容錯能力,增加連通性并減少延時,最小化簇數(shù)量,從而延長網(wǎng)絡(luò)生存周期[19-20]。分簇算法的任務(wù)是根據(jù)系統(tǒng)要求按照某種規(guī)則將網(wǎng)絡(luò)劃分成可以相互通信并覆蓋所有節(jié)點的多個簇,并在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時更新簇結(jié)構(gòu)以維護網(wǎng)絡(luò)的正常工作。分簇的基本思想是網(wǎng)絡(luò)中的地理位置相互鄰近的節(jié)點劃分為相連的區(qū)域,從而使網(wǎng)絡(luò)形成范圍較小且易于管理的邏輯結(jié)構(gòu)。傳感網(wǎng)的分簇結(jié)構(gòu)如圖1所示。

圖1 傳感網(wǎng)分簇結(jié)構(gòu)

CR-CTP算法是在分布式網(wǎng)絡(luò)中尋找最優(yōu)路徑,要求從源節(jié)點出發(fā),歷經(jīng)簇內(nèi)其他成員節(jié)點,最終到達簇首節(jié)點的過程,并滿足所有約束條件下代價最小的網(wǎng)絡(luò)路徑。本文在優(yōu)化過程中引入智能蟻群算法加以實現(xiàn)。

2.4 模型分析

根據(jù)上述假設(shè)可知,在網(wǎng)絡(luò)初始時刻,各節(jié)點能量均等。因此,各條路徑上的信息素也相等,設(shè)τij=C,C為常數(shù),其路徑上k個節(jié)點的轉(zhuǎn)移概率為:

(1)

設(shè)Set1={1,2,…,n}-Set2,表示當前節(jié)點k允許選擇的下一個目標節(jié)點,Set2表示記錄當前選中的節(jié)點集合。Set1、Set2兩個集合隨著時間的變化而動態(tài)調(diào)整。當網(wǎng)絡(luò)工作一個周期或N個周期時,路徑上的信息素會逐漸減少,直至為0,路由可持續(xù)控制參數(shù)ρ也會降低,1-ρ表示信息消失的程度,當數(shù)據(jù)從源節(jié)點到目的節(jié)點完成某一次數(shù)據(jù)傳輸時,所有路徑上的信息量要根據(jù)式(2)進行調(diào)整。

τij(t+n)=ρτij(t)+(1-ρ)Δτij

(2)

(3)

(4)

(5)

Bandwidth(PT(s,u))=min{Bandwidth(e),

n∈PT(s,u)}

(6)

(7)

(8)

其中,PT(s,u)為組播樹T(s,M)的上層源節(jié)點s至終點u的路由路徑。

3 CR-CTP算法分析與實現(xiàn)

3.1 分簇形成

分簇形成分為兩個階段:第一階段是簇首聲明階段;第二階段是簇的形成階段。在第一階段的網(wǎng)絡(luò)工作初始時刻,首先計算出監(jiān)測區(qū)域內(nèi)所有傳感器節(jié)點的數(shù)量并隨機認定簇首節(jié)點,然后這些節(jié)點向網(wǎng)絡(luò)中各數(shù)據(jù)采集節(jié)點以洪泛的方式廣播一個請求幀,其中包括該節(jié)點的ID信息與位置信息,聲明該節(jié)點為簇首節(jié)點。在簇首節(jié)點的聲明中存有一張結(jié)構(gòu)鏈表,用來記錄與該簇首節(jié)點相關(guān)的拓撲結(jié)構(gòu)的其他節(jié)點,如ID信息、位置信息、剩余能量、感知能力、距離位置等。各數(shù)據(jù)采集節(jié)點接收到簇首節(jié)點聲明信息并將其存儲在拓撲結(jié)構(gòu)鏈表中。在下一個周期內(nèi),簇首節(jié)點在本簇內(nèi)按照權(quán)值和參數(shù)變化范圍產(chǎn)生競爭。第二階段是簇的形成階段,在本階段中,其他節(jié)點收到請求幀后利用位置信息計算其與該簇首節(jié)點之間的距離,并與自身拓撲結(jié)構(gòu)表中的距離進行對比,如果小于拓撲結(jié)構(gòu)表中的距離,則將該簇首節(jié)點替換成新的簇首節(jié)點。在節(jié)點收到請求幀的同時,記錄接收到的幀的個數(shù),當其與網(wǎng)絡(luò)中的簇首數(shù)相等時,傳感器節(jié)點向簇首節(jié)點發(fā)送一個確認幀,其中包括ID和位置等信息,并停止接收請求幀。簇首節(jié)點收到確認幀后將其對應(yīng)的節(jié)點列為簇成員節(jié)點,并將位置和ID信息保存在成員列表中。經(jīng)過多個周期后,簇首節(jié)點停止廣播,每一個傳感器節(jié)點都加入到一個簇中。簇首節(jié)點可以以較大的傳輸距離直接與簇內(nèi)所有節(jié)點進行通信,但如果直接與所有簇內(nèi)成員節(jié)點進行通信,會給自身造成較重的負擔以及簇首節(jié)點與成員節(jié)點的相異性,產(chǎn)生部分非對稱鏈路。因此,在簇結(jié)構(gòu)形成階段,對簇首節(jié)點進行功率控制會消除非對稱鏈路,使網(wǎng)絡(luò)實現(xiàn)雙向連通。

定理1至少存在一條路徑在m個節(jié)點中所移動的最優(yōu)路徑概率Pr(Bm)大于或等于1-(1-cm-1p)S,其中,C=(1-ρ)L,且

證明設(shè)從源節(jié)點到目的節(jié)點所構(gòu)成的邊集為(k,l),有限多的路由路徑為u,則:

γ=min{[ηkl(u)]>β|(k,l)∈w*,u∈w*}>0

(9)

τkl(m+1)=(1-ρ)τkl(m)+ρΔτkl

(10)

(11)

由式(10)和式(11)可得:

τkl(m+1)≥(1-ρ)τkl(m)

(12)

由于τkl在m+1周期與m周期是相同的,因此通過遞歸計算可以得到式(13):

τkl(m)≥(1-ρ)m-1τkl(l)

(13)

在不失一般性的條件下,假定期望值ηkl(u)可以使用Γ=1的方法被規(guī)范化,即對所有路由邊集(k,l)及全局進行優(yōu)化,可得:

(14)

(15)

由轉(zhuǎn)移概率式(1)計算節(jié)點ru時,滿足不等式的條件為:

τkl(m)[ηkl(u)]>β

(16)

由式(9)、式(13)和式(16)可得:

(17)

由于節(jié)點之間相互獨立,因此由概率理論相關(guān)知識可得:

(18)

證明完畢。

3.2 路由恢復(fù)機制

CR-CTP采用一種分布式分簇方法。如果簇內(nèi)成員節(jié)點在正常采集數(shù)據(jù)情況下由于能量耗盡而死亡,則算法自動更新鏈表;如果簇內(nèi)節(jié)點由非正常因素死亡,如自然因素,路由鏈表不能得到及時更新,從而導(dǎo)致下一跳簇內(nèi)節(jié)點無法接收正確數(shù)據(jù),本次數(shù)據(jù)傳輸失敗,同時將非正常死亡節(jié)點ID寫入節(jié)點鏈表?；谏鲜鲈?本文采取相鄰節(jié)點代替非正常死亡節(jié)點。當出現(xiàn)非正常死亡簇內(nèi)節(jié)點時,選擇位置信息最近的簇內(nèi)鄰居節(jié)點作為下一跳節(jié)點,通過簇內(nèi)成員節(jié)點將融合數(shù)據(jù)傳輸至基站。圖2給出正常情況下CR-CTP算法構(gòu)建的分簇路由。圖3給出異常情況下CR-CTP算法構(gòu)建的分簇路由,其中“×”表示斷路。

圖2 正常情況下CR-CTP算法構(gòu)建的分簇路由

Fig.2Clustering routing constructed by CR-CTP algorithmunder normal circumstances

圖3 異常情況下CR-CTP算法構(gòu)建的分簇路由

Fig.3 Clustering routing constructed by CR-CTP algorithm under abnormal circumstances

4 實驗結(jié)果與分析

CR-CTP算法與文獻[13-14]算法在網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)能量兩個性能指標方面進行對比實驗,采用Matlab 8.0作為仿真平臺。CR-CTP是簇與可控參數(shù)相融合的算法,可以通過改變可控參數(shù)達到延長網(wǎng)絡(luò)生存周期和節(jié)省網(wǎng)絡(luò)能量開銷的目的。為方便比較,使用文獻[3]中的無線網(wǎng)絡(luò)能量消耗模型作為參考模型。每組實驗數(shù)據(jù)均為50次實驗的平均值。

4.1 網(wǎng)絡(luò)生存周期

圖4～圖7給出不同參數(shù)下的傳感器節(jié)點數(shù)量與網(wǎng)絡(luò)生存周期對比。圖4和圖5是以100 m100 m為監(jiān)測區(qū)域,可以看出,當{α=0.1,β=1.0,ρ=0.1},{α=0.3,β=1.2,ρ=0.2}和{α=0.5,β=1.5,ρ=0.3},{α=0.7,β=1.8,ρ=0.5}時,本文算法的網(wǎng)絡(luò)生存周期明顯優(yōu)于其他算法。隨著傳感器節(jié)點數(shù)量的增加,3種算法的網(wǎng)絡(luò)生存周期也隨之增加,由于CR-CTP算法是通過動態(tài)參數(shù)設(shè)定對網(wǎng)絡(luò)生存周期進行調(diào)節(jié),因此在網(wǎng)絡(luò)初始階段,CR-CTP算法的網(wǎng)絡(luò)生存周期要優(yōu)于其他兩種算法。在傳感器節(jié)點數(shù)量為30時,本文算法在不同參考作用下的網(wǎng)絡(luò)生存周期達到188 s、231 s、230 s、278 s,并趨于平衡狀態(tài),而DMOA算法和MTTA算法在節(jié)點數(shù)量為30時,網(wǎng)絡(luò)生存周期分別為102 s、161 s、135 s、201 s,與其他兩種算法相比,平均提升了12.06%。其主要原因是隨著可控參數(shù)的變化,本文算法的數(shù)據(jù)聚合能力變強,對于事件的數(shù)據(jù)融合度加大,簇內(nèi)冗余數(shù)據(jù)量減少,但DMOA算法和MTTA算法不具備參數(shù)調(diào)節(jié)能力,而是維持原來的增長趨勢。圖6和圖7的分析過程與圖4和圖5相似。

圖4 100 m×100 m區(qū)域內(nèi)路由算法在不同參數(shù)下的網(wǎng)絡(luò)生存周期變化1

Fig.4 Network lifetime varying with parameters of routing algorithms in 100 m×100 m region 1

圖5 100 m100 m區(qū)域內(nèi)路由算法在不同參數(shù)下的網(wǎng)絡(luò)生存周期變化2

Fig.5 Network lifetime varying with parameters of routing algorithms in 100 m×100m region 2

圖6 200 m200 m區(qū)域內(nèi)路由算法在不同參數(shù)下的網(wǎng)絡(luò)生存周期變化1

Fig.6 Network lifetime varying with parameters of routing algorithms in 200 m×200 m region 1

圖7 200 m200 m區(qū)域內(nèi)路由算法在不同參數(shù)下的網(wǎng)絡(luò)生存周期變化2

Fig.7 Network lifetime varying with parameters of routing algorithms in 200 m×200 m region 2

4.2 網(wǎng)絡(luò)能量

圖8 路由算法在不同參數(shù)下的網(wǎng)絡(luò)能量變化1

Fig.8 Network energy varying with parameters of routing algorithms 1

圖9 路由算法在不同參數(shù)下的網(wǎng)絡(luò)能量變化2

Fig.9 Network energy varying with parameters of routing algorithms 2

圖10 路由算法在不同參數(shù)下的網(wǎng)絡(luò)能量與運行時間變化1

Fig.10 Network energy and networkrunning time varying with parameters of routing algorithms 1

圖11 路由算法在不同參數(shù)下的網(wǎng)絡(luò)能量與運行時間變化2

Fig.11 Network energy and network running time varying with parameters of routing algorithms 2

5 結(jié)束語

本文在研究傳感網(wǎng)動態(tài)優(yōu)化路由機制的基礎(chǔ)上,提出一種帶有可控閾值參數(shù)的分簇路由優(yōu)化算法。引入智能蟻群算法,通過可控參數(shù)實現(xiàn)事件域內(nèi)的節(jié)點動態(tài)成簇,同時利用參數(shù)閾值確定分簇結(jié)構(gòu)鏈表中各節(jié)點的相關(guān)性能信息。此外,本文算法提供了一種重新選擇最優(yōu)路徑的機制,該機制可使簇首以較短的時間收集簇成員發(fā)來的各種信息,并避免移動過程的數(shù)據(jù)丟失。通過仿真實驗對網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)能量兩個指標進行對比,驗證了本文算法的有效性。后續(xù)將對智能蟻群算法中的跨層式路由選擇、連續(xù)性覆蓋控制和移動目標跟蹤等技術(shù)進行研究,進一步均衡網(wǎng)絡(luò)能耗并延長網(wǎng)絡(luò)生存周期。