面向電網(wǎng)監(jiān)測(cè)的線狀WSN節(jié)點(diǎn)中繼次數(shù)均衡路由算法

魏振春， 汪國(guó)勝， 石 雷， 衛(wèi) 星

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009；2.合肥工業(yè)大學(xué) 安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，安徽 合肥230009）

隨著超／特高壓輸電線路（500kV、750kV、1 000kV）開(kāi)始大量建設(shè)，電網(wǎng)規(guī)模不斷擴(kuò)大，線路走廊需要穿越各種復(fù)雜的地理環(huán)境（如沼澤、叢林、戈壁和崇山峻嶺等無(wú)人區(qū)），這些都使得電力線路的巡檢工作更加困難；另一方面，供電企業(yè)對(duì)輸電線路的管理維護(hù)向信息化和智能化方向發(fā)展，而依靠傳統(tǒng)巡檢方式獲取的信息量非常有限，難以滿足要求，因而急需一種有力的監(jiān)控手段對(duì)輸電線路進(jìn)行實(shí)時(shí)監(jiān)測(cè)。在高壓輸電線路上布置傳感器節(jié)點(diǎn)，利用傳感器采集高壓輸電線路的狀態(tài)信息和自然物理信息，通過(guò)傳感器節(jié)點(diǎn)組成的線狀無(wú)線傳感器網(wǎng)絡(luò)［1］對(duì)采集到的數(shù)據(jù)進(jìn)行傳輸，即可實(shí)現(xiàn)對(duì)高壓輸電線路的在線實(shí)時(shí)監(jiān)測(cè)。

在線狀無(wú)線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)傳輸?shù)姆绞接陕酚蓞f(xié)議決定［2］，如果采集到的數(shù)據(jù)都是按照從節(jié)點(diǎn)到基站逐點(diǎn)中繼傳遞，節(jié)點(diǎn)中繼次數(shù)將呈現(xiàn)離基站越近中繼次數(shù)越多的倒三角分布情況，導(dǎo)致節(jié)點(diǎn)中繼次數(shù)的不均衡。本文通過(guò)將傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為簇和簇群，建立了2層網(wǎng)絡(luò)結(jié)構(gòu)，提出一種節(jié)點(diǎn)中繼次數(shù)均衡路由算法。

1 相關(guān)工作

基于無(wú)線傳感網(wǎng)的高壓輸電線路監(jiān)測(cè)系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。通過(guò)在高壓輸電線路上均勻布置若干普通無(wú)線傳感器節(jié)點(diǎn)，并按照特定距離D（與傳感器節(jié)點(diǎn)最大傳輸距離有關(guān)）布置若干帶有GPRS／CDMA通信模塊的匯聚Sink節(jié)點(diǎn)，自組織后成為無(wú)線傳感器網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)采集高壓輸電線路的狀況以及周邊的環(huán)境狀況，如溫度、風(fēng)速、導(dǎo)線的弧垂、跨距等，實(shí)時(shí)以無(wú)線多跳的方式將數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn)，然后通過(guò)公網(wǎng)將信息發(fā)送到監(jiān)測(cè)中心。用于高壓輸電線路監(jiān)測(cè)的無(wú)線傳感器網(wǎng)絡(luò)沿著線路進(jìn)行人工布置，鐵塔安裝后其位置信息已基本確定，因而無(wú)線傳感器節(jié)點(diǎn)的定位問(wèn)題比較容易解決。

文獻(xiàn)［3］提出的 MERR（Minimum Energy Relay Routing，簡(jiǎn)稱(chēng)MERR）路由協(xié)議通過(guò)選擇最優(yōu)中繼傳輸距離，然后通過(guò)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)信息，從而使整個(gè)線狀網(wǎng)消耗的能量最??；而AMERR［4］（Adaptive Minimum Energy Relay Routing，簡(jiǎn)稱(chēng)AMERR）則在MERR基礎(chǔ)之上調(diào)整了最優(yōu)傳輸距離的計(jì)算方法。文獻(xiàn)［5］提出的基于電網(wǎng)監(jiān)測(cè)的無(wú)線傳感器網(wǎng)絡(luò)短路徑路由算法則通過(guò)短路徑場(chǎng)的建立來(lái)預(yù)留多條較短距離路徑，并在實(shí)際數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)選擇剩余能量最大的節(jié)點(diǎn)轉(zhuǎn)發(fā)，從而提高了傳輸可靠性和網(wǎng)絡(luò)生命周期；文獻(xiàn)［6］提出的 REECR（Energy Efficient Routing Protocol Based on Residual Energy and Energy Consumption Rate，簡(jiǎn)稱(chēng)REECR）算法綜合考慮所有節(jié)點(diǎn)的剩余能量和能量消耗率來(lái)選擇簇頭節(jié)點(diǎn)，以達(dá)到均勻消耗節(jié)點(diǎn)能量和延長(zhǎng)網(wǎng)絡(luò)生命周期的目的；文獻(xiàn)［7］則在REECR的基礎(chǔ)上將簇頭間的距離也作為選擇簇頭節(jié)點(diǎn)的依據(jù)之一，與節(jié)點(diǎn)的剩余能量和能量消耗率一起來(lái)選擇簇頭，提出 D－REECR（Distance－based REECR，簡(jiǎn)稱(chēng)D－REECR）路由協(xié)議。以上協(xié)議均將能量問(wèn)題作為首要約束條件，而高壓輸電線路監(jiān)測(cè)系統(tǒng)中通過(guò)采用現(xiàn)場(chǎng)取電、無(wú)線電供電等技術(shù)解決能量問(wèn)題，所以能量問(wèn)題不再是首要的約束條件，本文摒棄能量利用的限制條件，重點(diǎn)考慮節(jié)點(diǎn)中繼次數(shù)的均衡性問(wèn)題，提出了線狀WSN節(jié)點(diǎn)中繼次數(shù)均衡路由算法。

圖1 系統(tǒng)示意圖

2 線狀WSN節(jié)點(diǎn)中繼次數(shù)均衡路由算法

由于通過(guò)匯聚節(jié)點(diǎn)將整個(gè)沿輸電線路布置的WSN節(jié)點(diǎn)分割成最大距離為D的若干段，每段構(gòu)成一個(gè)獨(dú)立的 WSN網(wǎng)絡(luò)，因此本文僅討論距離D范圍內(nèi)節(jié)點(diǎn)的路由問(wèn)題。距離D范圍內(nèi)線狀WSN分層結(jié)構(gòu)如圖2所示。

假定圖1中由單個(gè)鐵塔周?chē)膫鞲衅鞴?jié)點(diǎn)組成一個(gè)簇，從每個(gè)簇中選擇一個(gè)節(jié)點(diǎn)作為簇頭，再將若干個(gè)簇組成一個(gè)簇群，每個(gè)簇群中含有若干個(gè)簇頭節(jié)點(diǎn)，僅簇頭節(jié)點(diǎn)參與中繼路由任務(wù)。線狀WSN節(jié)點(diǎn)中繼次數(shù)均衡路由算法可以劃分為節(jié)點(diǎn)分簇階段、分簇組群階段和路由階段3個(gè)部分。

圖2 網(wǎng)絡(luò)分層及路由示意圖

2.1 節(jié)點(diǎn)分簇階段

假設(shè)線狀無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)i到Sink的距離為Si，兩鐵塔間距為d，若

則規(guī)定節(jié)點(diǎn)i位于第k個(gè)簇中。簇中簇頭節(jié)點(diǎn)的選擇參考LEACH［8］，具體選擇過(guò)程如下。

節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)0～1之間的數(shù)，如果這個(gè)隨機(jī)數(shù)小于閾值P（m），則認(rèn)為自己即為簇頭。如果在本輪中已經(jīng)當(dāng)選過(guò)簇頭節(jié)點(diǎn)，則把P（m）置為0，之后此節(jié)點(diǎn)在本輪中就不會(huì)再次當(dāng)選為簇頭。隨著已當(dāng)選過(guò)簇頭節(jié)點(diǎn)數(shù)目的增加，剩余節(jié)點(diǎn)當(dāng)選為簇頭的閾值隨之增大，因此產(chǎn)生的隨機(jī)數(shù)小于閾值的概率隨之增大，當(dāng)只剩一個(gè)節(jié)點(diǎn)未當(dāng)選時(shí)，則該節(jié)點(diǎn)一定當(dāng)選。當(dāng)所有節(jié)點(diǎn)都當(dāng)選過(guò)簇頭時(shí)，則進(jìn)行新一輪簇頭的選擇。其閾值計(jì)算公式為：

其中，p為簇頭數(shù)與總節(jié)點(diǎn)數(shù)的百分比；r為當(dāng)前的輪數(shù)；C為最近1／p輪中非簇頭節(jié)點(diǎn)集。

2.2 分簇組群階段

從離Sink最遠(yuǎn)端開(kāi)始按簇的個(gè)數(shù)將相鄰的若干個(gè)簇組成簇群，設(shè)j號(hào)簇群所含簇的個(gè)數(shù)為Nj，采用2種方案進(jìn)行分簇組群。

方案1分簇組群依據(jù)如下：

方案2分簇組群依據(jù)如下：

其中，β為簇群增長(zhǎng)系數(shù)。

2.3 路由階段

路由協(xié)議采用分層網(wǎng)絡(luò)結(jié)構(gòu)，并通過(guò)統(tǒng)計(jì)每個(gè)傳感器節(jié)點(diǎn)的中繼路由次數(shù)使其達(dá)到均衡的目的。每個(gè)節(jié)點(diǎn)均保存有本簇群內(nèi)所有簇頭節(jié)點(diǎn)的中繼次數(shù)表，中繼次數(shù)表中包括節(jié)點(diǎn)的ID標(biāo)識(shí)和中繼次數(shù)。具體路由過(guò)程如下：所有節(jié)點(diǎn)的中繼次數(shù)路由表均為空，當(dāng)有數(shù)據(jù)傳輸任務(wù)到達(dá)時(shí)，節(jié)點(diǎn)首先判斷自己是否為簇頭節(jié)點(diǎn)，如果不是則直接丟棄該數(shù)據(jù)包，否則根據(jù)數(shù)據(jù)包ID判斷此數(shù)據(jù)包是否為上游相鄰簇群傳來(lái)的，如果是則搜索本節(jié)點(diǎn)中繼次數(shù)表，如果本節(jié)點(diǎn)的中繼次數(shù)最少，則轉(zhuǎn)發(fā)此數(shù)據(jù)包，并加上自己的ID標(biāo)識(shí)，否則直接丟棄數(shù)據(jù)包。如果中繼次數(shù)表中最小中繼次數(shù)不唯一，則節(jié)點(diǎn)ID標(biāo)識(shí)最小的節(jié)點(diǎn)參與本數(shù)據(jù)包的路由傳遞任務(wù)。

節(jié)點(diǎn)作為中繼節(jié)點(diǎn)傳遞數(shù)據(jù)后，廣播本節(jié)點(diǎn)的ID，相同簇群內(nèi)的簇頭節(jié)點(diǎn)收到此ID的數(shù)據(jù)包后，更新各自的中繼次數(shù)表。每個(gè)節(jié)點(diǎn)收到數(shù)據(jù)包后所執(zhí)行的算法如下：

（1）節(jié)點(diǎn)A接收到數(shù)據(jù)包。

（2）判斷節(jié)點(diǎn)A是否為簇頭節(jié)點(diǎn)，如果是轉(zhuǎn)到步驟（3），否則轉(zhuǎn)到步驟（8）。

（3）判斷數(shù)據(jù)包中的ID標(biāo)識(shí)是否為節(jié)點(diǎn)A的上游簇群內(nèi)節(jié)點(diǎn)的ID，如果是轉(zhuǎn)到步驟（4），否則轉(zhuǎn)到步驟（8）。

（4）檢索節(jié)點(diǎn)A的中繼次數(shù)路由表。判斷節(jié)點(diǎn)A的中繼次數(shù)是否最少，如果是轉(zhuǎn)到步驟（5），否則轉(zhuǎn)到步驟（8）。

（5）判斷節(jié)點(diǎn)A的中繼次數(shù)路由表內(nèi)最少中繼次數(shù)的節(jié)點(diǎn)個(gè)數(shù)是否為1，如果為1轉(zhuǎn)到步驟（7），否則轉(zhuǎn)到步驟（6）。

（6）尋找節(jié)點(diǎn)A的中繼次數(shù)表中的中繼次數(shù)最小且ID標(biāo)識(shí)最小的節(jié)點(diǎn)，判斷其ID是否為節(jié)點(diǎn)A的ID，如果是轉(zhuǎn)到步驟（7），否則轉(zhuǎn)到步驟（8）。

（7）中繼數(shù)據(jù)包，更新中繼次數(shù)路由表。

（8）丟棄數(shù)據(jù)包。

（9）結(jié)束。

3 仿真實(shí)驗(yàn)

GPSR［9］（Greedy Perimeter Stateless Routing，簡(jiǎn)稱(chēng)GPSR）算法也是不把能量問(wèn)題作為首要的約束條件，與本文的研究背景類(lèi)似，因此選擇和GPSR進(jìn)行比較。GPSR僅僅依靠相鄰節(jié)點(diǎn)位置信息選擇路由，只能實(shí)現(xiàn)局部最優(yōu)，用于線狀傳感器網(wǎng)絡(luò)時(shí)容易出現(xiàn)中繼次數(shù)呈現(xiàn)離基站越近中繼次數(shù)越多的倒三角分布情況，導(dǎo)致節(jié)點(diǎn)中繼次數(shù)的不均衡。而在本文提出的簇群選取方案1的路由算法中假設(shè)每個(gè)節(jié)點(diǎn)產(chǎn)生r個(gè)數(shù)據(jù)包，則每個(gè)簇群中的每個(gè)簇j內(nèi)節(jié)點(diǎn)作為中繼路由的平均次數(shù)為：

從而達(dá)到了中繼次數(shù)均衡的目標(biāo)。同時(shí)方案2的選取綜合考慮GPSR和方案1，避免了GPSR算法中繼次數(shù)增長(zhǎng)過(guò)快以及方案1中離Sink節(jié)點(diǎn)最近的簇群內(nèi)中繼節(jié)點(diǎn)單跳距離過(guò)長(zhǎng)的問(wèn)題。

本文的仿真條件是在線狀區(qū)域上，均勻分布128個(gè)簇，每個(gè)簇包括5個(gè)傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)產(chǎn)生50個(gè)數(shù)據(jù)包，MAC層采用802.11協(xié)議，其中方案2中的β取3，使用網(wǎng)絡(luò)仿真器NS－2進(jìn)行仿真實(shí)驗(yàn)。采用不同方案時(shí)，0～11號(hào)簇的簇內(nèi)節(jié)點(diǎn)平均中繼次數(shù)對(duì)比如圖3所示。

圖3 0～11號(hào)簇內(nèi)節(jié)點(diǎn)平均中繼次數(shù)對(duì)比

仿真實(shí)驗(yàn)結(jié)果表明，GPSR算法中到Sink距離越近的節(jié)點(diǎn)中繼次數(shù)越多，并且呈線性增長(zhǎng)，且增長(zhǎng)幅度非常明顯；采用方案2時(shí)，雖然中繼次數(shù)仍然線性增長(zhǎng)，但增長(zhǎng)幅度比較緩慢；而采用簇群選取方案1的路由算法時(shí)，簇內(nèi)節(jié)點(diǎn)平均中繼次數(shù)為48次，和每個(gè)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包數(shù)基本相當(dāng)，從而使節(jié)點(diǎn)的平均中繼次數(shù)達(dá)到均衡，避免了由于某些節(jié)點(diǎn)中繼任務(wù)過(guò)重而提前失效死亡，從而延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

假設(shè)無(wú)線傳感器節(jié)點(diǎn)的最大傳輸距離為S，鐵塔間距為d，從而得到方案1中距離D的最大值MAXD的計(jì)算方法為：

方案2中距離D的最大值MAXD的計(jì)算方法為：

當(dāng)β取3、d取50m，分別采用方案1與方案2時(shí)，對(duì)應(yīng)不同的節(jié)點(diǎn)最大傳輸距離所得到的距離D的最大值MAXD的對(duì)比，如圖4所示。從圖4可以看出，由于在分簇群時(shí)方案1的簇群內(nèi)節(jié)點(diǎn)個(gè)數(shù)增長(zhǎng)幅度比方案2要大，所以當(dāng)S≥850m以后，在節(jié)點(diǎn)最大傳輸距離相等的情況下，方案2的距離D的最大值MAXD要比方案1大，從而得到方案2的網(wǎng)絡(luò)覆蓋范圍比方案1大。而在高壓輸電線路中鐵塔間距是固定的，所以傳感器節(jié)點(diǎn)總體均勻分布，同時(shí)為了避免方案1導(dǎo)致離Sink節(jié)點(diǎn)最近的簇群內(nèi)中繼節(jié)點(diǎn)單跳距離過(guò)長(zhǎng)，以及盡量保證網(wǎng)絡(luò)覆蓋范圍更大、中繼次數(shù)均衡，因此方案2的路由算法更適合高壓輸電線路監(jiān)測(cè)這類(lèi)線狀無(wú)線傳感器網(wǎng)絡(luò)。

圖4 距離D的最大值MAXD對(duì)比

4 結(jié)束語(yǔ)

高壓輸電線路監(jiān)測(cè)系統(tǒng)中通過(guò)采用現(xiàn)場(chǎng)取電、無(wú)線電供電等技術(shù)，能量問(wèn)題不再是首要約束條件，因此研究中主要考慮線狀無(wú)線傳感網(wǎng)中節(jié)點(diǎn)的中繼次數(shù)，本文提出了一種節(jié)點(diǎn)中繼次數(shù)均衡路由算法。該算法使得整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的中繼次數(shù)達(dá)到均衡，從而有效延長(zhǎng)網(wǎng)絡(luò)的生命周期。同時(shí)，綜合考慮高壓輸電線路的特殊結(jié)構(gòu)以及方案1后認(rèn)為方案2更適合本文的研究背景。受傳感器節(jié)點(diǎn)無(wú)線最大傳輸距離的限制，本文提出的路由算法更適用于短距離密集型線狀無(wú)線傳感器網(wǎng)絡(luò)。

［1］王文光，劉士興，謝武軍.無(wú)線傳感器網(wǎng)絡(luò)概述［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（9）：1416－1419，1437.

［2］彭 靜，劉光祜，謝世歡.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究現(xiàn)狀與趨勢(shì)［J］.計(jì)算機(jī)應(yīng)用研究，2007（2）：4－9.

［3］Zimmerling M，Dargie W，Reason J M.Energy－efficient routing in linear wireless sensor networks［C］／／Proc IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，2007：1－3.

［4］Zimmerling M，Dargie W，Reason J M.Localized power－aware routing in linear wireless sensor networks［C］／／Proceedings of the 2nd ACM International Conference on Context－awareness for Self－Managing Systems，2008：24－33.

［5］鄭更生，賀貴明，謝治平.基于電網(wǎng)監(jiān)測(cè)的無(wú)線傳感器網(wǎng)絡(luò)短路徑路由算法［J］.武漢大學(xué)學(xué)報(bào)：工學(xué)版，2007，40（2）：121－124.

［6］Li Xiaoya，Huang Daoping，Yang Jian.Energy efficient routing protocol based on residual energy and energy Consumption rate for heterogeneous wireless sensor networks［C］／／Proceedings of the 26th Chinese Control Conference，2007：587－590.

［7］李小亞，黃道平，孫宗海.一種異構(gòu)傳感器網(wǎng)絡(luò)的能量有效路由算法［J］.計(jì)算機(jī)科學(xué)，2008，35（5）：60－63.

［8］Heinzelman W，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks［C］／／Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2002：3005－3014.

［9］Karp B，Kung H.GPSR：Greedy perimeter stateless routing for wireless networks［C］／／Proceedings of the 6th Annual Int Conf on Mobile Computing and Networking，2000：243－254.