WSN中基于代價函數的機會路由協議

徐越 童英華 田立勤

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

關鍵詞：無線傳感器網絡;代價函數;機會路由;網絡生命周期;候選節點集;吞吐量

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

0 引 言

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

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

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

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

1 系統模型

1.1 網絡模型

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

1.2 能耗模型

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

k bit數據傳輸到距離為d的地方，所需消耗的能量如下：

式中：Eelec是發送模塊和接收模塊處理1 bit數據所消耗的能量;εfs和εmp均為功率放大所消耗的能量;d為數據傳輸的距離;是兩個模型的閾值，如果d

2 機會路由協議

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

機會路由多節點轉發機制的工作思路如下：

（1）源節點先發送消息以發現鄰居節點;

（2）選擇轉發候選者;

（3）發送確認包;

（4）決定是否轉發接收到的包。

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

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

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

因此，機會路由協議在傳統路由協議的基礎上，利用無線信道廣播的特點，從上述兩個方面減少了重傳次數，提高了單次轉發傳輸的成功率。

3 基于代價函數的路由協議

3.1 代價函數

在對節點的優先級進行排序時，本文采用轉發代價C（x）作為度量標準，在候選節點集中選擇轉發代價C（x）最小的節點作為轉發者。

式中：Pxy是節點x正確將數據包發送到y的正確率，也是節點x到節點y的鏈路質量;d（x， d ），d（y， d ）分別表示節點x和節點y到目標節點的距離;E0表示節點y的初始能量，Ey表示節點y的剩余能量;α，β，γ均為權值函數，且α+β+γ=1。通過式（3）從候選節點集中選擇C（x）最小的節點作為轉發節點，并形成一條從源節點到目標節點的最優路徑。

由上述公式可知，剩余能量越多，傳輸的成本越小。同理，距離越短，節點發送數據包消耗的能量越少，轉發代價越小。鏈路質量好，剩余能量較多的候選節點將被選擇作為數據傳輸節點，既可緩解關鍵節點能量消耗，又能提高數據傳輸成功率，達到高效利用節點能量的效果。

3.2 尋找最優候選節點集

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

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

算法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的工作步驟：有數據發送到目的節點時，首先檢查目的節點是否在自己的鄰居節點中，如果在，就直接發送給目的節點，否則通過優先級算法選取符合要求的目的節點集合M（s）（鄰居節點到目的節點的距離大于本節點到目的節點的距離），計算鄰居節點的優先級概率。優先級排序后選擇優先級最高的節點N作為轉發數據包的節點。

算法2：尋找最優候選節點集

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 仿真結果分析

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

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

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

5 結 語

本文針對機會路由協議中能量有限的問題，提出了基于代價函數的機會路由協議，將代價函數作為選擇網絡中節點的候選節點集的指標，該指標綜合考慮了節點剩余能量、距離和鏈路質量，選擇轉發成本最小的節點作為候選節點進行轉發。仿真結果表明，本文所提的基于代價函數的機會路由協議可以有效提高網絡的吞吐量，延長網絡的生存周期。由于無線傳感器網絡常用于開放性的環境中，傳輸過程中內容容易被截獲，安全系數較低，所以在下一步工作中，可以在協議中加入安全機制，提高數據傳輸的可靠性。

參考文獻

[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]陳志剛，殷濱安，吳嘉.基于消息重要性的機會網絡能量均衡路由算法[J].通信學報，2018，39（12）：91-101.

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

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

[8]姚玉坤，王宇，呂盼成.基于節點編碼感知的機會轉發路由協議

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

[9]姚玉坤，張毅，李娟.基于網絡編碼的WSN機會路由優化算法

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

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

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

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

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

[14]趙宇紅，尹自立，張曉琳.基于節點社會性的機會網絡噴霧等待路由協議[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.