WSNs中基于分布式學(xué)習(xí)機(jī)的穩(wěn)定路由

宋海軍

(中國民航飛行學(xué)院，四川 廣漢 618307)

0 引 言

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)由微型、具有感知和通信能力的節(jié)點(diǎn)組成。通過這些節(jié)點(diǎn)監(jiān)測興趣區(qū)域環(huán)境數(shù)據(jù)，如溫度、濕度，或檢測區(qū)域內(nèi)異常事件，再將這感知數(shù)據(jù)傳輸至信宿，進(jìn)而實(shí)現(xiàn)對環(huán)境監(jiān)測目的，如森林防火監(jiān)測。

WSNs內(nèi)的節(jié)點(diǎn)不僅感知數(shù)據(jù)，還需傳輸或協(xié)助其他節(jié)點(diǎn)向信宿傳輸數(shù)據(jù)[2]。而傳輸數(shù)據(jù)消耗了節(jié)點(diǎn)的大部分能量。然而，節(jié)點(diǎn)通常由電池供電，屬于有限資源，一旦電池耗盡，節(jié)點(diǎn)就無法繼續(xù)工作。此外，多數(shù)基于WSNs的監(jiān)測應(yīng)用對數(shù)據(jù)傳輸時(shí)延有一定的要求，即需在限定的時(shí)間內(nèi)完成數(shù)據(jù)傳輸。

路由協(xié)議承擔(dān)了網(wǎng)絡(luò)內(nèi)數(shù)據(jù)傳輸?shù)呢?zé)任。高質(zhì)量的可靠路由協(xié)議能減少節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，縮短數(shù)據(jù)傳輸時(shí)延[3-4]，減少節(jié)點(diǎn)能耗。然而，由于WSNs路由受多方面因素影響，實(shí)現(xiàn)服務(wù)質(zhì)量(Quality of Service, QoS)路由存在挑戰(zhàn)。

QoS路由需考慮多項(xiàng)因素，如端到端可靠性、時(shí)延、能效。而這些因素往往又是相互矛盾的。因此，在實(shí)際情況下，采用準(zhǔn)QoS路由。準(zhǔn)QoS路由是指路由以一定概率滿足QoS要求[5]。

文獻(xiàn)[6]利用多路徑滿足QoS要求。確實(shí)，通過多條路徑傳輸數(shù)據(jù)能夠?qū)崿F(xiàn)QoS要求，但是多路徑也存在不足：多條路徑需要多個(gè)節(jié)點(diǎn)構(gòu)成路由，這就增加了參與路由的節(jié)點(diǎn)數(shù)，必然就增加網(wǎng)絡(luò)能耗。同時(shí)，多個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)，可能會形成彼此干擾。因此，需要單條路徑完成QoS要求。而選擇一條滿足多項(xiàng)因素的路徑是多約束路徑優(yōu)化問題，這是一個(gè)NP問題。

為此，提出基于分布式學(xué)習(xí)機(jī)的穩(wěn)定路由(Reliable Routing with Distributed Learning Automation, RRDLA)路由。RRDLA路由將選擇單一端到端可靠性和時(shí)延要求的路徑問題看成多約束優(yōu)化問題，再利用學(xué)習(xí)機(jī)求解優(yōu)化問題。仿真結(jié)果表明，提出的RRDLA路由有效地提高路由的穩(wěn)定性，增加了數(shù)據(jù)包傳遞率，并減少了能耗。

1 預(yù)備知識

1.1 約束條件

n個(gè)節(jié)點(diǎn)隨機(jī)分布于監(jiān)測區(qū)域，它們形成節(jié)點(diǎn)集V={υ0,υ1,υ2,…,υn}，其中υ0表示信宿。令Rs、Rc表示節(jié)點(diǎn)感測范圍、通信范圍。如圖1所示。如圖2所示。通常，Rs≥Rc。

圖1 節(jié)點(diǎn)的感測和通信模型

假定媒體接入控制協(xié)議(Medium Access Control, MAC)提供估計(jì)鏈路質(zhì)量的數(shù)據(jù)，即數(shù)據(jù)包接收率(Packet Reception Ratio, PRR)。且每個(gè)節(jié)點(diǎn)知曉其一跳鄰居節(jié)點(diǎn)的PRR。本文將利用PRR估計(jì)鏈路的可靠性。

令P(u,υ)表示節(jié)點(diǎn)u與節(jié)點(diǎn)υ鏈路的PRR。若一條路徑由m條鏈路構(gòu)成，則該條路徑的數(shù)據(jù)包傳遞率(Packet Delivery Ratio, PDR)等于這m條鏈路的PRR的乘積。

類似地，令P(u,υ)表示節(jié)點(diǎn)u與節(jié)點(diǎn)υ鏈路的數(shù)據(jù)傳輸時(shí)延，若一條路徑由m條鏈路構(gòu)成，則該條路徑的數(shù)據(jù)傳輸時(shí)延等于這m條鏈路的時(shí)延之和。

1.2 學(xué)習(xí)機(jī)概述

學(xué)習(xí)自動機(jī)(Learning Automata, LA)是解決優(yōu)化問題的有效技術(shù)。每個(gè)LA均保持有限的動作集，且每個(gè)動作均對應(yīng)一個(gè)概率[7]。最初，LA隨機(jī)地選擇動作，然后外界環(huán)境針對此動作產(chǎn)生反饋信號(獎勵(lì)或懲罰)，進(jìn)而修正選擇此動作的概率，如圖2所示。通過不斷迭代，最終，LA能夠從動作集中學(xué)習(xí)一個(gè)最優(yōu)的動作。

圖2 LA模型

可用E={α,β,c}表示LA模型，其中α={α1,α2,…,αn}為動作集，而β={β1,β2,…,βn}表示反饋信號。c={c1,c2,…,cn}為懲罰概率，其元素值與α={α1,α2,…,αn}內(nèi)值一一對應(yīng)。

引用T表示LA的學(xué)習(xí)算法，其定義如式(1)所示：

p(n+1)=T[p(n),α(n),β(n)]

(1)

其中p(n)動作概率矢量。

LA依據(jù)動作概率集p，學(xué)習(xí)機(jī)隨機(jī)地選擇一個(gè)動作αi，再將此動作作用于環(huán)境。收到環(huán)境反饋的信號后，學(xué)習(xí)機(jī)就依式(2)或式(3)更新動作概率。

若收到的是獎勵(lì)信號(β(n)=0)，就依式(2)更新：

(2)

若收到的是懲罰信號(β(n)=1)，就依式(3)更新：

(3)

其中λ、γ分別表示獎勵(lì)、懲罰因子。而r為動作集數(shù)。

2 RRDLA路由

2.1 初始階段

為了形成動作集，每個(gè)節(jié)點(diǎn)(假定是節(jié)點(diǎn)υi)先向鄰居節(jié)點(diǎn)傳輸請求建立動作集(Request Form Action, RFA)消息。一旦收到RFA消息，節(jié)點(diǎn)就回復(fù)請求建立動作集(Reply Form Action, P-RFA)消息。節(jié)點(diǎn)υi收集來自鄰居節(jié)點(diǎn)的P-RFA消息后，就可建立自己的動作集[8]。

實(shí)質(zhì)上，動作集可以理解為節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)。原因在于：節(jié)點(diǎn)需要傳輸數(shù)據(jù)，它需要從鄰居節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)。若有m個(gè)一跳鄰居節(jié)點(diǎn)，則它就有m個(gè)可能的動作。此處的動作可理解為選擇節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

每個(gè)動作對應(yīng)一個(gè)概率。學(xué)習(xí)機(jī)就是依據(jù)概率選擇動作的。最初，節(jié)點(diǎn)就依據(jù)動作集內(nèi)動作數(shù)，即節(jié)點(diǎn)數(shù)的倒數(shù)為動作概率。因此，最初，同一個(gè)動作集內(nèi)的所有動作具有相同概率。

圖3 構(gòu)建初始動作集示例

以圖3為例，假定節(jié)點(diǎn)A為源節(jié)點(diǎn)，它需要向信宿(節(jié)點(diǎn)J)傳輸數(shù)據(jù)，如圖3(a)所示。依據(jù)圖3(a)的拓?fù)浣Y(jié)構(gòu)所示，節(jié)點(diǎn)A有二個(gè)鄰居節(jié)點(diǎn){B,C}。相對應(yīng)的，它具有兩個(gè)動作{α1,α2}。它們的初始概率為{0.5,0.5}。

2.2 學(xué)習(xí)階段

當(dāng)節(jié)點(diǎn)需要傳輸數(shù)據(jù)(假定是節(jié)點(diǎn)υi)時(shí)，它就隨機(jī)選擇一個(gè)動作，即從鄰居節(jié)點(diǎn)集中隨機(jī)選擇一個(gè)節(jié)點(diǎn)(假定是節(jié)點(diǎn)υj)，并向節(jié)點(diǎn)υj傳輸一個(gè)激活數(shù)據(jù)包。一旦收該激活包，節(jié)點(diǎn)υj也隨機(jī)選擇一個(gè)動作，直到數(shù)據(jù)遍歷信宿。最終，將這些被選擇的節(jié)點(diǎn)加入至路由節(jié)點(diǎn)集Node_Rout。Node_Rout集是指構(gòu)建從源節(jié)點(diǎn)至信宿的路由的節(jié)點(diǎn)集合。

LA對每個(gè)動作進(jìn)行反饋，從而選擇最優(yōu)路由節(jié)點(diǎn)集，進(jìn)而構(gòu)建穩(wěn)定的路徑。將已選的動作作用于環(huán)境，環(huán)境再對動作進(jìn)行反饋，再對所選擇的動作進(jìn)行獎勵(lì)或懲罰，最終更新每個(gè)動作的概率。

具體而言，若已選的路徑的時(shí)延小于當(dāng)前迭代的路徑時(shí)延，并且路徑的PDR高于當(dāng)前，則就需對當(dāng)前的動作進(jìn)行獎勵(lì)。否則，就是對當(dāng)前的動作進(jìn)行懲罰。

即當(dāng)β(n)=0時(shí)，信宿就對該動作獎勵(lì)。并依據(jù)式(2)更新概率。若β(n)=1，信宿就對動作懲罰，并依據(jù)式(3)更新概率。

仍以圖3為例，分析動作更新過程。最初，節(jié)點(diǎn)A隨機(jī)地選擇一個(gè)動作(假定選擇了動作α1)。然后，節(jié)點(diǎn)A就向節(jié)點(diǎn)C傳輸數(shù)據(jù)，并激活節(jié)點(diǎn)C的學(xué)習(xí)機(jī)。

節(jié)點(diǎn)C再隨機(jī)地選擇一個(gè)動作(假定選擇了動作α2)，并傳輸數(shù)據(jù)包激活它。當(dāng)節(jié)點(diǎn)A選擇節(jié)點(diǎn)C后，節(jié)點(diǎn)A就修改它的動作集，即禁用(disabled)節(jié)點(diǎn)B。

當(dāng)節(jié)點(diǎn)G的LA被激活后，它就需要選擇一個(gè)動作，最終，就能到達(dá)信宿(節(jié)點(diǎn)J)。則本次迭代，就構(gòu)成了Node_Rout={A,C,G,J}。即形成了路徑A→C→G→J。整個(gè)過程如圖4所示。表1顯示動作集的概率。

表1 動作集的最終概率

2.3 數(shù)據(jù)傳輸階段

學(xué)習(xí)階段后，就進(jìn)入數(shù)據(jù)傳輸階段。在數(shù)據(jù)傳輸階段，將Node_Rout內(nèi)的節(jié)點(diǎn)，并傳輸數(shù)據(jù)包。如圖4所示。

圖4 選擇節(jié)點(diǎn)示例

3 性能仿真

利用NS-2.34軟件建立仿真平臺[9]，分析RRDLA路由性能。N個(gè)傳感節(jié)點(diǎn)分布于150 m×150 m區(qū)域。具體的仿真參數(shù)如表2所示。

表2 仿真參數(shù)

同時(shí)，選擇文獻(xiàn)[10]提出的可靠的能效路由(Reliable Energy-Efficient Routing, REER)和文獻(xiàn)[11]提出的時(shí)延-能量權(quán)衡的可靠通信(Delay-Energy tradeoff with reliable communication, DETR)路由作為參照，并分析它們的端到端時(shí)延、數(shù)據(jù)包傳遞率、網(wǎng)絡(luò)壽命和數(shù)據(jù)包傳輸次數(shù)。

3.1 數(shù)據(jù)分析

3.1.1端到端傳輸時(shí)延

首先，分析傳輸數(shù)據(jù)的端到端傳輸時(shí)延。從圖5可知，RRDLA路由的端到端傳輸時(shí)延最低。原因在于：學(xué)習(xí)機(jī)考慮了數(shù)據(jù)傳輸時(shí)延因素，并通過時(shí)延決策是否對動作進(jìn)行獎勵(lì)或懲罰。此外，相比于DETR和REER路由，RRDLA路由的時(shí)延隨節(jié)點(diǎn)數(shù)的增加而保持穩(wěn)定。

圖5 端到端傳輸時(shí)延

3.1.2數(shù)據(jù)包傳遞率

圖6顯示了RRDLA、DETR和REER路由的數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況。

圖6 數(shù)據(jù)包傳遞率

從圖6可知，數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的增加而呈上升趨勢。這主要是因?yàn)椋壕W(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)越多，可選的路徑數(shù)就越多，建立穩(wěn)定路徑的可能性越高。相比于DETR和REER，提出的RRDLA路由保持高的數(shù)據(jù)包傳遞率。

3.1.3網(wǎng)絡(luò)壽命

接下來，分析網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)數(shù)的變化情況。引用文獻(xiàn)[12]的能量模型計(jì)算網(wǎng)絡(luò)壽命。網(wǎng)絡(luò)壽命是指從部署節(jié)點(diǎn)至網(wǎng)絡(luò)內(nèi)第一個(gè)節(jié)點(diǎn)因能量消耗殆盡的時(shí)間差。

圖7 網(wǎng)絡(luò)壽命

從圖7可知，相比于DETR和REER，RRDLA路由在網(wǎng)絡(luò)壽命方面獲取良好的性能。原因在于：RRDLA路由通過減少參與路由的節(jié)點(diǎn)，減少網(wǎng)絡(luò)能耗，進(jìn)而提高了網(wǎng)絡(luò)壽命。

3.1.4數(shù)據(jù)包的平均傳輸次數(shù)

最后，分析節(jié)點(diǎn)數(shù)對傳輸數(shù)據(jù)包的次數(shù)的影響。數(shù)據(jù)包的平均傳輸次數(shù)反映了從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的跳數(shù)。從圖8可知，RRDLA路由以少的傳輸次數(shù)完成數(shù)據(jù)包的傳輸。這也說明：RRDLA路由能夠選擇最優(yōu)路徑，并能夠穩(wěn)定地傳輸數(shù)據(jù)包。

圖8 數(shù)據(jù)包的平均傳輸次數(shù)

4 總 結(jié)

針對WSNs的QoS服務(wù)質(zhì)量路由，提出基于分布式學(xué)習(xí)機(jī)的穩(wěn)定路由RRDLA。RRDLA路由利用學(xué)習(xí)機(jī)解決尋找多路徑優(yōu)化問題。通過學(xué)習(xí)機(jī)找到最優(yōu)的路徑，進(jìn)而提高路由的穩(wěn)定性，并減少網(wǎng)絡(luò)能耗。仿真結(jié)果表明，提出的RRDLA路由有效地提高路由穩(wěn)定性，提高了數(shù)據(jù)包傳遞率，并控制了能效。