無線傳感器網絡強化學習增強路由研究

張華南，李石君，金 紅

1.廣東培正學院數據科學與計算機學院，廣東 廣州 510830

2.武漢大學計算機學院，湖北 武漢 430072

3.湖北大學計算機與信息工程學院，湖北 武漢 430062

無線傳感器網絡（wireless sensor networks,WSN）通過相互連接的傳感器設備實現了數據采集、數據傳輸與數據分析。實時監控系統是傳感器網絡的一個重要應用，傳感器節點收集數據并通過多跳傳輸轉發給匯聚節點，系統對實時通信有很強的要求。因此設計一個低延遲、高可靠性的路由協議是非常重要的。用于監控應用的路由協議有以下要求：

1）高可靠性 傳感器的傳輸范圍有限，采樣數據需要通過多跳傳輸轉發到目的地。如果傳感器之間的鏈路質量差導致數據頻繁丟失，則無法滿足業務需求。

2）低延遲 從傳感器采樣的數據要快速傳遞到目的地，否則不可能對緊急情況給予反應。如在健康監測系統中，數據延遲對患有嚴重疾病的患者來說是致命的。因此，需要構建最短路徑或通過負載均衡減少排隊延遲，將數據及時轉發到目的地。

3）能源效率 監測應用場景的傳感器通常安裝在電池更換困難的地方。如果某個特定節點的能量很快耗盡，就會導致網絡壽命縮短。因此減少網絡能量消耗是非常必要的。

傳統的Ad-hoc 路由協議[1]能夠保證可靠傳輸，滿足WSN 源節點的業務需求，涉及到傳感器維護路由路徑的高計算能源開銷。為了降低控制開銷帶來的能量消耗，基于樹的路由是一種可行的解決方案。父節點選擇是基于樹的路由協議的一個關鍵角色，因為父節點和子節點之間的鏈路被用作路由路徑。傳統的樹路由[2]使用到接收器的跳數作為父節點選擇的決策標準。每個源節點都可以通過選擇跳數最少的節點作為父節點來構建到接收器的最短路徑。這種方法可以提供低延遲，但是在選擇父節點的過程中沒有考慮父節點和子節點之間的鏈路質量，因此不能保證可靠的傳輸。

路由協議在WSN 中起著重要的作用，可以保證可靠傳輸，滿足單個節點的服務質量（quality of service,QoS）要求。網絡節點的電池在野外是難以替代的，因此，路由協議應該以較低的能量開銷創建路由路徑。在響應式路由協議中，源節點在需要到目的節點的路由路徑時發送路由請求消息。為了保證路由路徑的可靠性，節點會定期廣播控制消息，并向相鄰節點檢測鏈路狀態。在移動自組織網絡等節點頻繁移動的網絡中，響應式路由可以保證可靠的傳輸，但是為了維護路由路徑，能量消耗顯著增加。

為了減少控制消息的數量，主動路由協議（如優化的鏈路狀態路由協議）會選擇相鄰節點間連通性高的節點作為父節點。為了維護拓撲信息，父節點必須定期廣播控制消息。這種驅動路由可以減少控制消息的數量，因為只有父節點廣播拓撲信息。但是，當需要傳輸大量節點信息時，廣播開銷和內存占用會增加。此外，在節點頻繁移動的網絡中，由于拓撲信息必須頻繁廣播，控制開銷顯著增加。為了降低廣播開銷帶來的能量消耗，基于樹的路由是小型WSN 的最佳解決方案。樹型路由協議由一個根節點和多個傳感器節點組成，節點之間具有父子關系，通過樹型結構相互連接。每個節點選擇最優的父節點并將數據轉發給父節點，直到數據到達根節點?；跇涞穆酚煽梢韵窂剿阉鞑⒈苊獯罅繌V播消息。父節點和子節點之間的通信鏈路作為路由路徑，根據樹的路由協議選擇父節點[3]。

1 相關工作

為了構建穩定的樹結構拓撲，文獻[4-5] 采用鏈路質量作為決策標準。但是，在選擇父節點時沒有考慮負載均衡，因此，在特定的節點上可能會放置過多的負載，導致嚴重的丟包。為了防止擁塞，文獻[6-7] 提出了一種負載敏感的父節點選擇算法，但沒考慮鏈路質量和能源效率。這些基于樹的路由協議獨立地解決不同的父節點選擇問題。然而，無法同時解決傳輸可靠性、端到端延遲和能耗等多個性能指標。

為此，文獻[8-9] 嘗試在考慮多個認知指標的情況下選擇最佳父節點。為了共同實現多個目標，采用了線性加權的方法[10]，其中每個節點通過多個指標計算加權[11]。然而，線性加權方法采用了主觀權重，使性能指標之間缺乏靈活的權衡。為了克服這一局限性，提出了一種基于多標準決策（multi-criteria decision making,MCDM）的選擇方案，該方案通過層次分析法（analytical hierarchy process,AHP）[12]確定多個決策準則（相對重要性）來尋找最佳父節點，然后通過簡單加權法（simple additive weighting,SAW）[13]得到加權值。然而，決策者需要根據其偏好或目標網絡的背景知識來計算每個指標的權重。此外，由于無線傳感器網絡的規模越來越大，部署也越來越復雜，因此在大規模無線傳感器網絡中尋找最優父節點具有挑戰性。

為了消除決策者的偏見，并在復雜的部署場景中給出適應性決策，進而實現多個目標，如高可靠性、低延遲和能源效率，本文通過強化學習獲得的關于目標網絡的經驗數據以找到最好的父節點。具體來說，使用多個認知指標定義一個狀態空間、動作集和激勵函數，通過試錯找到最佳父節點。

2 系統模型和問題陳述

2.1 網絡模型

網絡模型如圖1 所示，包括N個傳感器節點和M個匯聚節點，其中Sink node 是匯聚節點，Sensor node 是傳感器節點，Obstacle 是障礙物。這些節點構成了樹狀拓撲結構，其中匯聚節點位于樹的頂層。樹狀結構通過樹狀路由協議自主配置。匯聚節點作為控制器，將從傳感器節點采樣的數據進行聚合，形成樹狀結構。假設傳感器節點和匯聚節點都有固定的位置，節點間的鏈路質量取決于地理位置。然后，每個傳感器節點在其鄰居節點中選擇一個父節點，并將數據傳遞給父節點，直到到達匯聚節點。

圖1 匯聚節點和傳感器節點的部署Figure 1 Deployment of sink nodes and sensor nodes

為了根據網絡條件的變化選擇最優的父節點，每個節點需要使用多個認知指標來識別當前的網絡狀態。主要目標是實現高可靠性、低延遲和能源效率[14]。但是，選擇最佳父節點需要考慮很多因素，例如，多個傳感器節點選擇同一個父節點，在父節點上建立隊列，導致排隊延遲增加或數據包丟失。此外，父節點和子節點之間的鏈接質量取決于它們的地理位置，因此，障礙會使傳輸變得不可靠。

為了減少每次傳輸的延遲，每個節點都應該構建一條到目的地的最短路徑。在樹狀路由中，到匯聚節點的跳數是選擇父節點的決定性指標，即每個節點都可以通過將匯聚節點的跳數作為決策變量來保持較低的延遲。在這項工作中，采用跳數H作為決策變量，形成分層樹狀結構，減少端到端延遲[15]。

父節點和子節點之間的鏈接質量高度依賴于距離和障礙物。在鏈路質量較差的情況下，如果節點選擇到匯聚節點的跳數最短節點作為父節點，則可能會造成因丟包和重傳導致的額外能耗增加。用子節點和候選父節點之間接收到的信號強度P描述信號質量，每個節點在接收到鄰近節點的Hello 消息時，可以很容易獲得信號強度。

使用加權移動平均（weighted moving average,WMA）來防止測量值的突然變化，近期測量數據的權重較高，過去測量數據的權重較低，因此，將每個測量值乘以一個權重。設發送一個Hello 消息用時為t，則節點i與鄰居節點在n個周期的信號強度WMA 值公式為

式中：Pi(i=1,2,···,n) 為節點i的信號強度WMA 值；時間因子t-n表示當前所處的時間點；權重系數wi決定了每一個歷史數據在計算中所占的比重。

如果多個節點選擇同一個鄰居作為父節點，則該父節點將會負載過重。換句話說，當父節點接收到超過其處理能力的數據時，可能會發生緩沖區溢出。為了防止擁塞，采用緩沖區占用率作為選擇父節點的決策變量。為防止測量數據的突然變化，定義相鄰節點i的緩沖區占用率的n周期WMA，用來描述相鄰節點i的緩沖區占用率Bi在時間序列中的演化過程，公式為

式中：Bi為第t個時間點上的WMA 值；指數項表示前n個時間點上的值與權重之間的線性組合；Bt為t時刻緩沖區占用率，公式為

式中：Bcur為t時刻的當前緩沖區；Bmax為最大緩沖區。

一般情況下，野外部署的傳感器電池很難更換。如果某個特定節點的能量很快耗盡，就會導致網絡壽命的縮短。為了提高整個網絡的壽命，采用功耗比作為決策變量來選擇父節點。功耗比E的公式為

式中：Tcu表示由于回退或重傳引起的累積延遲；a為回退或幀重傳的數量。L為有效載荷長度。Eidle、ETx、ERx和Esleep為每種收發模式的能耗，Etotal為總能耗。

在根據網絡條件的變化找最優父節點的時候需要考慮多種因素，以在相互沖突的目標（即高可靠性、低延遲和能源效率）之間找到合理的平衡。在文獻[16] 所提到的方法中，每個節點計算出每個鄰居多個標準的加權和，然后選擇具有最高加權值的節點，它合理地權衡了性能指標之間的關系。然而，決策者必須根據自己的偏好或對網絡的背景知識來計算權重因子。相比之下，在這項工作中，強化學習（reinforcement learning,RL）模型使每個節點都能利用網絡的經驗數據，從而根據網絡狀態自適應地選擇父節點。

3 樹路由協議

本文提出的樹路由協議由幾個組件組成，協議框架如圖2 所示。每個組件與其他組件交互以構建樹狀拓撲，并通過父節點選擇找到最優路由路徑。本節首先描述路由協議的基本操作，然后指定基于RL 模型的父節點選擇算法。

圖2 協議架構Figure 2 Protocol architecture

圖2 中Event scheduler 是事件調度程序，RL-based parent selection 是指基于強化學習的父代選擇，Loop detection 是循環檢測，Control packet queue 是控制分組隊列，Neighbor management 是鄰居管理，Neighbor Table 是鄰居表格。

3.1 樹結構

匯聚節點定期廣播消息，包括到匯聚節點的跳數、根節點、父節點選擇和數據傳輸路徑。當節點接收到構建消息時，將跳數存儲在鄰居表中，并將構建消息中的跳數加1，然后節點重新廣播構建消息。由于節點選擇跳數相同或更少的相鄰節點作為父節點，因此節點的層次級別根據到匯聚節點的跳數自主確定。此外，每個節點定期廣播一個Hello 消息，其中包含了提議的決策標準（即P、B和E）。每個節點收到鄰居的Hello 消息后，將決策標準存儲在鄰居表中。這些變量用于在每個節點上選擇父節點。樹的構造細節在算法1 中給出。

3.2 父節點的選擇

3.2.1 RL 模型

在RL 模型中，狀態空間可以定義為3 個決策準則的集合，S={Pi,Bi,Ei},i∈N，即每個節點根據相鄰節點的鏈路質量Jaccept、擁塞程度r=True 和剩余能量選擇父節點。動作空間定義為鄰居表中的一組候選父節點，應該注意的是候選父節點集只包含到匯聚節點的跳數與匯聚節點本身相同或更少的相鄰節點；關于激勵函數可以定義如下：如果選擇一個節點作為父節點，該操作增加了幀重傳、包錯誤率和能量消耗，則獲得較低的激勵，否則會得到很高的激勵。

3.2.2 基于RL 的父節點選擇算法

為了找到最佳的父節點，定義了多個認知指標（包括跳數、接收信號強度、緩沖區占用率和功耗比）。主要思想是每個節點根據當前網絡狀態使用認知指標自適應地改變其父節點。顯然考慮的認知指標越多，在選擇父節點時獲得的好處就越多，但是這樣也可能會出現復雜的決策問題。為了解決這一問題，提出了基于RL 的父節點選擇算法，該算法選擇激勵最高的節點作為父節點，算法2 給出了父節點選擇的詳細過程。給定一個狀態S，每個節點根據貪心算法在相鄰節點中選擇一個父節點（第④～⑤行）。當父節點選擇完成時，節點觀察網絡環境中的激勵R和新狀態S′（第⑥～⑧行）。節點向候選父節點發送加入請求（第⑨行）。選中的父節點接收到加入請求消息后，以接受加入消息或拒絕加入消息回復相應節點（第?～?行）。每個節點都會通過反復實驗找到最優的父節點。

由于節點選擇到匯聚節點的跳數與自己相同或更少的相鄰節點作為父節點，因此節點的層次級別是根據跳數自主配置的。但是，每個節點可以選擇一個同級的鄰居節點（即到sink節點的跳數相同的節點）作為父節點，因此可以生成一個循環。為了檢查父節點和子節點之間的循環，每個節點向候選父節點及其子節點列表發送一個連接請求消息（第⑨行）。接收連接請求消息的節點根據子節點列表檢測一個循環（第?～?行）。如果沒有檢測到循環，節點將回復接受加入消息。否則，它返回一個拒絕加入的消息。

3.3 父節點更換率

由于無線傳感器網絡中的網絡狀況變化頻繁，每個節點都需要定期更新父節點。例如，如果父節點長時間不更新，則特定節點負載過大。為了實現拓撲結構的穩定，每個節點都會根據Hello 消息間隔定期更新其父節點。但是，如果節點頻繁更改父節點，可能會產生額外的開銷。

4 仿真實現

4.1 仿真設置

仿真參數如表1 所示，進行100 次模擬，置信區間為95%。具體來說，運行3 600 s 的模擬，并將網絡大小設置為5 000 m×5 000 m。為了構建大規模網絡，將傳感器節點的數量設置為100 個，sink 節點的數量設置為5。為了構建樹狀拓撲，sink 節點每隔20 s 周期性地廣播一條構建消息。每個節點收到構建消息后，更新鄰居表中sink 節點的跳數，并開始選擇父節點。此外，所有節點每隔5 s 會周期性地向鄰居發送Hello 消息。將構建消息和Hello 消息的大小分別設置為192 bits 和128 bits。為了驗證所提出的方案，根據網絡條件的變化自適應地改變父節點，從而在多個目標之間找到合理的權衡，并通過改變流量比特率和誤碼率來觀察性能指標。為了模擬擁塞，將流量比特率從1 000 bits/s 改為5 000 bits/s。此外，將誤碼率從10-2更改為10-6，以使鏈路條件為動態。

表1 仿真參數Table 1 Simulation parameters

所設計的對比算法是基于線性加權和的父節點選擇算法[17]和基于MCDM 的父節點選擇算法?；诰€性加權和的方案考慮了跳數、緩沖區占用率、鏈路質量和剩余能量作為決策指標，且每個指標的權重以相同的比例固定?；贛CDM 的父節點選擇方案，當網絡不穩定時，增加接收信號強度的權重，選擇鏈路條件好的父節點。如果候選節點的鏈路條件差異不顯著，則每個節點將另一個緩沖區占用率低、剩余能量高的節點替換為父節點[18]。

4.2 可靠性

根據鏈路情況，影響報文傳遞比的主要因素是擁塞導致的緩沖區溢出和誤碼。如圖3 所示，隨著流量比特率的增加，所有方案都會因擁塞而造成丟包。線性加權和方案在決策過程中考慮了鏈路質量。但是，由于多個指標之間的權重是相等的，即使發生緩沖區溢出，父節點也很少改變。由于基于MCDM 的方案具有較高的緩沖區占用率權重，所以其擁塞丟包比基于線性加權和的方案要小。隨著誤碼率的增加，自適應地選擇鏈路質量好的節點，從而獲得更好的報文轉發速率。

圖3 數據包傳輸率仿真結果Figure 3 Simulation results of packet delivery ratio

然而，在基于MCDM 的方案運行時不能改變指標之間的權重，因此它有一個明顯的局限性，即難以響應網絡場景的變化。而所提方案通過反復實驗來學習如何在運行時應對網絡條件的變化，因此能表現出最佳的性能。

4.3 延遲

影響樹路由端到端延遲的主要因素是到匯聚節點的跳數和排隊延遲。傳統樹路由是根據到匯聚節點的跳數來選擇父節點的，當流量比特率較低時，性能最佳。但是，隨著流量比特率的增加，到匯聚節點跳數較少的節點會發生擁塞，導致端到端時延急劇增加。為了解決這一問題，基于線性加權和的算法在決策過程中考慮了具有跳數的擁塞度量。如圖4 所示，在基于線性加權和的方案中，由于指標之間的權值相同，隨著流量比特率的增加，負載分配并不有效，從而會增加排隊延遲。此外，當誤碼率增加時，可以選擇鏈路質量較好的節點作為父節點，而不是跳數較低的節點，端到端延遲略有增加。

圖4 端到端時延仿真結果Figure 4 Simulation results of end-to-end delay

在MCDM 的方案中，決策者預先確定了每個網絡環境指標的權重，因此在預配置的網絡場景中表現良好，但該方案不能應對運行時發生的網絡條件變化。相比之下，每個節點根據網絡環境通過Q-learning 學習優化，能夠自適應地應對網絡條件的變化，具有較好的性能。

4.4 能源效率

增強樹路由能耗的主要原因是擁塞和鏈路斷裂造成的丟包重傳。在樹形路由中，除了能量效率外，還需要平衡傳感器節點之間的能量消耗，以保證路由路徑的多樣性。

傳統的樹路由是根據當前節點到匯聚節點的跳數選擇父節點。流量擁塞會導致大量丟包，數據重傳又導致能量消耗的增加，而且當鏈路質量較差時，重傳次數也會增加。為了解決這一問題，基于線性加權和的方案在決策過程中同時考慮了鏈路質量和緩沖區占用率，但由于多個指標之間的權重沒有適當調整，也難以響應網絡條件的變化。結果如圖5 所示，單位時間能耗最高，死節點數也最多。

圖5 功耗比仿真結果Figure 5 Simulation results of power consumption ratio

因為決策者提前知道網絡環境，并據此確定合適的權重，因此基于MCDM 的方案比基于線性加權和的方案性能更好。然而在運行時不能調整度量的權重。相比之下，本文方案通過各種認知指標來識別網絡環境，并通過反復實驗找到優化性能指標的最佳策略。結果表明，該方案比基于MCDM 的父節點選擇方案具有更好的性能。

4.5 討論

由于決策者基于先驗知識預先確定了每個指標的權重，因此存在一個明顯的限制，即權重不能在運行時更改。為了解決這個問題，使用多個認知指標來識別網絡環境，并通過強化學習找到聯合優化性能指標的最優策略。此外，使用WMA 來防止認知指標的突然變化。顯然通過根據網絡條件的變化自適應地改變父節點，在沖突的性能指標之間提供靈活的權衡。

研究表明，使用強化學習方法可以顯著提高無線傳感器網絡中路由性能指標，減少能耗、降低延遲。然而，在實際應用時還需考慮諸多因素如拓撲結構變動、鏈路質量波動等復雜情況對算法性能帶來影響。

5 結語

為了在樹路由中實現多個目標，重新考慮在復雜部署場景中尋找最優父節點。通過強化學習利用目標網絡的經驗數據找到最佳父節點。分析了3 種類型的認知指標來應對各種網絡場景；提出了將RL 應用于樹路由的系統模型，并給出了樹構造、環路檢測和父節點更新的具體算法；定義狀態空間、動作集和激勵函數，通過強化學習找到最佳父節點。通過綜合仿真，證明了本文提出的父節點選擇方案可以在端到端延遲、分組傳輸比和能量消耗等性能指標之間取得平衡。