一種帶有可控閾值參數的分簇路由優化算法

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

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

0 概述

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

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

1 相關工作

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

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

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

2 網絡模型建立與分析

2.1 基本假設

為方便研究,本文做以下假設:

1)網絡初始時刻,所有節點呈現同構形態且始終保持圓盤狀[17]。

2)感知半徑遠小于監測區域邊長,即R(si)l,忽略邊界效應。

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

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

5)在網絡工作階段,簇首節點能量高于其他節點能量。

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

2.2 相關定義

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

定義2設H為簇首節點集合,稱為網絡支配集,記簇首節點為hi,hiH,HV。定義h(si)為節點si的簇首節點,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)}為簇首節點,hi所在簇中所有節點的集合記為∪?hi∈HC(hi)=V。

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

2.3 網絡模型

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

圖1 傳感網分簇結構

CR-CTP算法是在分布式網絡中尋找最優路徑,要求從源節點出發,歷經簇內其他成員節點,最終到達簇首節點的過程,并滿足所有約束條件下代價最小的網絡路徑。本文在優化過程中引入智能蟻群算法加以實現。

2.4 模型分析

根據上述假設可知,在網絡初始時刻,各節點能量均等。因此,各條路徑上的信息素也相等,設τij=C,C為常數,其路徑上k個節點的轉移概率為:

(1)

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

τ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)的上層源節點s至終點u的路由路徑。

3 CR-CTP算法分析與實現

3.1 分簇形成

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

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

證明設從源節點到目的節點所構成的邊集為(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的方法被規范化,即對所有路由邊集(k,l)及全局進行優化,可得:

(14)

(15)

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

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

(16)

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

(17)

由于節點之間相互獨立,因此由概率理論相關知識可得:

(18)

證明完畢。

3.2 路由恢復機制

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

圖2 正常情況下CR-CTP算法構建的分簇路由

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

圖3 異常情況下CR-CTP算法構建的分簇路由

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

4 實驗結果與分析

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

4.1 網絡生存周期

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

圖4 100 m×100 m區域內路由算法在不同參數下的網絡生存周期變化1

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

圖5 100 m100 m區域內路由算法在不同參數下的網絡生存周期變化2

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

圖6 200 m200 m區域內路由算法在不同參數下的網絡生存周期變化1

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

圖7 200 m200 m區域內路由算法在不同參數下的網絡生存周期變化2

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

4.2 網絡能量

圖8 路由算法在不同參數下的網絡能量變化1

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

圖9 路由算法在不同參數下的網絡能量變化2

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

圖10 路由算法在不同參數下的網絡能量與運行時間變化1

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

圖11 路由算法在不同參數下的網絡能量與運行時間變化2

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

5 結束語

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