基于WSNs智能交通系統(tǒng)的非均勻分簇路由

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

（1.貴州省機械電子產(chǎn)品質(zhì)量監(jiān)督檢驗院，貴州 貴陽550081；2.貴州師范大學(xué) 物理與電子科學(xué)學(xué)院，貴州 貴陽550001；3.貴州省教育廳汽車電子技術(shù)特色重點實驗室，貴州 貴陽550001）

0 引 言

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

在智能交通場景中，傳感器節(jié)點多，采集的原始數(shù)據(jù)量較大。此外，車輛節(jié)點具有高移動性，使得車輛傳感網(wǎng)的節(jié)點分布情況比靜態(tài)傳感器網(wǎng)絡(luò)具有更頻繁的變化。因此，現(xiàn)有的分層WSNs路由協(xié)議都不太適合智能交通環(huán)境。本文提出了一種能量均衡的非均勻分簇路由協(xié)議 （UCSNP）用于智能交通系統(tǒng)。該協(xié)議著重對非均勻成簇、簇間路由以及簇半徑調(diào)整進行討論。結(jié)合智能交通的特點，UCSNP建立鏈?zhǔn)浇Y(jié)構(gòu)［9］和分簇結(jié)構(gòu)混合的通信方式，并在這種通信方式下，通過混合蛙跳算法［10］對簇間路由進行優(yōu)化，動態(tài)調(diào)整簇通信半徑。UCSNP 使網(wǎng)絡(luò)拓?fù)涓雍侠?，提高網(wǎng)絡(luò)的生存周期并且減短了網(wǎng)絡(luò)的收斂時間。本文在文獻 ［11］基礎(chǔ)之上解決基于WSNs的交通信息傳輸?shù)摹盁釁^(qū)”問題。

1 混合蛙跳算法

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

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

2 UCSNP協(xié)議

2.1 網(wǎng)絡(luò)模型與分簇策略

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

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

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

圖1 鏈?zhǔn)胶头执鼗旌系木W(wǎng)絡(luò)結(jié)構(gòu)

網(wǎng)絡(luò)中的每一個傳感器 （車輛和路邊設(shè)施）都有一個唯一的標(biāo)志ID，由可信中心 （trusted authority）負(fù)責(zé)對節(jié)點認(rèn)證、注冊并授權(quán)。節(jié)點可通過ID 號和TA 簽發(fā)的數(shù)字證書相互驗證身份。

節(jié)點能量模型描述如下，節(jié)點發(fā)射l比特數(shù)據(jù)到距離為d 的位置，則發(fā)送端的能量為

接收端的能量為

其詳細(xì)說明參見文獻 ［8］。

2.2 簇間路由初始化參數(shù)

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

青蛙個體的適應(yīng)度主要依據(jù)傳輸數(shù)據(jù)的能耗和可靠性來計算。定義適應(yīng)度函數(shù)為

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

函數(shù)fi描述路徑Pi的總體能量消耗，包括該路徑上各節(jié)點的計算代價和通信負(fù)荷。每一輪數(shù)據(jù)采樣，簇頭CHi接收簇內(nèi)成員節(jié)點和來自相鄰簇頭的消息，計算出各能耗參數(shù)并更新從該簇頭到Sink 節(jié)點的每條路徑的代價。其中，系數(shù)α1，α2，α3為各種參數(shù)在節(jié)點總體能耗中的比重?？梢姡亻g最優(yōu)路徑問題等于青蛙最優(yōu)解的問題。最優(yōu)解問題是目標(biāo)函數(shù)E（Pi）取最小值，即fi取最大值。

CHi將生 成 的 青 蛙 適 應(yīng) 度 按 降 序 排 列 成P1，P2，...，PF，并劃分成m 個種群Y1，Y2，...，Ym，構(gòu)造子種群。m 的數(shù)值由P 中源點的下一跳節(jié)點的個數(shù)來決定。每個子種群包含s只青蛙，滿足下列關(guān)系

2.3 簇間路由優(yōu)化

（1）局部優(yōu)化

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

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

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

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

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

經(jīng)過交叉后，Pw變?yōu)?/p>

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

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

（2）全局優(yōu)化

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

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

步驟3 重復(fù)步驟2，直到滿足目標(biāo)函數(shù)E（Pi）值最小為止。

2.4 簇半徑的動態(tài)調(diào)整

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

簇內(nèi)成員節(jié)點與簇頭采用單跳通信方式通信。成員節(jié)點除了發(fā)送自身采集的數(shù)據(jù)，還需轉(zhuǎn)發(fā)來自簇外其它節(jié)點的通過鏈?zhǔn)浇Y(jié)構(gòu)傳送的數(shù)據(jù)。如果簇頭節(jié)點承擔(dān)過重負(fù)擔(dān)，將消耗更多的能量，這樣會使得簇頭過早失效或丟棄數(shù)據(jù)包，從而造成感知空洞。為此，UCSNP采取一種動態(tài)的簇半徑優(yōu)化策略以調(diào)整節(jié)點間負(fù)載均衡。設(shè)置權(quán)值Wi計算公式如下

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

3 性能分析

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

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

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

圖2 UCSNP和EEUC協(xié)議能耗比較

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

圖3 UCSNP和EEUC存活節(jié)點數(shù)目

圖4顯示為UCSNP 協(xié)議和EEUC 協(xié)議端到端平均收斂時間的對比。當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時，EEUC 協(xié)議在簇內(nèi)重新選舉簇頭，并通過簇間協(xié)商建立簇通信半徑。當(dāng)網(wǎng)絡(luò)規(guī)模較大時，該協(xié)議由于收斂時間的大幅度增加而使得性能迅速下降。然而，在UCSNP 中，由固定簇頭CHi或其備用簇頭CH′i重新建立簇通信，無需選舉簇頭。此外，某些成員節(jié)點連接來自簇外的鏈?zhǔn)浇Y(jié)構(gòu)以分擔(dān)簇頭的負(fù)荷。從圖4中可以看出，當(dāng)兩簇頭間路由跳數(shù)增加時，EEUC協(xié)議近似于線性變化，而UCSNP協(xié)議呈凹形曲線。可見，相比EEUC，UCSNP協(xié)議在收斂時間方面明顯減少。

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

4 結(jié)束語

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

［1］WANG Ruchuan.The technology and application of WSNs［M］.Beijing：People’s Posts and Telecommunications Publishing House，2011：8－20 （in Chinese）. ［王汝傳.無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用 ［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）.［李野，王晶波，董利波，等.物聯(lián)網(wǎng)在智能交通中的應(yīng)用研究 ［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］.四川大學(xué)學(xué)報 （自然科學(xué)版），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路由協(xié)議的改進型數(shù)據(jù)融合算法 ［J］.陜西科技大學(xué)學(xué)報（自然科學(xué)版），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）.［唐加山，王燕.無線傳感器網(wǎng)絡(luò)中改進的EEUC 路由協(xié)議 ［J］.重慶郵電大學(xué)學(xué)報 （自然科學(xué)版），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）.［徐冬冬，陳光亭，譚立興，等.基于非均勻分簇的無線傳感網(wǎng)絡(luò)路由協(xié)議 ［J］.杭州電子科技大學(xué)學(xué)報，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）.［游子毅，章俊華，陳世國.基于無線傳感網(wǎng)絡(luò)的數(shù)據(jù)融合方法及其在智能交通系統(tǒng)中的應(yīng)用 ［J］.計算機應(yīng)用研究，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.