基于WSNs智能交通系統的非均勻分簇路由

游子毅，章俊華，陳世國，王 義

（1.貴州省機械電子產品質量監督檢驗院，貴州 貴陽550081；2.貴州師范大學 物理與電子科學學院，貴州 貴陽550001；3.貴州省教育廳汽車電子技術特色重點實驗室，貴州 貴陽550001）

0 引 言

路由協議對于交通信息采集中的網絡傳輸性能尤為關鍵。由于分簇路由協議具有節能性好等特點，現已成為重點研究的一 類 無 線 傳 感 器 網 絡 （WSNs）路 由 協 議［1，2］。LEACH［3］是最早出現的均勻分簇路由協議，但是該類分簇結構也帶來了一些問題。研究結果表明，隨機選擇簇頭和簇內單跳路由會增加節點能耗并限制網絡規模。此外，在規模較大的WSNs中，簇頭間采用多跳通信方式與Sink節點 通 信，從 而 造 成 “熱 區”問 題［4，5］。Heed 是 基 于LEACH 改進的成簇協議，主要在簇首選舉中加入能量因素考慮［6］；TEEN［7］的主要框架和LEACH 一致，是一種應對時間緊急事件的響應式路由協議。LEACH，Heed 和TEEN 協議都沒考慮到 “熱區”問題。EEUC 是一種非均勻成簇路由協議［8］，其根據距離Sink節點的遠近由近至遠構造由小到大的簇半徑，使靠近Sink節點的簇的成員數少于遠離Sink節點的簇，從而減輕靠近Sink節點的簇頭能量的消耗。然而，EEUC算法適合分布較均勻的情況。如果在實際的應用環境中節點分布不均勻，EEUC 還是無法緩解 “熱區”問題。

在智能交通場景中，傳感器節點多，采集的原始數據量較大。此外，車輛節點具有高移動性，使得車輛傳感網的節點分布情況比靜態傳感器網絡具有更頻繁的變化。因此，現有的分層WSNs路由協議都不太適合智能交通環境。本文提出了一種能量均衡的非均勻分簇路由協議 （UCSNP）用于智能交通系統。該協議著重對非均勻成簇、簇間路由以及簇半徑調整進行討論。結合智能交通的特點，UCSNP建立鏈式結構［9］和分簇結構混合的通信方式，并在這種通信方式下，通過混合蛙跳算法［10］對簇間路由進行優化，動態調整簇通信半徑。UCSNP 使網絡拓撲更加合理，提高網絡的生存周期并且減短了網絡的收斂時間。本文在文獻 ［11］基礎之上解決基于WSNs的交通信息傳輸的“熱區”問題。

1 混合蛙跳算法

首先，隨機生成F 個解 （青蛙）作為初始種群。第i個解可表示為d 維問題的解Xi＝｛xi1，xi2，...，xid｝。其適應度可表示為Yi＝f（Xi），其中Yi為目標函數。F 只青蛙按Y值降序排列，并記錄具有最好適應度的解Xg為整個種群中的最好解。然后把整個種群平均劃分到m 個包含s 個解的子種群：F ＝m×s。在每個子種群中，將適應度最好的解和最差的解分別記為Xb和Xw。由每個子種群通過局部搜索對最差解Xw進行更新

式中：dj表示分量j 上移動的距離；rand（）是0到1之間的隨機數；Dmax是青蛙允許移動的最大距離。當本輪局部搜索完成后，所有簇群的青蛙重新混合、排序并劃分新簇群，開始下一輪的局部搜索。不斷循環直到達到迭代次數。

2 UCSNP協議

2.1 網絡模型與分簇策略

在智能交通的應用中無線傳感器網絡結構設計由車輛之間組成的移動的、分布式自組織形式與公路設施上傳感器間組成的固定無線網絡結構相結合［12］。存在兩種信息通信 類 型，一 種 稱 為 車—車 協 同 系 統 Vehicle－to－Vehicle（V2V），即車輛配備傳感器以進行車輛之間的信息交互，這對于避免如交通堵塞等嚴重情況至關重要，另一種稱為車—路協同系統Vehicle－to－Infrastructure（V2I），即車輛與安裝在公路固定設施上的傳感器之間進行信息傳輸，這對于在道路特別是高速公路上交通情況的及時反饋尤為重要。

假定在二維平面區域：Z2＝｛（x，y），0≤x，0≤y｝，所有的傳感器節點 （車輛和固定設施）隨機分布。該區域可通過具體的原則和方法網格化［13，14］，其格狀網每個正方形小區域為α×α，邊長α根據應用任務的求解精度而定。假設兩個節點的位置分別為LP（xi，yi）和LQ（xj，yj），則兩個位置之間的距離為

將該區域劃分成n個區，n的數量由該區域的長度和分區節點的通信半徑確定。Sink節點部署在區域外的一個固定位置。為了實現能耗均衡，距離Sink節點近的分區內的簇數目應多于遠的分區。由于交通環境下車輛節點的高移動性，每個簇的簇頭由Sink節點指定為該簇區內的一個固定設施。其它節點與簇頭之間單跳通信，簇頭可通過調整通信半徑控制成員數以減小通信負載。對于相鄰的兩個簇簇頭CHi和CHj，則D（CHi，CHj）≥RCHi＋RCHj，其中D（CHi，CHj）表示CHi與CHj之間的距離，RCHi和RCHj表示相應的半徑。此外，不在任何一個簇通信半徑覆蓋下的傳感器節點可采用鏈式結構［9］的多跳通信，基于貪婪算法選擇信號強度最好的中繼節點傳送感知數據，以此方式將數據傳遞至距離最近的簇內的成員節點。該節點作為鏈首進行一次數據融合后，將數據包發送至簇頭，如圖1所示。

圖1 鏈式和分簇混合的網絡結構

網絡中的每一個傳感器 （車輛和路邊設施）都有一個唯一的標志ID，由可信中心 （trusted authority）負責對節點認證、注冊并授權。節點可通過ID 號和TA 簽發的數字證書相互驗證身份。

節點能量模型描述如下，節點發射l比特數據到距離為d 的位置，則發送端的能量為

接收端的能量為

其詳細說明參見文獻 ［8］。

2.2 簇間路由初始化參數

簇區內簇頭CHi周期性地向其他成員節點發送詢問報文REQ 以同步時間。每一輪采樣l（1≤l≤N），簇頭CHi將接收到的感知數據進行融合，生成新的數據包傳送至Sink節點。傳送時，CHi會選擇相鄰簇頭作為中繼節點轉發數據包。因此，從源點CHi到Sink節點之間可生成一條或多條不同的路徑。除與Sink節點一跳距離的簇外，簇頭CHi可隨機生成F 只青蛙，每只青蛙個體表示一條從CHi到Sink節點的可行路徑，即P ＝｛P1，P2，...，Pd｝，其中d表示解空間的維數，Pi＝｛CHi，...，CHx，Sink｝。P 即為生成的初始群體。

青蛙個體的適應度主要依據傳輸數據的能耗和可靠性來計算。定義適應度函數為

式 （7）中，α1＋α2＋α3＝1；CHi∈Pi表示CHi是路徑Pi上的一個節點；nk∈ci表示nk是簇ci內成員節點；ERX（CHi，nk）／ETX（CHi，nk）表示簇頭CHi對成員節點nk接收／發送數據所消耗的能量；CHj∈adj（CHi）表示CHj是CHi的相鄰簇頭；ERX（CHi，CHj）／ETX（CHi，CHj）表示CHi對CHj接收／發送數據所消耗的能量；EDA（CHi）表示CHi融合數據所消耗的能量；Ecomput（CHi）表示CHi進行相應計算所消耗的能量。

函數fi描述路徑Pi的總體能量消耗，包括該路徑上各節點的計算代價和通信負荷。每一輪數據采樣，簇頭CHi接收簇內成員節點和來自相鄰簇頭的消息，計算出各能耗參數并更新從該簇頭到Sink 節點的每條路徑的代價。其中，系數α1，α2，α3為各種參數在節點總體能耗中的比重。可見，簇間最優路徑問題等于青蛙最優解的問題。最優解問題是目標函數E（Pi）取最小值，即fi取最大值。

CHi將生 成 的 青 蛙 適 應 度 按 降 序 排 列 成P1，P2，...，PF，并劃分成m 個種群Y1，Y2，...，Ym，構造子種群。m 的數值由P 中源點的下一跳節點的個數來決定。每個子種群包含s只青蛙，滿足下列關系

2.3 簇間路由優化

（1）局部優化

將青蛙種群劃分的多個子種群分別進行局部搜索。

步驟1 在第l輪（1≤l≤N），計算子種群Yi的適應度f（i）k，以概率p 一一進行更新，并找出最優解Pb和最差解Pw。

步驟2 Pb與Pw進行交叉替換操作，即查找兩條路徑中的相同節點，從選中的一個公共節點開始到下一個公共節點對Pw進行鏈路替換。如果兩條路徑僅有一個相同節點，則取Sink節點為下一個公共點。

例如：Pw＝｛CHs，CH2，CH3，CH5，CH7，Sink｝

Pb＝｛CHs，CH3，CH5，CH6，Sink｝

經過交叉后，Pw變為

Pw＝｛CHs，CH3，CH5，CH6，Sink｝

步驟3 計算交叉后最差解Pw的適應度newf（i）w，如果newf（i）w大于替換前最差解適應度f（i）w，則替換成功，否則，交叉失敗。如果交叉失敗，則再選用全局最優解Pg對Pw進行交叉替換。如果newf（i）w仍沒有得到改進，則隨機產生一個新的青蛙來代替原Pw。

（2）全局優化

步驟1 本輪搜索結束后，進行新一輪局部搜索。

步驟2 重復步驟1，經過N 輪局部優化后，將所有子種群的解重新混合在一起，按適應度f（i）降序排列，重新劃分簇群。

步驟3 重復步驟2，直到滿足目標函數E（Pi）值最小為止。

2.4 簇半徑的動態調整

每一輪采樣l（1≤l≤N），簇頭CHi可計算其競爭半徑如下［8］

簇內成員節點與簇頭采用單跳通信方式通信。成員節點除了發送自身采集的數據，還需轉發來自簇外其它節點的通過鏈式結構傳送的數據。如果簇頭節點承擔過重負擔，將消耗更多的能量，這樣會使得簇頭過早失效或丟棄數據包，從而造成感知空洞。為此，UCSNP采取一種動態的簇半徑優化策略以調整節點間負載均衡。設置權值Wi計算公式如下

式中： ——0－1之間的參數；E（nk）——簇ci內成員節點nk在本輪采樣中所消耗的能量；E（CHi）——簇頭CHi在本輪采樣中所消耗的能量；R0——簇頭CHi在本輪的通信半徑。從式 （9）可得出，權值Wi由成員節點總能耗與簇頭能耗之比和成員節點到簇頭距離總和與到簇頭通信半徑之比來決定。

3 性能分析

在下面實驗中，通過仿真網絡中節點的通信和節點能耗［15］，主要從能耗和收斂時間方面與EEUC 進行對比分析。設置一個200m×200m 的監測區域，區域內通過分簇算法形成1個Sink節點和若干個簇，每個簇內有1個融合節點，其中，Sink節點和融合節點為固定位置，其余節點成隨機分布 （random waypoint）。

節點總的個數為100，普通節點的最大通信半徑為10m，簇頭的最大通信半徑為20m。普通節點初始能量為1J，Sink節點和融合節點則為40J，數據包的最大值為128B，節點間傳輸帶寬為0.5Mbps。設置節點周期性地感知和發送數據，各節點的采樣周期為0.5－1.0s，發送數據的周期為0.2－0.5s，青蛙群體總數最大值為50，全局優化的迭代次數為N＝10，每次仿真持續時間為300s。

實驗總共進行300 輪。圖2 為UCSNP 協議和EEUC協議在網絡運行期間除簇頭和Sink節點以外的普通節點平均能耗比較。由圖2分析得出，UCSNP協議和EEUC協議網絡分區合理，能耗曲線都比較平穩，即相同的仿真時間內，能耗消耗均衡。UCSNP協議由于引入了簇半徑優化策略，使得網絡中有較多的簇規模接近最優，相比EEUC 協議減少了能耗。簇頭和Sink節點都為路邊固定設施，所以其能耗問題的影響相比普通節點要小很多。

圖2 UCSNP和EEUC協議能耗比較

圖3為UCSNP協議和EEUC 協議的存活節點數目對比圖。從圖3中可以看出，EEUC 協議第一個節點的死亡輪數是第88輪，而UCSNP 協議第一個節點的死亡輪數是123輪，比EEUC協議推遲了35 輪。在第300 輪時，EEUC協議存活節點數為29，而UCSNP協議的存活節點數為57。從以上分析得出，UCSNP協議由于引入了基于混合蛙跳算法的簇間路由優化，從而延長了網絡生命周期。

圖3 UCSNP和EEUC存活節點數目

圖4顯示為UCSNP 協議和EEUC 協議端到端平均收斂時間的對比。當網絡拓撲發生變化時，EEUC 協議在簇內重新選舉簇頭，并通過簇間協商建立簇通信半徑。當網絡規模較大時，該協議由于收斂時間的大幅度增加而使得性能迅速下降。然而，在UCSNP 中，由固定簇頭CHi或其備用簇頭CH′i重新建立簇通信，無需選舉簇頭。此外，某些成員節點連接來自簇外的鏈式結構以分擔簇頭的負荷。從圖4中可以看出，當兩簇頭間路由跳數增加時，EEUC協議近似于線性變化，而UCSNP協議呈凹形曲線。可見，相比EEUC，UCSNP協議在收斂時間方面明顯減少。

圖4 UCSNP和EEUC平均收斂時間比較

4 結束語

路由協議對于提高WSNs的整體性能及服務質量尤為關鍵。本文提出了一種非均勻分簇的路由優化協議UCSNP，用于緩解基于WSNs的智能交通系統的 “熱區”問題。UCSNP協議考慮了智能交通環境下車輛傳感網絡的特點，采用鏈式結合非均勻分簇的混合網絡結構。在該網絡中，簇頭間存在多路徑路由傳送采集的數據到基站。如果確定一條從源點到Sink節點的固定路徑進行傳輸，當某個簇通信負載增大時，就會出現因簇頭失效或負荷過重導致數據包丟失和傳輸時延增大，為此重新更新路由，將進一步增大能耗。因此，UCSNP協議采用混合蛙跳算法來全局優化簇間路由。此外，簇半徑優化策略的引入避免了集中式成簇機制的一些弊端，在一定程度上平衡了網絡負載。仿真實驗結果表明，UCSNP協議在網絡模型中相比EEUC協議能更有效地延長網絡生命周期并且減短網絡收斂時間。

［1］WANG Ruchuan.The technology and application of WSNs［M］.Beijing：People’s Posts and Telecommunications Publishing House，2011：8－20 （in Chinese）. ［王汝傳.無線傳感器網絡技術及其應用 ［M］.北京：人民郵電出版社，2011：8－20.］

［2］LI Ye，WANG Jingbo，DONG Libo，et al.Research on applications of the internet of things in ITSs［J］.Journal of Mobile Communication，2010，15 （1）：30－34 （in Chinese）.［李野，王晶波，董利波，等.物聯網在智能交通中的應用研究 ［J］.移動通信，2010，15 （1）：30－34.］

［3］Bani Yassein M，Al－zou＇bi A，Khamayseh Y，et al.Improvement on LEACH protocol of wireless sensor network（VLEACH）［J］.International Journal of Digital Content Technology and its Applications，2009，3 （2）：132－136.

［4］Gong Bencan，Xu Shouzhi.Unequal density－based node deployment and clustering routing protocol in wireless sensor networks［J］.Journal of Networks，2012，7 （11）：1892－1899.

［5］LIU Haolin，ZHU Min，ZHANG Zhihong.An uneven layered－based routing algorithm in wireless sensor network［J］.Journal of Sichuan University （Natural Science Edition），2011，4 （1）：803－807 （in Chinese）. ［劉昊霖，朱敏，張志宏.一種基于非均勻分層的WSN 分簇路由算法 ［J］.四川大學學報 （自然科學版），2011，4 （1）：803－807.］

［6］Sasikumar M，Dr R Anitha.Performance evaluation of heterogeneous－HEED protocol for wireless sensor networks［J］.International Journal of Advanced Research in Computer and Communication Engineering，2014，3 （2）：5555－5558.

［7］ZHANG Juntao，LI Yuan，CHEN Xiaoli.A novel improved data fusion algorithm based on TEEN ［J］.Journal of Shaanxi University of Science and Technology （Natural Science Edition），2013，31 （4）：110－113 （in Chinese）. ［張俊濤，李媛，陳曉莉.基于TEEN路由協議的改進型數據融合算法 ［J］.陜西科技大學學報（自然科學版），2013，31 （4）：110－113.］

［8］TANG Jiashan，WANG Yan.Improved EEUC routing protocol for wireless sensor networks ［J］.Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition），2013，2 （1）：172－177 （in Chinese）.［唐加山，王燕.無線傳感器網絡中改進的EEUC 路由協議 ［J］.重慶郵電大學學報 （自然科學版），2013，2 （1）：172－177.］

［9］XU Dongdong，CHEN Guangting，TAN Lixing，et al.Routing protocol based on non－uniform clustering for wireless sensor networks ［J］.Journal of Hangzhou Dianzi University，2012，32 （3）：61－63 （in Chinese）.［徐冬冬，陳光亭，譚立興，等.基于非均勻分簇的無線傳感網絡路由協議 ［J］.杭州電子科技大學學報，2012，32 （3）：61－63.］

［10］LUO Jianping，CHEN Minrong.Study on trajectory and convergence analysis of shuffled frog leaping algorithm and its improved algorithm ［J］.Signal Processing，2010，26 （9）：1428－1433 （in Chinese）.［駱劍平，陳泯融.混合蛙跳算法及其改進算法的運動軌跡及收斂性分析 ［J］.信號處理，2010，26 （9）：1428－1433.］

［11］YOU Ziyi，ZHANG Junhua，CHEN Shiguo.A data aggregation scheme based on wireless sensor networks and its application research in intelligent transportation system ［J］.Application Research of Computers，2014，31 （6）：1719－1722 （in Chinese）.［游子毅，章俊華，陳世國.基于無線傳感網絡的數據融合方法及其在智能交通系統中的應用 ［J］.計算機應用研究，2014，31 （6）：1719－1722.］

［12］Hussein T Mouftah，Mounib Khanafer，Mouhcine Guennoun.Wireless sensor network architectures for intelligent vehicular systems［EB／OL］.http：／／www.mcit.gov.sa／nr／rdo nlyres／08880e2f－f4c9－4029－988f－05bf1379516d／0／paper2.pdf，2010.

［13］Ossenbruggen P，Laflamme E.Time series analysis and models of freeway performance［J］.Journal of Transportation Engineering，2012，138 （8）：1030－1039.

［14］Shin－Ting Jeng，Tok YCA，Ritchie SG.Freeway corridor performance measurement based on vehicle reidentification［C］／／IEEE Transactions on Intelligent Transportation Systems，2010，11 （3）：639－646.

［15］Singh Y，Chaba Y，Jain M，et al.Performance evaluation of on demand multicasting routing protocols in mobile ad hoc networks ［C］／／International Conference on Recent Trends in Information， Telecommunication and Computing，2010：298－300.