面向物聯網的自適應可靠路由機制研究

郎 登 何

(重慶電子工程職業學院人工智能與大數據學院 重慶 401331)

Bidirectional processing

0 引 言

物聯網(Internet of Things,IoT)是一種新興的信息通信技術范式，支持分布式計算和集中式計算兩種計算方式[1]。同時，IoT也是一種無邊界智能網絡，其中海量傳感器、執行器和各種通信設備相互連接，并且可以采用復雜協同方式執行各種應用任務。隨著IoT的不斷發展，其網絡架構呈現一種復雜分布式異構網絡特征[2]。同時，IoT已經得到研究者和研究機構的密切關注，如智能家居、智能電網、智能交通和智能健康等領域[3]。

近年來，IoT路由方面的研究內容主要集中在服務路由選擇、路由節點能耗和安全路由機制等方面?？紤]網絡中新相遇節點分組機制導致路由選擇精度低的問題，文獻[4]提出了一種物聯網高效服務模型，該方法通過分組交換增量計算出傳輸概率，同時采用Epidemic機制產生節點約束概率，從而組建相遇節點的數據分組機制。對于IoT感知節點路由選擇來說，能量受限是制約IoT節點傳輸效率的一個瓶頸之一，因此，陶亞男等[5]提出一種基于改進貓群算法的路由優化策略。該方法引入備份思想，在綜合考慮節點剩余能量方差、節點負載和節點距離等條件下，保證數據傳輸實時性。與此同時，開放IoT環境下，IoT的路由機制容易受到惡意丟包攻擊，張光華等[6]基于RPL協議提出一種具有信任機制的安全路由方法，該方法解決了網絡中非法入侵因素導致的惡意節點誤判斷問題。但是，這些IoT路由方面研究均以無線傳感器網絡為數據傳輸背景，其網絡的節點和路由節點通常采用電池供電方式，具有能量受限和資源受限等特點。當前IoT發展階段，無線傳感器網絡已經不是IoT組網的主要組網方式，在部分智能家居和智能健康領域，傳感器主要通過手機或者智能網關將數據傳輸到云端或者其他計算單元中[2]，而這些智能網關多是固定電源供電。在這些條件下，網關設備不存在感知節點路由選擇[4]、節點能量受限[5]和節點的路由安全問題[6]。因此，IoT智能網關路由策略性能成為制約新形勢下IoT數據轉發效率的一大瓶頸。

IoT智能網關路由策略通常采用自適應負載均衡技術[7]和多維通信技術[8]，以解決異構IoT網絡數據傳輸問題，同時保證海量高采樣率IoT傳感器設備流數據的高效轉發和低延遲特性。文獻[7]提出了一種面向IoT的自適應負載均衡路由技術，解決了并行機會路由場景中數據從源網關到互聯網的延遲問題。而對于異構IoT來說，文獻[8]提出一種三維異構IoT路由決策，降低了異構IoT的能耗和端到端延遲。此外，為了解決節點動態流量變化對網關造成的路由性能不佳問題，王玉玨等[9]提出一種最大化網關流量的IoT路由策略。雖然以上文獻已經對路由傳輸延遲、能耗和流量控制等方面問題進行了研究，但是這些IoT網關路由策略只具備單項處理能力，無法根據數據特性實現雙向路由處理，這對于IoT應用來說至關重要，許多場景需要雙向數據傳輸，也就是一方面需要傳輸數據到云端，另外一方面IoT節點需要等待云端反饋控制信息。因此，急須開發一種自適應的雙向處理路由策略。

因此，本文提出一種自適應雙向處理路由策略，用于雙向處理條件下的IoT物聯網路由網關。該策略將路由信息轉發表的更新操作交由節點本身處理，且只存儲對于節點處理消息有用的信息數據。這些有用信息通常包括消息源節點和目的節點、輸入和輸出鏈路、當前消息切換值(Handover Number,HN)及路由表[8，10]。除此之外，對收集到的消息進行觀察和分析，同時結合反向學習和強化學習模式來估計數據包到達目的節點所需要的時間。

1 相關工作

物聯網作為一種新型的網絡范式，涉及范圍涵蓋端、邊和云，包括終端傳感設備對數據的產生和監測、邊緣交換轉發設備對數據的轉發、云端控制器對數據的處理過程。智能網關路由策略是端、邊和云數據交互的重要傳輸機制。

文獻[7]表示，使用傳統的路由技術將數以百萬計的物聯網設備連接到互聯網，會導致網關擁擠和過載，導致物聯網網絡吞吐量下降。為了提高吞吐量，提出了將多種無線技術用于并行數據傳輸，即并行機會主義路由(Parallel opportunistic Routing,PoR)。然而，在PoR中，從源網關到Internet的數據始終遵循相同的路徑。這會導致某些網關出現擁塞，進而影響吞吐量。因此，文獻[10]提出了一種自適應和負載均衡路由技術，稱為自適應路由技術，利用多技術和負載均衡器，通過在整個網絡上分配負載來最大化物聯網網絡的吞吐量。

文獻[8]針對路由機制存在數據傳輸效率低、能耗高、物聯網端到端延遲差等問題，建立了三維和通信模型的基礎，并提出了基于蜂窩地址(Cellular Address,CA)的三維異構物聯網路由決策機制。首先，CA建立了基于元胞自動機和節點平均接收信號強度的網絡節點數據轉發準則；其次，CA通過IPv6地址實現路由優化和控制；最后，通過蜂窩地址解決路由決策機制。仿真結果表明CA的包傳送率在82%到95%之間，路由消耗率在20%到35%之間，平均端到端延遲為20毫秒，不僅保證了物聯網通信性能指標，而且提高了網絡的可靠性。

文獻[10]為了更好地利用物聯網基礎設施，考慮在物聯網網絡中動態發現和組合物聯網相關的功能，以執行新的或動態出現的任務。為了實現這一目標，開發了一個基于語義的物聯網服務發現路由協議。在路由協議中，為了減少路由所需的空間，每個節點都維護一個帶有“伸縮視圖”的路由表，即關于直接鄰居能力的更精確的信息，以及對更遠的鄰居能力的摘要。定義了一個能力本體，設計了一個基于本體的能力匯總算法，實現了伸縮視圖的概念。同時還設計了一個本體編碼方案，以進一步減少路由的內存需求，同時實現功能總結。解決方案能夠減小路由表的大小，適用于內存有限的物聯網設備。此外，實驗結果表明，與現有的基于語義的路由算法相比，文獻[8]方法可以顯著降低網絡流量和IoT功能查找的延遲。

文獻[11]發現在物聯網網絡中，需要一個領導者節點，例如找到能量最小的節點或位于網絡的最左側。對于這類應用程序，算法必須具有魯棒性和容錯性，因為如果節點發生故障，很難甚至不可能進行干預。如果這個節點是領導者，這種情況可能是災難性的。于是提出了一種基于樹路由協議的新算法。它從根節點開始，通過洪泛的過程，以確定一棵生成樹。在此過程中進行路由操作。如果兩個生成樹相遇，那么路由效果最佳的樹將繼續其進程，而其他樹將停止。從而得出路由主宰樹，它的根則作為領導者。該算法可以在任何節點可能發生故障和網絡斷開的情況下工作，能耗降低率可達85%以上。

盡管存在大量的IoT路由研究工作，但這些工作只具備單向處理能力，無法針對網絡的變化進行有效反饋和靈活應對，特別是傳感器流數據的雙向自適應處理，因此也無法適應物聯網中大量設備和數據的動態變化。

2 自適應可靠路由機制

本文提出的機制主要包括三部分：首先通過反向學習建立初始化的路由自適應模型；其次通過強化學習對初始化模型進行修正，使其支持可靠性；最后結合這兩種學習模式實現分布式路由的自適應與可靠性傳輸。

2.1 反向學習初始化

給定任意一條鏈路LI，經過它的數據包所攜帶的HN數值能夠被用于估計從源節點S到當前節點X所需的最短時間。于是，反向學習機制利用這個情況，同樣也可以利用數據包所攜帶的HN數值來估計從當前節點X到源S的最短時間。

以LI作為輸出鏈路，最短時間可以表示為T(S,LI)。隨著網絡時間的推移，節點X對于到達S的最短時間的預估已經不再準確，使用T(S,LI)old表示，那么基于反向學習技術，更新的過程可以表示如下：

T(S,LI)new=T(S,LI)old+k[HN-T(S,LI)old]

(1)

可以看出，影響數據包到達目的節點的最短時間的因素為參數k。通常，0≤k≤1。考慮到實際情況，需要對式(1)進行修正。于是引入兩種類型的k參數k1和k2，其中：k1表示模型的“學習因子”，用于降低T(S,LI)；k2則表示“遺忘因子”，用于提高T(S,LI)。在這里其實存在著更為復雜的統計預估方法，但這些方法通常需要每個路由表條目上的額外信息，從而對系統造成額外的開銷。

然而，由反向學習所建立的模型通常需要使用間接信息，但是這種間接信息通常是不足的，這種情況往往可能會導致出現“乒乓效應”。以節點A和B為例，數據包目的節點為C，存在這樣一種情況，A以為B距離C最近，而B同樣以為A距離C最近，最終，數據包會在A和B之間來回傳遞，直到達到最大的切換次數Δtmax，從而終止。接下來對這種模型進行進一步的修正。

2.2 負增強學習修正

“乒乓效應”是反向學習技術的主要缺陷之一，它可以通過觀察數據包處理過程中所采用的信息結構來進行判斷。通常，當LI=LO成立的時候，就會發生這種“乒乓效應”。這種判斷條件可以通過周期性的節點輸入輸出鏈路監測來保證。在此基礎上，再采用負增強學習技術來對其進行修正和增強。

具體而言，負增強學習通過設置相應的懲罰機制來對反向學習進行修正。當任意節點X上存在LI=LO的情況時，進行以下修正操作：

T(D,LO)new=T(D,LO)old+2ΔTL

(2)

其中：T(D,LO)new和T(D,LO)old分別表示反向從目的到源所需的最短時間。那么根據式(2)對節點X上的路由信息表條目中的屬性進行修改。將信息塊中的特殊信號位(通常為0)設置為utility，并將信息返回給LO。如果LO上存在一個為utility的信號位，那么首先將其重置為0，然后對路由表進行如下修改：

T(D,X)new=T(D,X)old+2ΔTL

(3)

式中，ΔTL表示數據包通過當前鏈路所需要的時間長度。盡管對路由模型進行了修正，負增強學習在非對稱懲罰的情況下的路由效率較低。

2.3 雙向自適應機制

鑒于反向學習初始化模型和負增強學習修正技術彼此之間的優缺點，本文將二者進行融合，在保留它們有效特性的同時，抵消它們的缺陷。

根據式(1)的定義，顯然在將“遺忘因子”k2設置為0的情況下，可以得出比較好的效果，原因在于k2的值和路由表條目數量成正比。這種融合情況下的技術，本文將其稱之為雙向自適應機制。一方面，通過使用減少路由表條目的反向學習方法來糾正負增強技術所導致的過度補償，從而支持對新鏈路或者修復鏈路的自動化適應過程；另一方面，通過使用負增強技術增加路由表條目，從而提供對受損鏈路或者節點的直接適應規則，最后消除反向學習的錯誤信息問題。具體而言，如果來自于源節點S的消息數據包沿著鏈路LI到達節點X所花費的時間比從節點X到達S的預估時間T(S,LI)要小，那么，需要按照以下規則更新T(S,LI)：

T(S,LI)new=min[HN,T(S,LI)old]

(4)

另外，如果路由算法為任意數據包所選擇的輸出鏈路LO和輸入鏈路LI相同，則調用負增強規則，如式(2)和式(3)所示。雙向自適應機制的實現同樣還需要在每個消息塊中設置一個額外的標志位。一旦發生“乒乓效應”，該標志位就會被設置為unity。此時，假設節點Y需要處理一個目的節點為D的數據包，使得LI=LO=X，那么，T(D,X)遞增2個單位。在將標志位設為unity后，還需要將反饋消息發送回節點X。至此，重新檢測標志位狀態并將其重置為0，那么T(D,Y)同樣遞增2個單位。

2.4 時間復雜度分析

3 仿真實驗與分析

3.1 實驗參數設置

仿真實驗拓撲基于NREN網絡(如圖1所示)，具有1 157個節點和2 930條邊，符合物聯網規模的特性。1 157個節點分為兩種類型，其中300個節點作為目的節點，857個節點作為源節點。源節點作為IoT數據傳感輸入端，接收傳感器采集的數據流，目的節點作為數據流的終點，并每接收1分鐘數據，向源節點反饋數值信息平均值。

圖1 NREN拓撲

為了使測試更接近實際的IoT路由環境，使用公開數據集MIMIC-III Waveform Database中的傳感器數據作為本文的IoT流數據源。該數據庫包括22 317條波形記錄和22 247數值記錄，其中波形記錄包含一條或者多條心電信號、連續動脈壓信號、呼吸信號和光電容積脈搏波信號等；數值記錄包含心率、呼吸率、血氧和動脈平均壓等數值數據。其中，每個節點配置為單核處理器，隊列初始化為空，數據流的到達服從泊松分布。不同節點的處理速率不同，均服從均勻分布。

對于所有的實驗情況，將“學習因子”k1設置為0.75，而“遺忘因子”k2則設置為0.25，從而模擬實際情況下的網絡和模型的學習情況。

3.2 評價指標與對比機制

為了對本文提出算法進行評估，本文實現了三種先進的IoT路由策略進行對比分析，這三種先進的IoT路由策略分別為基于語義的IoT路由協議(算法1)[10]、最佳擬合路由策略(算法2)[12]和最大化網關流量的路由策略(算法3)[9]。此外，采用路由表條目數量和信息交付率等兩個評價指標作為本文對比方法的評價指標，并在討論非故障鏈路條件下和故障鏈路條件下的信息交付率。

3.3 實驗結果與分析

3.3.1路由表條目數量對比

路由表條目數量是衡量路由算法效率的重要依據之一[10]。首先，在同等實驗條件下，本文實現了四種不同方法(包括本文提出的方法和三種對比方法)。圖2所示為四種方法的平均路由表條目數量對比。其中，本文假設在沒有流量的時候路由表條目為空，即對于流量數為0時，對應的平均路由表條目數也為0。通過觀察路由表條目數量的變化，可以得出一種路由算法是否能夠適應當前網絡狀態的變化。圖2表明四種算法在網絡流量增加的條件下，對應的路由表條目也隨著增加。其原因在于流量與負載是呈現正相關趨勢，流量增加路由條目也會隨之增加，以適應更多的流量種類。

圖2 路由表條目數量

如圖2所示，相比其他三種算法來說，本文算法所需的路由條目數量最少，而算法3的路由表條目最多。一方面，這是由于本文采用了雙向自適應機制，可以根據網絡狀態來動態獲取當前網絡中最佳的路由表條目數量；另一方面，本文采用了雙向適應和負強化學習策略動態修正最短時間估計，從而保證了本文方法對各種網絡場景的適應能力。與此同時，算法1為了保證低延遲特性，犧牲了部分路由表效率性能，增加了除了直系鄰居以外的所有路由表條目數量[10]。而算法2是基于最優擬合遍歷的路由策略[12]，需要提高路由表條目數量來保證路由精度。對于算法3而言，它采用大流量節點構建路由表，但是本文的泊松分布輸入條件下，某些一類節點會有較大流量出現，從而導致這些節點路由表數目龐大[9]。綜上，在相同網絡規模和實驗條件下，本文方法具有最低的路由表數量，說明本文提出的路由策略對網絡的自適應能力更佳。

3.3.2無鏈路故障條件下信息交付率對比

為了驗證本文算法的可靠性，本文采用信息交付率作為驗證路由性能的指標，它也是路由信息交付準確率的一種重要指標[10]。本文中用小數表示，范圍為(0,1]。在無鏈路故障條件下，測試了四種算法的信息交付能力。

如圖3所示，本文算法在流量負載增加的情況下，信息交付率可以保持穩定，并未出現斷崖式降低或者持續下降的問題。在流量負載從250增加到2 000的情況下，本文算法仍然能保持穩定的信息交付率，平均信息交付率約為0.91。對于其他三種算法而言，在小流量負載情況下(250到500)，算法1與本文算法信息交付率相差不多(平均信息交付率分別為0.96和0.94)，而算法2和算法3信息交付率相對較低(平均信息交付率分別為0.91和0.88)，特別是在負載為500的條件下。對于大于750的流量負載條件來說，雖然所有算法的信息交付率均逐漸降低，但是本文算法均保持在0.86以上，平均信息交付率為0.90，而算法1、算法2和算法3的平均信息交付率僅為0.79，0.74和0.62。以上情況的主要原因在于本文算法信息交付率可以通過負強化學習不斷修正相關參數，從而達到自適應的策略，保持信息交付率的穩定性和可靠性。同時，其他三種算法無反饋機制參與路由決策，無法根據網絡負載情況動態調整路由策略。相比較而言，算法1可以在小流量范圍內提供高信息交付能力，但是對于大流量負載來說，無法提供可靠的路由傳輸，這是因為該方法以直接鄰域為優先策略，較遠節點出現大流量負載無法及時動態調整。綜上所述，本文算法可以保持可靠的信息交付能力，提供高信息交付率的路由策略。

圖3 信息交付率

3.3.3鏈路故障條件下信息交付率對比

為了進一步驗證本文算法的可靠性，本文采用隨機破壞網絡的方式對算法進行進一步驗證。雖然本文的實驗環境有2 930條鏈路，但是超過一半以上故障屬于網絡癱瘓情況，所以隨機生成故障鏈路范圍被設置為1到1 000。為了與無故障鏈路條件實驗次數統一，所以隨機生成8個故障鏈路數目，用于檢驗算法對突發事件和故障事件的魯棒性。

圖4所示為鏈路故障條件下四種算法的信息交付率比較，故障鏈路數量從左到右分別為142、420、484、786、798、910、951和970?？傮w上講，隨著故障鏈路數量的增加，所有算法的信息交付率呈遞減趨勢。但是，本文算法的平均信息交付率為0.81，而其他三種算法的信息交付率僅為0.54、0.51和0.41。特別是當故障鏈路數量超過484以后，其他三種算法出現了斷崖式的突然下降。這是因為算法1受到隨機破壞影響，直系鄰域節點范圍減少，一些節點的路由交付效率降低；算法2則無法獲得全局最優解[14]，導致性能下降；而對于算法3來說，無法適應隨機故障，局部路由流量過大，導致信息沖突增加，信息交付率降低。進一步，對于本文算法，由于采用了反向學習機制，算法可以根據當前網絡環境做出預判，并負增強學習進行修正，從而達到對路由表中最短時間的自適應更新，保證了信息交付的穩定性。因此，本文算法在鏈路故障條件下仍然可以保證較可靠的路由交付功能。

圖4 鏈路故障下的消息交付率

為了進一步驗證提出機制的可靠性，在相同的流量條件下，分別針對網絡鏈路無故障和有故障的情況，測試了提出機制所取得的交付能力。通過觀察表1，可以得出：(1) 提出的機制在無故障情況下取得的交付能力要高于有故障的情況，符合實際情況；(2) 提出的機制在有故障和無故障兩種情況下的交付能力都較高；(3) 提出的機制在網絡有故障和無故障兩種情況下，所取得的交付能力差別不大，大概在0.9%～6.83%之間。

表1 提出機制在有故障和無故障情況下的交付率

綜合第2和第3種現象，可以看出提出的機制能夠有效地應對網絡無故障和有故障的情況，也能夠保證在網絡發生故障時，網絡性能下降不大。因此，這在一定限度上反映了提出算法具有較高的可靠性。

4 結 語

本文針對物聯網環境下的路由問題，提出了一種動態的、可反饋和修正的自適應路由算法。該方法通過負增強學習方法建立路由的修正模型，并提供反饋信息；采用雙向自適應機制，實現路由表的自適應估計。實驗結果表明，提出的算法有較好的網絡適應特性，能夠在不同的網絡狀態下保證相應的路由性能。未來的研究工作包括對進一步思考邊緣計算在物聯網中所起到的作用。