WSN中基于代價(jià)函數(shù)的機(jī)會路由協(xié)議

徐越 童英華 田立勤

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

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

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2020）05-00-04

0 引 言

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

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

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

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

1 系統(tǒng)模型

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

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

1.2 能耗模型

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

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

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

2 機(jī)會路由協(xié)議

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

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

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

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

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

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

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

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

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

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

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

3.1 代價(jià)函數(shù)

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

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

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

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

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

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

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

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

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平臺進(jìn)行仿真實(shí)驗(yàn)，選用802.11Mac協(xié)議，將基于代價(jià)函數(shù)的機(jī)會路由協(xié)議與傳統(tǒng)的ExOR協(xié)議進(jìn)行比較，傳感器節(jié)點(diǎn)部署在一個200 m×200 m的區(qū)域內(nèi)，具體仿真參數(shù)設(shè)置見表1所列。

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

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

5 結(jié) 語

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

參考文獻(xiàn)

[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ī)會網(wǎng)絡(luò)能量均衡路由算法[J].通信學(xué)報(bào)，2018，39（12）：91-101.

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

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

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

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

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

[J].計(jì)算機(jī)工程，2018，44（6）：68-73.

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

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

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

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

[14]趙宇紅，尹自立，張曉琳.基于節(jié)點(diǎn)社會性的機(jī)會網(wǎng)絡(luò)噴霧等待路由協(xié)議[J].計(jì)算機(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.