無線傳感器網(wǎng)絡(luò)中基于同心圓樹的路由選擇算法

文孟飛，彭軍，張曉勇，劉偉榮

（中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410075）

高速公路的交通情況主要受車流的流向和天氣氣候以及高速公路路況和地形因素的影響，而高速公路的主要任務(wù)是減少上述因素對整個交通情況所造成的影響。國內(nèi)外研究者提出了許多交通系統(tǒng)用于高速公路的監(jiān)視與控制。這些系統(tǒng)可采集車流量、超速、交通意外和路面狀況等各種信息，并依據(jù)這些現(xiàn)場信息做出安全預(yù)警、出行參考和事故救援等決策[1?2]。無線傳感器網(wǎng)絡(luò)（Wireless sensor network，WSN）作為一種全新的信息獲取和處理技術(shù)，集成了傳感器、計算機網(wǎng)絡(luò)和無線通信等技術(shù)，能很好地實現(xiàn)系統(tǒng)與車的通信，但是，無線傳感器節(jié)點能量有限，在公路環(huán)境下為其補充能量成為難題,因此，亟需高效合理地利用能量以最大化提高整個無線傳感器網(wǎng)絡(luò)的壽命[3?5]。針對無線傳感器網(wǎng)絡(luò)能量利用，研究人員提出相應(yīng)能量感知路由協(xié)議，如：林益等[6]提出了一種最少跳數(shù)路由協(xié)議，利用蟻群算法來尋找從源節(jié)點到目標節(jié)點間跳數(shù)最少的路徑。該方法可快速地構(gòu)建路由并有效減少能量消耗，但是其數(shù)據(jù)傳送路徑過于集中，容易使關(guān)鍵節(jié)點能量迅速耗盡，從而減小整個網(wǎng)絡(luò)的生存周期；能量感知路由協(xié)議（EAR）算法在源節(jié)點和目的節(jié)點間提供了多種路由選擇。節(jié)點每次發(fā)送數(shù)據(jù)時根據(jù)某概率選擇路徑，該概率由路徑節(jié)點能耗特征及其剩余能量決定。該協(xié)議能夠均衡節(jié)點數(shù)據(jù)傳輸能量消耗，延長整個網(wǎng)絡(luò)工作時間，但是，該協(xié)議中概率計算過程過于復(fù)雜，算法收斂速度慢。Lu等[7]提出了一種能量高效多路徑路由協(xié)議（EEMRP），通過鏈路代價選擇下一跳中繼節(jié)點，鏈路代價由節(jié)點的剩余能量級別和節(jié)點到目的的節(jié)點跳數(shù)共同決定，但是，該協(xié)議通過離目的節(jié)點的跳數(shù)少而非實際距離來衡量節(jié)點間的距離關(guān)系，這會使得能量問題的考慮過于片面。總之，無線傳感器網(wǎng)絡(luò)的路由選擇協(xié)議和分簇算法會影響網(wǎng)絡(luò)通信能耗、數(shù)據(jù)量和通信延時，因此，亟需提出延長網(wǎng)絡(luò)生存周期、提高節(jié)點能量利用效率的路由機制。針對此問題，為建立高速公路設(shè)施安全監(jiān)控?zé)o線傳感器網(wǎng)絡(luò)模型（WSN-H），本文作者提出一種基于同心圓路由樹的路由選擇算法（C2TRA）。在該算法中，節(jié)點在保證網(wǎng)絡(luò)健壯性的前提下以最小功率進行路由發(fā)現(xiàn)，并采用短距離的多跳數(shù)據(jù)傳輸，節(jié)省了節(jié)點能耗；在選擇數(shù)據(jù)路由時，根據(jù)潛在下一跳節(jié)點能量狀況來選擇中級，均衡了網(wǎng)絡(luò)能耗；引入對簇內(nèi)節(jié)點分級的機制，形成以簇頭節(jié)點為樹根的簇內(nèi)路由樹，加強了數(shù)據(jù)往目的節(jié)點的導(dǎo)向，去除了不必要數(shù)據(jù)的轉(zhuǎn)發(fā)，提高了數(shù)據(jù)轉(zhuǎn)發(fā)效率，降低了整個網(wǎng)絡(luò)的能耗和通信延遲。

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

結(jié)合無線傳感器網(wǎng)絡(luò)組網(wǎng)特點和公路基礎(chǔ)設(shè)施安全監(jiān)控的實際情況，提出如圖1所示的WSN-H系統(tǒng)模型。該系統(tǒng)模型具有如下幾個特點：監(jiān)控區(qū)域廣泛且分散，目標信息變化較快，目標信息傳輸距離遠且要求實時，監(jiān)控區(qū)域地處偏遠。網(wǎng)絡(luò)模型建立在如下假設(shè)基礎(chǔ)上：

（1）網(wǎng)絡(luò)中所有的節(jié)點的最大發(fā)射功率相同，每個節(jié)點有唯一的身份標識符（ID），所采集的數(shù)據(jù)采用統(tǒng)一的數(shù)據(jù)格式。

（2）每個節(jié)點初始能量一致，發(fā)射功率均可快速調(diào)整，都可以在最小的發(fā)射功率情況下與其他節(jié)點建立連接，即不存在孤立節(jié)點。

（3）每個節(jié)點位置固定，重點部署于路口以及均勻部署于公路沿線；利用GPS或定位算法確定自己的位置及與公路的相對位置。

（4）匯聚節(jié)點部署在移動汽車上，有充分能量，數(shù)據(jù)處理與通信能力較強。

（5）存在時延約束量Δ，各節(jié)點間數(shù)據(jù)傳輸時延不得超過該約束量。

（6）每個簇的簇頭已知。

2 基于同心圓樹的路由選擇算法（C2TRA）

2.1 算法描述

為了降低節(jié)點能耗，無線傳感器網(wǎng)絡(luò)一般采用節(jié)點功率控制和多跳路由等技術(shù)，但各方法的效率有明顯差別。為此，提出一種基于同心圓樹的路由選擇算法，以提高能量利用效率，延長網(wǎng)絡(luò)生存時間。

2.1.1 多跳路由

文獻[8]給出了無線傳感器網(wǎng)絡(luò)的能耗模型。該模型可計算距離為d的2個節(jié)點發(fā)送l個比特數(shù)據(jù)所消耗的能量ETx（l，d）。

其中：l為非負整數(shù)，表示節(jié)點間發(fā)送數(shù)據(jù)的比特數(shù)；Eelec為發(fā)射電路能耗。當(dāng) d＜d0時，采用自由空間模型；εfs為該模型的功率放大能耗；當(dāng) d≥d0時，采用多路徑衰減模型；εmp為該模型的功率放大能耗；nlos_d為非視距誤差，由于高速公路環(huán)境下無線傳感器網(wǎng)絡(luò)分布較為集中，因此，可將此誤差視為正的隨機噪聲。

圖1 WSN-H系統(tǒng)模型圖Fig.1 Model of WSN-H system

本文按照式（1）分析WSN-H能耗。如圖2所示，設(shè)A，B和C 3個節(jié)點構(gòu)成1個直角三角形。A向B發(fā)送數(shù)據(jù)時有2條可選路徑：A?B和A?C?B。這2條路徑在2種模型下各自的能耗分析如下。

節(jié)點間距離分別為dAB=5，dAC=4，dBC=3。為了分析簡單，假設(shè)3個距離都不小于d0，此時為多路徑衰減模型，則A?B的通信能耗為：

A?C?B的通信能耗為：

比較式（2）與（3）可知：盡管 A?B的通信距離比A?C?B的通信距離短，但A?C?B路徑比A?B路徑的通信能耗更低。

圖2 3個傳感席子點構(gòu)成的直角三角形Fig.2 Right triangle constituted by three sensor node

若以上3個距離都小于d0，由式（1）計算分析可得出A?B路徑比A?C?B路徑的通信能耗低。

經(jīng)上述分析得出結(jié)論：當(dāng)節(jié)點間距離較小時，直接通信能耗更低；而當(dāng)節(jié)點間距離較大時，通過其他節(jié)點多跳通信能耗更低。下面將動態(tài)地根據(jù)節(jié)點剩余能量、節(jié)點間距離、連通性及信道模型等因素來選取單跳或多跳的路由策略。

2.1.2 節(jié)點功率控制

Kleinrock等[9]經(jīng)分析得出網(wǎng)絡(luò)中節(jié)點的平均鄰節(jié)點數(shù)為5.89時，連接較穩(wěn)定可靠，故本文采用功率控制技術(shù)將節(jié)點的鄰節(jié)點數(shù)保持在6個左右。節(jié)點數(shù)量的確認并不是頻繁進行的，每隔一定時間更新1次。該方案盡管存在路由開銷，但是，保證了路由穩(wěn)定，總體上對總路由開銷影響很小。節(jié)點根據(jù)其與接受節(jié)點或中繼節(jié)點之間的距離動態(tài)地調(diào)整發(fā)送功率，在保證通信質(zhì)量的基礎(chǔ)上，盡可能節(jié)約能量。每個節(jié)點會根據(jù)鄰節(jié)點的反饋，建立路由鄰居信息表，其中：ID為鄰節(jié)點的標識符；d為與鄰節(jié)點間的距離；Er為鄰節(jié)點的當(dāng)前剩余能量；level為鄰節(jié)點在當(dāng)前簇的路由層級；P 為將數(shù)據(jù)發(fā)送給鄰節(jié)點所需的最小發(fā)射功率；active為狀態(tài)標識符，表示是否與鄰節(jié)點建立穩(wěn)定連接，1表示可以轉(zhuǎn)發(fā)數(shù)據(jù)，0表示不能轉(zhuǎn)發(fā)數(shù)據(jù)。節(jié)點根據(jù)路由鄰居信息表及其當(dāng)前的工作狀態(tài)，動態(tài)地進行功率控制，如圖3所示，其中：圖3（a）所示表示未進行功率控制，此時節(jié)點發(fā)射功率最大，覆蓋范圍最大，但能耗最大；圖3（b）所示表示節(jié)點調(diào)整功率，保證剛好覆蓋到其最遠鄰節(jié)點，若鄰節(jié)點過多，能耗也較大，該情況一般用于廣播；圖 3（c）所示表示節(jié)點繼續(xù)調(diào)低發(fā)射功率，使其鄰節(jié)點數(shù)量保持在6個左右，保證節(jié)點的連通穩(wěn)定性，此時節(jié)點處于發(fā)送數(shù)據(jù)前的路由發(fā)現(xiàn)階段；圖3（d）所示表示節(jié)點確定其下一跳鄰節(jié)點后，將發(fā)射功率調(diào)整到能保證它們之間通信穩(wěn)定的最小值。

圖3 普通節(jié)點功率控制策略圖Fig.3 Power control strategy of normal node

2.1.3 路由層級劃分與路由規(guī)則

WSN-H系統(tǒng)由多個局部無線傳感器網(wǎng)構(gòu)成，其局部網(wǎng)絡(luò)覆蓋規(guī)模較小，節(jié)點數(shù)量有限，所以，可規(guī)定簇內(nèi)數(shù)據(jù)傳輸?shù)奶鴶?shù)不多于3跳。本文根據(jù)圖論中樹的形成機理，提出將簇內(nèi)進行分層的思想，以保證發(fā)射功率盡可能小且跳數(shù)不大于3。

假設(shè)dmin為簇頭節(jié)點鄰居信息表中最近節(jié)點間距離，dmax為其中最遠距離，簇頭根據(jù)這2個距離d將所有節(jié)點劃分為如下3層：

為提高數(shù)據(jù)轉(zhuǎn)發(fā)效率，提出如下路由規(guī)則：

（1）同級節(jié)點間無數(shù)據(jù)轉(zhuǎn)發(fā)；

（2）節(jié)點只為自己外層節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)；

（3）節(jié)點可向內(nèi)跨層轉(zhuǎn)發(fā)數(shù)據(jù)。

該規(guī)則可使數(shù)據(jù)盡快發(fā)送給簇頭，避免多余的轉(zhuǎn)發(fā)，降低能耗和通信時延，保證簇內(nèi)數(shù)據(jù)傳輸?shù)奶鴶?shù)不多于3跳，從而也保證了時延約束量Δ的限制。

2.2 算法實現(xiàn)

2.2.1 路由發(fā)起

在路由開始階段，節(jié)點查詢其路由鄰居信息表中存儲的發(fā)送給鄰節(jié)點所需的最小發(fā)射功率Pt，選取合適的Pt，調(diào)整發(fā)射功率，使其通信范圍能覆蓋6個左右鄰節(jié)點。然后，節(jié)點廣播路由請求信息（Routing link request,RLR），如圖4（a）所示。RLR中包含了該節(jié)點的標識信息、簇信息和層級信息。鄰節(jié)點收到RLR信息后根據(jù)RR判斷是否應(yīng)答，若應(yīng)答，則反饋路由連接應(yīng)答信息（Routing link answer,RLA），RLA中包含了應(yīng)答節(jié)點的標識信息、層級與剩余能量信息。節(jié)點根據(jù)收到的 RLA 更新路由鄰居信息表中的 Er，level和active信息，然后，根據(jù)如圖4所示的中繼選擇原則選擇下一跳鄰節(jié)點。

圖4 路由發(fā)起示意圖Fig.4 Route initiation schematic

如圖 4（b）所示，節(jié)點接收到多個鄰節(jié)點的反饋RLA信息，即都滿足RR規(guī)則，均可作為下一跳節(jié)點。但需要按照中繼選擇原則選擇唯一的下一跳鄰節(jié)點。本文的中繼選擇原則為：假設(shè)節(jié)點O接收到n條RLA信息，其相應(yīng)鄰節(jié)點的剩余能量分別為Er1，Er2，…，Ern，可計算出n個鄰節(jié)點的平均剩余能量：

從所有滿足式（6）的節(jié)點中選擇距離最近的節(jié)點作為下一跳。從路由鄰居信息表中查詢向該下一跳鄰節(jié)點發(fā)送數(shù)據(jù)所需的最小發(fā)射功率。

該路由選擇方案既減輕了剩余能量少的節(jié)點的負載，又能保證每個節(jié)點都以最合適發(fā)射功率發(fā)送數(shù)據(jù)，從而提高能量利用率。

2.2.2 路由回復(fù)

節(jié)點收到源節(jié)點的路由請求信息 RLR后，根據(jù)RLR中包含的信息和該節(jié)點本身的狀態(tài)，按照RR來決定是否應(yīng)答源節(jié)點的請求。節(jié)點只應(yīng)答本簇內(nèi)外層節(jié)點發(fā)來的RLR信息；此外，節(jié)點決定是否應(yīng)答時應(yīng)充分考慮自身剩余能量，避免能量低的節(jié)點過早死亡。

假設(shè)節(jié)點A經(jīng)節(jié)點B轉(zhuǎn)發(fā)將l比特數(shù)據(jù)給節(jié)點C，A與B的距離為d1，B與C的距離為d2，由于相互層級之間距離一般較小，可認為是式（1）中的自由空間模型，則節(jié)點B將數(shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點C所需的能量為：

考慮到節(jié)點接收數(shù)據(jù)也要消耗一定的能量，文獻[9]提出了接受數(shù)據(jù)的能耗模型，節(jié)點接收l比特數(shù)據(jù)所需能耗ERx（l）為：

故節(jié)點B在轉(zhuǎn)發(fā)l比特數(shù)據(jù)的過程中的總消耗為：

且僅當(dāng)節(jié)點B的剩余能量Er＞E時，才應(yīng)答節(jié)點A發(fā)來的RLA信息，以表示其能提供路由。經(jīng)過節(jié)點間不斷的路由請求和應(yīng)答，整個網(wǎng)絡(luò)最終會形成如圖5所示的同心圓路由樹。

圖5 簇內(nèi)節(jié)點通信同心圓路由樹Fig.5 Concentric routing tree of communication between cluster members

3 仿真與性能分析

利用OPNET工具對EEMRP，EAR和C2TRA進行仿真。這3種多跳的算法網(wǎng)絡(luò)生存時間如圖6所示，分別為684，715和747 s，而簇內(nèi)節(jié)點與簇頭直接一跳通信的EECA網(wǎng)絡(luò)生存時間為648 s，由此可知短距離多跳通信的能量利用效率比遠距離多跳通信的高。網(wǎng)絡(luò)生存時間是衡量算法綜合性能的 1個指標，C2TRA這方面表現(xiàn)最優(yōu)，主要是因為其采取了多跳路由、功率控制及低能量節(jié)點保護等機制，均衡網(wǎng)絡(luò)能耗，提高了網(wǎng)絡(luò)能量利用率。

圖6 網(wǎng)絡(luò)剩余節(jié)點個數(shù)與網(wǎng)絡(luò)生存時間關(guān)系Fig.6 Relationship between numbers of nodes and network sunvival time

3種算法網(wǎng)絡(luò)失效前能耗與發(fā)送數(shù)據(jù)包之間的關(guān)系如圖 7所示。當(dāng)發(fā)送相同數(shù)量的數(shù)據(jù)分組時，C2TRA，EEMRP和EAR消耗的能量依次增大，發(fā)送單位數(shù)據(jù)包平均能耗依次減小。C2TRA算法能夠控制數(shù)據(jù)發(fā)送時的轉(zhuǎn)發(fā)次數(shù)，增強對數(shù)據(jù)發(fā)送方向的導(dǎo)向，避免不必要數(shù)據(jù)的轉(zhuǎn)發(fā)，從而減少額外能耗；同時，網(wǎng)絡(luò)失效時C2TRA可使節(jié)點平均剩余能量最小。由此可知：C2TRA算法能量利用率較高，而EAR能量利用率最低。這主要是其路由中繼選取時需要考慮過多網(wǎng)絡(luò)狀態(tài)信息，且進行迭代計算，復(fù)雜度較高，從而消耗過多額外能量。

圖8所示為網(wǎng)絡(luò)失效前數(shù)據(jù)發(fā)送量與路由開銷的關(guān)系。由于 EAR根據(jù)路徑節(jié)點能耗特征及其剩余能量，按照一定概率選取源節(jié)點到目的節(jié)點多條路由，故發(fā)送數(shù)據(jù)中路由開銷很大，且多數(shù)路由開銷都是無效的。EEMRP通過鏈路代價選擇下一跳，鏈路代價由節(jié)點的剩余能量級別和節(jié)點到目的的節(jié)點跳數(shù)共同決定，這導(dǎo)致節(jié)點每次發(fā)送數(shù)據(jù)都要不斷地試探周圍，增加了不必要的開銷。本文提出的C2TRA在保證鏈路穩(wěn)定的條件下，限制了節(jié)點鄰節(jié)點數(shù)量，使得數(shù)據(jù)傳輸時，路由鏈路相對穩(wěn)定，從而一定程度上比EEMRP進一步降低了路由開銷。

圖7 網(wǎng)絡(luò)失效前數(shù)據(jù)發(fā)送量與網(wǎng)絡(luò)能耗的關(guān)系Fig.7 Relationship between amount of data sent and energy consumption of network

圖8 網(wǎng)絡(luò)失效前數(shù)據(jù)發(fā)送量與路由開銷能耗的關(guān)系Fig.8 Relationship between amount of data sent and energy consumption of routing overhead

圖9所示為網(wǎng)絡(luò)發(fā)送數(shù)據(jù)包與簇頭成功接收數(shù)據(jù)包之間的關(guān)系。圖中曲線反映的是數(shù)據(jù)成功投遞率。由圖9可見：在失效節(jié)點出現(xiàn)前，這3種算法數(shù)據(jù)傳送成功率都較固定，其中 EAR成功率較低，C2TRA成功率較高。這主要是因為C2TRA限制了路由中多跳傳輸?shù)奶鴶?shù)。本文仿真場景中，節(jié)點覆蓋密度較大，節(jié)點間距離較小，若路由中繼選擇時不限制路由跳數(shù)，僅考慮剩余能量，則數(shù)據(jù)路由次數(shù)會明顯增加，數(shù)據(jù)丟失率會加大，從而降低數(shù)據(jù)傳輸成功率。因此，在簇的覆蓋范圍不是很大如高速公路路口的面積一般不大時，WSN-H中的簇就不用覆蓋太遠，限制數(shù)據(jù)轉(zhuǎn)發(fā)跳數(shù)，能大幅地減少數(shù)據(jù)丟失，同時降低網(wǎng)絡(luò)的通信延遲。

以上仿真結(jié)果表明：C2TRA算法能夠有效延長網(wǎng)絡(luò)生存時間，提高網(wǎng)絡(luò)能量利用率。

圖9 網(wǎng)絡(luò)發(fā)送的數(shù)據(jù)包與成功到達簇頭的數(shù)據(jù)包關(guān)系Fig.9 Relationship between number of package sent and nember of package received by cluster head

4 結(jié)論

（1）將 WSN技術(shù)引進了高速公路安全監(jiān)控領(lǐng)域，根據(jù)該領(lǐng)域的背景需求和WSN的組網(wǎng)特征，搭建了高速公路安全監(jiān)控?zé)o線傳感器網(wǎng)絡(luò)WSN-H網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)。

（2）針對無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)生存時間與能量問題，提出了一種基于同心圓路由樹的路由選擇協(xié)議C2TRA，以降低節(jié)點能量消耗，均衡整個網(wǎng)絡(luò)能耗，從而提高了WSN-H中了點能量的利用效率，并延長了該網(wǎng)絡(luò)的生存壽命。仿真結(jié)果表明所提出的算法是有效的。

[1]Li L J,Li X,Cheng C J.Research collaboration and ITS topic evolution:10 years at T-ITS[J].IEEE Transactions on Intelligent Transportation Systems,2010,11（3）:517?523.

[2]Yan E,Ding Y.Topics in Dyanmic research communities:A exploratory study for the field of information retrieval[J].Journal of Informatrics,2012,6（1）:140?153.

[3]Tao M,Lu D.An adaptive energy-aware multi-path routing protocol with load balance for wireless sensor networks[J].Wireless Personal Communication,2010,6（2）:1?24.

[4]尚鳳軍,任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究[J].傳感技術(shù)學(xué)報,2012,25（4）:529?535.SHANG Feng-jun,REN Dong-hai.A distributed multi-hop routing algorthm in wirdess sensor networks[J].Chinese Journal of Sensors and Actuators,2012,25（4）:529?535.

[5]Zhao G,Liu X.Energy-efficient geographic routing with virtual anchors based on projection distance[J].Computer Communications,2008,31（10）:2195?2204.

[6]林益,楊靖.無線傳感器網(wǎng)絡(luò)中路由選擇算法的研究[J].計算機測量與控制,2009,17（1）:252?254.LIN Yi,YANG Jin.Research on routing selection algorithm for wireless sensor networks[J].Computer Measurement and Control,2009,17（1）:252?254.

[7]Lu Y,Wong V.An energy efficiency multipath routing protocol for wireless sensor networks[J].International Journal of Communication Systems,2007,20（7）:1?5.

[8]曾志文,陳志剛,劉安豐.無線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計算機學(xué)報,2010,33（1）:13?14.ZHENG Zi-wen,CHEN Zhi-gang,LIU An-feng.Energy-hole avoidance for WSN based on adjust transmission power[J].Chinese Journal of Computer,2010,33（1）:13?14.

[9]Kleinrock L,Silvester J A.Optimum transmission radii in packet radio networks or why six is a magic number[C]//Proceedings of the IEEE National Telecommunications Conference.Birmingham,1978:431?443.