一種改進的群組機器人網絡路由算法

關鍵詞：群組機器人；按需距離矢量路由協議；跨層；分簇；能量

中圖分類號：ＴＰ３９３ 文獻標志碼：Ａ 開放科學（資源服務）標識碼（ＯＳＩＤ）：

文章編號：１００３－３１０６（２０２４）１１－２６３３－０７

０引言

在地震受災區域，由于災害情況未知，道路交通也受損嚴重，救援工作面臨著巨大挑戰［１］，群組機器人憑借其可移動性和適應性強等特點［２］，具備協助或替代救援人員完成重復、高危任務的能力，不僅有助于保障救援人員的生命安全，同時還提高了任務執行的效率［３］。

在災害發生后，預先部署的通信基礎設施可能遭到部分或完全破壞［４］，這可能導致群組機器人系統無法通過基站正常通信［５］。此時就需要構建臨時性的基于移動自組織網絡（Ｍｏｂｉｌｅ Ａｄ ＨｏｃＮｅｔｗｏｒｋ，ＭＡＮＥＴ）的群組機器人通信網絡［６］，其具有高度魯棒性和抗毀能力［７］。幾乎每個ＭＡＮＥＴ 路由協議都依賴于廣播方案通過網絡分發路由信息，自組織按需距離矢量（Ａｄ ｈｏｃ Ｏｎ-Ｄｅｍａｎｄ ＤｉｓｔａｎｃｅＶｅｃｔｏｒ，ＡＯＤＶ）協議路由發現的基本機制是通過從源到目的地的節點廣播技術來查找現有路徑［８］，但隨著群組機器人進入災區后的頻繁移動和節點的增多，重新廣播會導致冗余數據包數量過多，從而顯著降低網絡性能，同時由于機器人依賴電池供電，個體機器人能量有限［９］，因此，優化路由算法和機制，引入簇結構，是減少網絡耗能的重要策略之一，有助于提高網絡的能效性能。

在對平面ＡＯＤＶ 協議的改進中，郭秀云［１０］提出了一種能量優化路由算法，綜合考慮了節點能量信息以及路徑跳數，但沒有考慮節點移動性對網絡生存時間的影響，當中繼節點速度過大時，導致剛建立好的鏈路斷裂，影響網絡性能。Ｅｒ-ｒｏｕｉｄｉ 等［１１］通過在ＡＯＤＶ 路由協議的選擇標準中添加能耗率和電池電量，提高了路由的穩定性，但有些節點會出現高負載，影響網絡性能。陳書旺等［１２］針對無線自組網數據包在傳輸過程中的能量損耗和擁塞問題，以ＡＯＤＶ路由協議為基礎，提出了一種基于擁塞控制和能量狀態的路由協議，延長了網絡生存時間，但在群組機器人系統中，還需要考慮到其運動狀態，避免網絡拓撲頻繁變化。

當節點數量變多，平面ＡＯＤＶ協議的控制開銷大幅度增多，引入簇結構就顯得尤為重要，曹樂等［１３］通過引入雙簇頭選擇算法，提出一種改進的ＡＯＤＶ 路由協議，延長了車載自組織網絡整體生存時間，但簇頭選擇指標未加入能量因素，會出現簇頭節點更早退出網絡。Ｅｂａｄｉｎｅｚｈａｄ［１４］著重于車聯網的穩定性，提出了基于集群的增強型車聯網ＡＯＤＶ，選擇具有低移動性的可靠節點作為簇頭，通過采用集群方法使其成本最小化，但不適用于能量有限的群組機器人系統在應急場景下的應用。張德干等［１５］提出了一種基于邊緣計算的分簇ＡＯＤＶ 路由新算法，綜合考慮了車輛節點能量和行駛速度，提高了路由選擇的效率，降低了控制開銷，但只考慮了鏈路整體能耗，鏈路中存在低能量節點，且研究中添加的邊緣服務器靜止，具有無限能量，不適用于群組機器人在應景場景下的應用。Ｔａｍｉｚｈａｒａｓｕ 等［１６］提出一種基于節能權重的聚類算法，克服了由于簇頭工作量而存在的局限性。由于考慮因素多，計算復雜且控制開銷中需要加入多個字段。

因此，為了更好地適應群組機器人網絡，本文在ＡＯＤＶ協議的基礎上，通過綜合考慮節點能量、負載和速度３個直接或間接影響網絡運行時間的跨層要素，使用與三者相關的路由性能作為路由判據，選擇更穩定的路徑，減少鏈路斷裂次數，引入簇結構，減少簇內普通節點的路由廣播洪泛次數。減少控制數據包數量，延長網絡生存時間，提高可靠性，為應急救援提供保障。

１度量指標的計算

２路由算法實現

改進的跨層多度量路徑選擇分簇路由協議首先限制能量過小、速度過大的節點轉發數據包；其次，綜合考慮節點能量、負載和速度３ 個能夠直接或間接影響網絡生存時間的跨層要素，使用與３個要素相關的路由性能選擇更穩定的路徑，使所選路徑上的節點消耗能量更低、速度更小、負載更小；最后，引入簇結構，節點間通過ＨＥＬＬＯ 數據包動態修改自身節點類型，通過判斷節點類型，使數據包主要在簇頭和網關組成的骨干網絡中傳輸，減少簇內普通節點的廣播洪泛。

２．１數據包格式的改進

在ＡＯＤＶ 協議的路由請求（Ｒｏｕｔｅ Ｒｅｑｕｅｓｔ，ＲＲＥＱ）、路由應答（Ｒｏｕｔｉｎｇ Ｒｅｐｌｙ，ＲＲＥＰ）數據包和路由表基礎上加入路由性能ＲＶ、節點類型，在ＨＥＬＬＯ 數據包和鄰居路由表的基礎上加入節點類型和節點穩定度，使它們適用于基于能量與速度的分簇ＡＯＤＶ 協議（Ｃｌｕｓｔｅｒｅｄ ＡＯＤＶ Ｐｒｏｔｏｃｏｌ Ｂａｓｅｄ ｏｎＥｎｅｒｇｙ ａｎｄ Ｓｐｅｅｄ，ＥＳＣ-ＡＯＤＶ）路由算法。

２．２節點類型轉換

機器人節點類型轉換示意如圖１ 所示。

在網絡初始階段，網絡中的所有節點類型都是未分配，節點通過比較自身節點穩定度ψｉ 與ＣＨ 來決定是否可以成為簇頭，若節點穩定度ψｉ 大于ＣＨ，則稱為簇頭，并廣播自己成為簇頭的消息，相鄰節點接收到消息之后改變自身節點類型，接收到１個簇頭的消息，則將自身節點類型修改為簇內節點，并將其加入到該簇頭所在的簇；若接收到２個或２個以上不同簇頭的消息，需將節點類型修改為網關；若１ 個都沒有接收到，那就將自己的節點類型修改為簇頭，避免孤島的存在。由于節點移動性、能量等因素的影響，網關若只與１ 個簇頭保持聯系，則節點類型變為簇內成員；若與所有的簇頭失去聯系，則將類型轉變為未分配，向鄰居節點發送信息，變更自己類型。簇內成員與所處簇的簇頭失去聯系，將節點類型變為未分配狀態，簇頭若失去簇內所有節點，則將節點類型變更為未分配狀態。

２．３控制消息處理流程

ＥＳＣ-ＡＯＤＶ 路由算法中對ＲＲＥＱ 數據包的具體處理流程如圖２所示。

① 接收到ＲＲＥＱ 數據包后，判斷其是否來自源節點、簇頭或網關，若是則轉到②，若不是則轉到⑦；

② 若ＲＲＥＱ 數據包由節點自己產生，則轉到⑦，否則轉到③；

③ 若當前節點能量大于０．２倍的初始能量且節點速度小于０．９倍的最大速度，則轉到④，否則轉到⑦；

④ 若中間節點接收過此ＲＲＥＱ數據包，則轉到⑦，否則轉到⑤；

⑤ 將收到的數據存入緩存區，判斷ＲＲＥＱ數據包中的ＲＶ是否小于路由表中的ＲＶ，若小于，則更新路由表，否則轉到⑥；

⑥ 若當前節點是目的節點或者有到目的節點的路由，則產生并發送ＲＲＥＰ數據包，否則更新ＲＶ，并繼續廣播ＲＲＥＱ 數據包；

⑦ 丟棄該ＲＲＥＱ數據包。

ＥＳＣ-ＡＯＤＶ 路由算法中對ＲＲＥＰ數據包的具體處理過程如圖３所示。

① 節點接收到ＲＲＥＰ 數據包，判斷該ＲＲＥＰ 數據包是否來自于簇頭或網關，若是則轉到③，若不是則轉到②；

②若當前節點是簇頭，則轉到③，否則轉到⑤；

③若ＲＲＥＰ 數據包中的ＲＶ 小于路由表中的ＲＶ，則更新路由表，否則轉到④；

④判斷當前節點是否是目的節點且ＲＲＥＰ 數據包中的ＲＶ 大于等于路由表中的ＲＶ，若滿足條件，則轉到⑤，否則更新ＲＶ，繼續轉發ＲＲＥＰ 數據包。

⑤ 丟棄該ＲＲＥＰ 數據包。

３仿真與分析

在Ｌｉｎｕｘ ＋ ＮＳ２． ３５［２０］仿真環境下，對ＡＯＤＶ、基于能量、負載和速度的ＡＯＤＶ 路由協議（ＡＯＤＶ ＲｏｕｔｉｎｇＰｒｏｔｏｃｏｌ Ｂａｓｅｄ ｏｎ Ｅｎｅｒｇｙ，Ｌｏａｄ ａｎｄ Ｓｐｅｅｄ，ＥＬＳ-ＡＯＤＶ）（加入簇結構前使用跨層多度量路徑選擇方法改進的協議）、ＥＳＣ-ＡＯＤＶ 協議進行仿真，在不同的節點數下的仿真對比，驗證所改進路由協議的優勢，每個場景運行５次求平均，仿真環境參數選取如表１所示。

機器人節點數量對平均端到端時延、數據包投遞率、節點平均剩余能量、路由開銷和吞吐量的影響如圖４～圖８所示。

由圖４ 可以看出，在機器人節點數量較少時，ＥＳＣ-ＡＯＤＶ 協議的平均端到端時延低于ＡＯＤＶ，但要高于ＥＬＳ-ＡＯＤＶ，這是由于網絡中節點數量較少時，到達目的節點的路由被簇結構所影響，會通過較長的路徑傳輸數據，節點的尋路時間變長，比不加入簇結構的ＥＬＳ-ＡＯＤＶ 協議延時大一些，但依舊優于ＡＯＤＶ 協議；在節點數量變多時，簇結構優勢被體現出來，減少了洪泛的廣播選路次數，通過簇頭和網關組成的骨干網絡尋路優于平面路由選路方式。由于用路由性能代替跳數作為路由判據，傳輸鏈路更加穩定，減少了路由修復時延。

由圖５ 可以看出，當節點數量較少時，會出現ＥＳＣ-ＡＯＤＶ 協議的包投遞率小于ＥＬＳ-ＡＯＤＶ，這是由于ＥＳＣ-ＡＯＤＶ 通信時，以１ 跳的鄰居節點作為簇內節點，進行簇間通信時，即使是原本２、３跳的路由也需要通過骨干路由到達。隨著節點數量的增加，ＥＳＣ-ＡＯＤＶ 協議的包投遞率優于ＥＬＳ-ＡＯＤＶ 和ＡＯＤＶ，這是由于節點數量較多時，節點間的通信鏈路都被延長，此時，簇結構能夠使得通信更加穩定，減少數據包碰撞概率。

由圖６ 可以看出，使用ＥＳＣ-ＡＯＤＶ 的網絡在運行２００ｓ之后節點的平均剩余能量高于使用ＥＬＳ-ＡＯＤＶ和ＡＯＤＶ的網絡。伴隨著節點數量的增加，ＥＳＣ-ＡＯＤＶ 相比于其他２種協議，能夠節省更多的能量，使得網絡運行更長時間，這是由于ＥＬＳ-ＡＯＤＶ通過路由判據的改進使得尋找到的路徑更優，而ＥＳＣ-ＡＯＤＶ 引入簇結構，使得廣播洪泛減少，進一步節省網絡能量。

由圖７可以看出，３種協議中，ＡＯＤＶ 的路由開銷最大，ＥＬＳ-ＡＯＤＶ 次之，ＥＳＣ-ＡＯＤＶ 最小，這是由于ＥＬＳ-ＡＯＤＶ 尋找到的路徑更穩定，減少了路由維護次數，而ＥＳＣ-ＡＯＤＶ 是由于簇頭與網關，使得簇內節點廣播洪泛次數減少，進一步降低了路由開銷。隨著節點增加，３種協議的路由開銷都隨之變大，但依舊是ＥＳＣ-ＡＯＤＶ 的路由開銷最小。

由圖８ 可以看出，節點數量較少時，ＥＬＳ-ＡＯＤＶ的吞吐量最大，ＥＳＣ-ＡＯＤＶ 高于ＡＯＤＶ 但低于ＥＬＳ-ＡＯＤＶ，這是由于ＥＬＳ-ＡＯＤＶ 將具有更高能量和更低速度的節點作為下一跳，路由更穩定，每秒傳輸更多的數據包，而ＥＳＣ-ＡＯＤＶ則由于簇結構的引入，導致有些路由變長，降低了包投遞率，從而降低了吞吐量。當節點數量變多時，ＥＳＣ-ＡＯＤＶ 憑借簇結構，使得網絡穩定性更好，減少路由重構次數，提高了網絡吞吐量。

４結束語

通過對群組機器人系統中ＡＯＤＶ協議的研究，針對應急救援場景下對網絡性能的更高要求，提出了ＥＳＣ-ＡＯＤＶ協議，綜合考慮能量、負載和速度的路由性能作為新的路由判據，引入分簇結構，通過簇頭和網關組成的骨干網絡減少簇內普通節點廣播洪泛，進一步節省能量。由仿真結果可以看出，通過選擇消耗能量更低、負載更小和速度更小的節點作為下一跳，利用分簇結構可以進一步減少網絡控制數據包數量。相比于ＡＯＤＶ 協議與ＥＬＳ-ＡＯＤＶ 協議，改進的路由協議ＥＳＣ-ＡＯＤＶ在延長網絡生存時間并減少平均端到端時延的同時，提高了可靠性，增大了吞吐量并降低了路由開銷。當節點數量較多時，ＥＳＣ-ＡＯＤＶ的性能更優，能更好地適應群組機器人在應急救援過程中的應用。總之，ＥＳＣ-ＡＯＤＶ對群組機器人路由協議研究具有一定的價值。

作者簡介

李明明 女，（１９７７—），碩士，副教授。主要研究方向：機器人技術、云計算及大數據技術。

邵立鵬 男，（１９９９—），碩士研究生。主要研究方向：群組機器技術、群組機器人網絡。