徐越 童英華 田立勤

摘 要：在無線傳感器網(wǎng)絡中，因為節(jié)點自身的能量十分有限，容易出現(xiàn)能量過早耗盡，導致節(jié)點過早死亡的問題。針對該問題，文中提出了一種基于代價函數(shù)的機會路由協(xié)議。該協(xié)議采用代價函數(shù)作為優(yōu)先級指標，在綜合考慮剩余能量、節(jié)點間距離和鏈路質(zhì)量的情況下，選擇轉(zhuǎn)發(fā)成本較低的鄰居節(jié)點作為候選節(jié)點，并選擇一條最優(yōu)的路徑進行傳輸，以緩解關鍵節(jié)點的能量消耗，解決網(wǎng)絡負載不均勻問題，提高數(shù)據(jù)傳輸成功率。仿真結(jié)果表明，相比傳統(tǒng)的機會路由協(xié)議ExOR，基于代價函數(shù)的機會路由協(xié)議提高了數(shù)據(jù)的吞吐量，從而延長了網(wǎng)絡的生存周期。

關鍵詞：無線傳感器網(wǎng)絡;代價函數(shù);機會路由;網(wǎng)絡生命周期;候選節(jié)點集;吞吐量

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2020）05-00-04

0 引 言

無線傳感器網(wǎng)絡（Wireless Sensor Networks，WSN）已廣泛應用于軍事、商業(yè)、環(huán)境監(jiān)測等領域，可為用戶提供較為連續(xù)的數(shù)據(jù)采集與傳輸服務。但由于無線傳感器在鏈路中的不可靠性，采用傳統(tǒng)的路由協(xié)議可能會造成大量數(shù)據(jù)重傳，導致節(jié)點能量的浪費。因此，Biswas[1]等人提出了機會路由協(xié)議（ExOR），該協(xié)議充分利用了無線通信的廣播特性，從多個候選節(jié)點中選出轉(zhuǎn)發(fā)節(jié)點，從而提高了數(shù)據(jù)傳輸?shù)目煽啃?，減少了數(shù)據(jù)重傳的次數(shù)，大幅降低了節(jié)點的能量消耗，與傳統(tǒng)的路由協(xié)議相比，機會路由有效延長了網(wǎng)絡的生命周期。

對于節(jié)能機會路由協(xié)議，國內(nèi)外學者已經(jīng)進行了大量研究。文獻[2]提出了一種能量有效的機會路由（EEOR），該協(xié)議使用預期成本作為路由指標，并在固定傳輸功率或動態(tài)可調(diào)情況下優(yōu)化轉(zhuǎn)發(fā)列表，選擇最優(yōu)轉(zhuǎn)發(fā)節(jié)點，使節(jié)點能耗最小化。文獻[3]提出了一種能量有效的機會路由協(xié)議，該協(xié)議以期望成本為路由指標，計算消息傳輸過程中的成本。文獻[4]提出了基于PSO的聚類算法，該算法通過考慮傳輸距離與跳數(shù)，平衡了節(jié)點間的能量消耗，延長了網(wǎng)絡生命周期。文獻[5]提出了一種基于消息重要性的能量均衡路由算法，該算法對消息重要性進行度量，并根據(jù)消息轉(zhuǎn)發(fā)收益確定消息的轉(zhuǎn)發(fā)順序和路由，在節(jié)點緩存空間不足時，會依據(jù)消息緩存價值進行緩存替換。文獻[6]提出一種基于剩余能量的機會路由協(xié)議，以剩余傳輸次數(shù)為度量指標來確定候選節(jié)點集中節(jié)點的優(yōu)先級，從而提高網(wǎng)絡的生存周期。文

獻[7]提出了一種基于EIETX的自適應功率控制的機會路由協(xié)議APExOR，通過建立轉(zhuǎn)發(fā)能耗模型來優(yōu)化轉(zhuǎn)發(fā)候選集和發(fā)射功率，以降低網(wǎng)絡的能量消耗。文獻[8]提出了一種適用于多跳無線網(wǎng)絡的節(jié)點編碼感知機會轉(zhuǎn)發(fā)路由協(xié)議，通過引入基于偵聽概率的附加ID信息添加機制、最優(yōu)轉(zhuǎn)發(fā)節(jié)點選擇機制和數(shù)據(jù)包的高效緩存機制，提高網(wǎng)絡吞吐量和編碼包的解碼成功率，減小數(shù)據(jù)包的平均端到端時延。文獻[9]提出了一種基于網(wǎng)絡編碼的機會路由優(yōu)化算法，通過信道誤碼率和丟包率計算節(jié)點接收編碼包失敗的概率，以減少編碼包的重傳次數(shù)。同時通過減少選擇主轉(zhuǎn)發(fā)節(jié)點的時間以及網(wǎng)絡開銷來降低網(wǎng)絡中節(jié)點的能耗，以延長網(wǎng)絡的生命周期。文獻[10]提出了能耗和延遲平衡的機會路由協(xié)議，它通過估算預期能耗值來選擇能耗較低的鄰居節(jié)點作為候選節(jié)點，在平衡能耗和延遲性能方面做了優(yōu)化。文獻[11]提出了基于排序轉(zhuǎn)發(fā)列表的機會路由協(xié)議，通過選擇到目標節(jié)點最小距離的節(jié)點加入轉(zhuǎn)發(fā)列表，來最大限度減少能源的消耗。文獻[12]提出了一種適用于BLE Mesh網(wǎng)絡的機會路由優(yōu)化協(xié)議，它將ETX作為優(yōu)先級指標來選擇轉(zhuǎn)發(fā)節(jié)點并運用于BLE Mesh網(wǎng)絡中，優(yōu)化協(xié)調(diào)策略和后備節(jié)點維護策略，減小通信時延，提升吞吐量。文獻[13]提出了一個自適應機會路由協(xié)議—負載均衡的機會路由協(xié)議，該協(xié)議在考慮節(jié)點到目標節(jié)點距離的基礎上還考慮了PLC鏈路的不穩(wěn)定性以及流量的變化，并將此作為優(yōu)先級指標。文獻[14]提出一種基于節(jié)點社會性的噴霧等待路由協(xié)議，它通過節(jié)點的社會屬性、移動模式和對消息的轉(zhuǎn)發(fā)效能來對中繼節(jié)點的選擇進行優(yōu)化，從而改善消息投遞率和傳輸延遲的問題。

在這些已有機會路由協(xié)議的基礎上，本文提出了一種基于轉(zhuǎn)發(fā)代價的機會路由協(xié)議（Cost Function-based Opportunistic Routing Protocol，CFOR），以能量代價函數(shù)作為選擇轉(zhuǎn)發(fā)節(jié)點的指標，得到最優(yōu)的傳輸路徑，從而改善網(wǎng)絡中節(jié)點能量的均衡性。

1 系統(tǒng)模型

1.1 網(wǎng)絡模型

假設有n個同構(gòu)的傳感器節(jié)點隨機且靜止的分布在監(jiān)測區(qū)域內(nèi)，每個節(jié)點有唯一的ID，所有傳感器節(jié)點的傳輸功率、傳輸范圍相同。然后用通信圖G =（V， E）對多跳無線網(wǎng)絡進行建模，其中V表示傳感器節(jié)點集，E表示網(wǎng)絡中所有無線鏈路的集合。

1.2 能耗模型

本文采用文獻[15]中的first-order能量模型，節(jié)點將

k bit數(shù)據(jù)傳輸?shù)骄嚯x為d的地方，所需消耗的能量如下：

式中：Eelec是發(fā)送模塊和接收模塊處理1 bit數(shù)據(jù)所消耗的能量;εfs和εmp均為功率放大所消耗的能量;d為數(shù)據(jù)傳輸?shù)木嚯x;是兩個模型的閾值，如果d

2 機會路由協(xié)議

機會路由是針對無線多跳網(wǎng)絡信息廣播特性、有損特性提出的一種路由協(xié)議，與傳統(tǒng)路由協(xié)議不同的是，它的傳輸路徑并不是固定的。在機會路由中源節(jié)點將原本向目的節(jié)點發(fā)送的數(shù)據(jù)包先發(fā)送給鄰居節(jié)點進行數(shù)據(jù)包的轉(zhuǎn)發(fā)，該轉(zhuǎn)發(fā)節(jié)點由多個候選節(jié)點的競爭選擇產(chǎn)生，由此帶來比傳統(tǒng)固定路徑無線路由更高的傳輸可靠性以及端到端的吞吐量。

機會路由多節(jié)點轉(zhuǎn)發(fā)機制的工作思路如下：

（1）源節(jié)點先發(fā)送消息以發(fā)現(xiàn)鄰居節(jié)點;

（2）選擇轉(zhuǎn)發(fā)候選者;

（3）發(fā)送確認包;

（4）決定是否轉(zhuǎn)發(fā)接收到的包。

轉(zhuǎn)發(fā)序列的第一個節(jié)點是在它所有的鄰居節(jié)點中選擇一個能夠把數(shù)據(jù)包傳遞給離目的節(jié)點更近的候選者子集，發(fā)送者把該集合列在包頭中，用機會算法來劃分優(yōu)先級。傳輸后，每個接收到數(shù)據(jù)包的節(jié)點在包頭的候選者列表中尋找它的地址，每個接收者依據(jù)它在列表里的位置，在發(fā)送確認包之前延遲一段時間。各節(jié)點查看收到的確認包集合來決定是否轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)節(jié)點用新的候選者列表重寫數(shù)據(jù)包幀頭，然后轉(zhuǎn)發(fā)包。

如圖1所示，假設源節(jié)點S向中間節(jié)點V1～Vn傳輸數(shù)據(jù)的成功率相同且均為25%，則這n個中間節(jié)點都有可能作為下一跳接收到數(shù)據(jù)包轉(zhuǎn)發(fā)給目的節(jié)點D，且數(shù)據(jù)傳輸?shù)某晒β蕿?-（1-25%）n，其中n>1，比選擇一個中間節(jié)點作為傳輸固定路徑的傳輸成功率高。

如圖2所示，雖然直接將數(shù)據(jù)包從源節(jié)點S發(fā)送給目的節(jié)點D是最簡單的方法，但是可能由于鏈路質(zhì)量的問題導致傳輸成功率僅為10%，而機會路由采用了多節(jié)點轉(zhuǎn)發(fā)機制，選擇S，A，B，D的路徑成功率高達72.9%，該方法減少了數(shù)據(jù)重傳的次數(shù)，從而節(jié)約了網(wǎng)絡資源。

因此，機會路由協(xié)議在傳統(tǒng)路由協(xié)議的基礎上，利用無線信道廣播的特點，從上述兩個方面減少了重傳次數(shù)，提高了單次轉(zhuǎn)發(fā)傳輸?shù)某晒β省?/p>

3 基于代價函數(shù)的路由協(xié)議

3.1 代價函數(shù)

在對節(jié)點的優(yōu)先級進行排序時，本文采用轉(zhuǎn)發(fā)代價C（x）作為度量標準，在候選節(jié)點集中選擇轉(zhuǎn)發(fā)代價C（x）最小的節(jié)點作為轉(zhuǎn)發(fā)者。

式中：Pxy是節(jié)點x正確將數(shù)據(jù)包發(fā)送到y(tǒng)的正確率，也是節(jié)點x到節(jié)點y的鏈路質(zhì)量;d（x， d ），d（y， d ）分別表示節(jié)點x和節(jié)點y到目標節(jié)點的距離;E0表示節(jié)點y的初始能量，Ey表示節(jié)點y的剩余能量;α，β，γ均為權(quán)值函數(shù)，且α+β+γ=1。通過式（3）從候選節(jié)點集中選擇C（x）最小的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，并形成一條從源節(jié)點到目標節(jié)點的最優(yōu)路徑。

由上述公式可知，剩余能量越多，傳輸?shù)某杀驹叫?。同理，距離越短，節(jié)點發(fā)送數(shù)據(jù)包消耗的能量越少，轉(zhuǎn)發(fā)代價越小。鏈路質(zhì)量好，剩余能量較多的候選節(jié)點將被選擇作為數(shù)據(jù)傳輸節(jié)點，既可緩解關鍵節(jié)點能量消耗，又能提高數(shù)據(jù)傳輸成功率，達到高效利用節(jié)點能量的效果。

3.2 尋找最優(yōu)候選節(jié)點集

在本文中，C（x）指標被用來選擇節(jié)點的候選節(jié)點集。在基于代價函數(shù)的路由協(xié)議中，通過最小化節(jié)點的C（x）指標可以有效減少節(jié)點能量的消耗，提高數(shù)據(jù)傳輸成功率。

在算法1中，節(jié)點先周期發(fā)送廣播包，廣播包中包含節(jié)點的位置信息（x， y），成功率p和剩余能量LeftEnergy，鄰居節(jié)點接收到廣播包后建立鄰居信息表。

算法1：建立鄰居集合

Input：Topo Node

Oupt：Neighbor

（1）All Nordes send hello {x，y，p，LeftEnergy}

（2）node receive the hello from neighboring Nordes，and make neighboring Nordes table M（s）

（3）if（hello->LeftEnergy > 0）

（4）node insert M（s）

（5）else

（6）remove node from M（s）

算法2的工作步驟：有數(shù)據(jù)發(fā)送到目的節(jié)點時，首先檢查目的節(jié)點是否在自己的鄰居節(jié)點中，如果在，就直接發(fā)送給目的節(jié)點，否則通過優(yōu)先級算法選取符合要求的目的節(jié)點集合M（s）（鄰居節(jié)點到目的節(jié)點的距離大于本節(jié)點到目的節(jié)點的距離），計算鄰居節(jié)點的優(yōu)先級概率。優(yōu)先級排序后選擇優(yōu)先級最高的節(jié)點N作為轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點。

算法2：尋找最優(yōu)候選節(jié)點集

Input：destination node Sink Position，neighboring Nordes table M（s）

Output：best next hop node

（1）receive data packet

（2）if（DestAddress==MyAddress）

（3）send packet to sink

（4）else

（5）for（i=0;i

（6）calculate the best next hop N

（7）

（8）if （C（x）

（9）N=x，C（N）=C（x）

（10）if（N==-1）

（11）do not have next hop

（12）else

（13）output N

4 仿真結(jié)果分析

本文采用OPNET平臺進行仿真實驗，選用802.11Mac協(xié)議，將基于代價函數(shù)的機會路由協(xié)議與傳統(tǒng)的ExOR協(xié)議進行比較，傳感器節(jié)點部署在一個200 m×200 m的區(qū)域內(nèi)，具體仿真參數(shù)設置見表1所列。

在通信距離為50 m時，節(jié)點數(shù)目分別為50個，100個，隨著時間的增加節(jié)點失效的數(shù)目分別如圖3、圖4所示。保持通信距離不變，增大網(wǎng)絡內(nèi)節(jié)點的數(shù)目，可以看出傳統(tǒng)的機會路由算法在仿真開始約1 min已有節(jié)點失效，僅僅依靠鄰居節(jié)點和Sink節(jié)點的地理位置信息來確定中間轉(zhuǎn)發(fā)節(jié)點。在這種情況下，認為在傳輸范圍內(nèi)，距離Sink節(jié)點越近，路徑越優(yōu)。這樣在網(wǎng)絡初始過程中，會造成頻繁使用某一節(jié)點作為中間節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)，直至該節(jié)點能量耗盡失效，而其他節(jié)點存在能量冗余的現(xiàn)象，網(wǎng)絡整體失效后，能量無法得到有效利用。采用改進的機會路由算法后，網(wǎng)絡能耗能均勻分布到鄰居節(jié)點中，使網(wǎng)絡生存時間增加，直到周圍節(jié)點能量基本耗盡時，在第14 min時集中失效，基本達到網(wǎng)絡最長生存時間。

從圖5、圖6可以看出，當網(wǎng)絡運行到達一定時間時，節(jié)點每秒平均接收的能量會突然減少，相較于傳統(tǒng)的機會路由協(xié)議，基于代價函數(shù)的機會路由協(xié)議能將節(jié)點的能量平均分配到各節(jié)點上，在50個中間節(jié)點范圍內(nèi)，基于距離的機會路由算法的生存時間約為10 min，而改進的機會路由算法能達到14 min，使得網(wǎng)絡節(jié)點的生存時間更長。

5 結(jié) 語

本文針對機會路由協(xié)議中能量有限的問題，提出了基于代價函數(shù)的機會路由協(xié)議，將代價函數(shù)作為選擇網(wǎng)絡中節(jié)點的候選節(jié)點集的指標，該指標綜合考慮了節(jié)點剩余能量、距離和鏈路質(zhì)量，選擇轉(zhuǎn)發(fā)成本最小的節(jié)點作為候選節(jié)點進行轉(zhuǎn)發(fā)。仿真結(jié)果表明，本文所提的基于代價函數(shù)的機會路由協(xié)議可以有效提高網(wǎng)絡的吞吐量，延長網(wǎng)絡的生存周期。由于無線傳感器網(wǎng)絡常用于開放性的環(huán)境中，傳輸過程中內(nèi)容容易被截獲，安全系數(shù)較低，所以在下一步工作中，可以在協(xié)議中加入安全機制，提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

參考文獻

[1] BISWAS S，MORRIS R. ExOR：Opportunistic multi-hop routing for wireless networks（conference paper）[J]. Computer communication review，2005，35（4）：133-144.

[2] MAO X，TANG S，XU X，et al. Energy-efficient opportunistic routing in wireless sensor networks [J]. IEEE transactions on parallel & distributed systems，2011，22（11）：1934-1942.

[3] SAHOO J，SALAHUDDIN M A，GLITHO R，et al. A survey on replica server placement algorithms for content delivery networks（review）[J]. IEEE communications surveys and tutorials，2017，19（2）：1002-1026.

[4] KUILA P，JANA P K. Energy efficient clustering and routing algorithms for wireless sensor networks：particle swarm optimization approach [J]. Engineering applications of artificial intelligence，2014，33（8）：127-140.

[5]陳志剛，殷濱安，吳嘉.基于消息重要性的機會網(wǎng)絡能量均衡路由算法[J].通信學報，2018，39（12）：91-101.

[6]呂曉軍，王小書，賈新春，等.WSNs中基于剩余能量的機會路由協(xié)議[J].計算機工程與設計，2018，39（11）：3301-3305.

[7]張大鵬，康會莉，王新生.WSNs中一種基于EIETX的自適應功率控制的機會路由[J].傳感器與微系統(tǒng)，2013，32（3）：43-45.

[8]姚玉坤，王宇，呂盼成.基于節(jié)點編碼感知的機會轉(zhuǎn)發(fā)路由協(xié)議

[J].電子技術(shù)應用，2017，43（9）：119-122.

[9]姚玉坤，張毅，李娟.基于網(wǎng)絡編碼的WSN機會路由優(yōu)化算法

[J].計算機工程，2018，44（6）：68-73.

[10]高宏超，陳曉江，徐丹，等.無源感知網(wǎng)絡中能耗和延遲平衡的機會路由協(xié)議[J].軟件學報，2019，30（8）：2528-2544.

[11]劉友武，王晶，劉持標.WSN中基于排序轉(zhuǎn)發(fā)列表的機會路由協(xié)議[J].重慶理工大學學報（自然科學版），2019，33（5）：161-167.

[12]孫吉武，江凌云.BLE Mesh網(wǎng)絡中的機會路由協(xié)議優(yōu)化[J].南京郵電大學學報（自然科學版），2018，38（6）：90-95.

[13]李祝紅，趙燦明，閆龍，等.智能電網(wǎng)中電力線通信網(wǎng)絡負載均衡的機會路由協(xié)議[J].計算機應用，2019，39（3）：812-816.

[14]趙宇紅，尹自立，張曉琳.基于節(jié)點社會性的機會網(wǎng)絡噴霧等待路由協(xié)議[J].計算機仿真，2018，35（7）：231-236.

[15] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE transactions on wireless communications，2002，1（4）：660-670.