摘要：為了在無法獲知全網(wǎng)拓撲情況下解決無人機集群網(wǎng)絡(luò)中的環(huán)路問題，本文設(shè)計了一種基于鄰居關(guān)系的環(huán)路避免方法。此方法針對性地避免鏈狀鏈路引起的網(wǎng)絡(luò)環(huán)路，包括鏈狀拓撲節(jié)點身份判別、鏈狀拓撲節(jié)點集合建立、變更與注銷，以及基于鏈狀拓撲節(jié)點集合的選路策略。各節(jié)點通過鄰居數(shù)量判斷本節(jié)點的身份信息，包括鏈狀拓撲末端節(jié)點、鏈狀拓撲中間節(jié)點、鏈狀拓撲首節(jié)點。鏈狀拓撲節(jié)點向其他鏈狀拓撲節(jié)點以及鏈狀拓撲首節(jié)點的鄰居進行身份通告，從而建立鏈狀拓撲節(jié)點集合。當(dāng)鄰居關(guān)系或鏈狀拓撲節(jié)點身份發(fā)生變化時，通過身份通告來更新鏈狀拓撲節(jié)點集合，或通過注銷報文刪除鏈狀拓撲節(jié)點集合。當(dāng)鏈狀拓撲首節(jié)點的鄰居接收到目的節(jié)點為鏈狀拓撲節(jié)點的報文時，直接選擇鏈狀拓撲首節(jié)點為下一跳，以此避免環(huán)路問題的發(fā)生。此方法無需依賴全網(wǎng)拓撲為先驗信息，且節(jié)點身份信息無需擴散至全網(wǎng)，所以開銷較小。

關(guān)鍵詞：無人機集群；Ad hoc網(wǎng)絡(luò)；鏈狀拓撲；網(wǎng)絡(luò)環(huán)路

無人機集群憑借低成本和高效工作的優(yōu)點被廣泛應(yīng)用于各個領(lǐng)域。無人機之間進行組網(wǎng)和通信是實現(xiàn)無人機協(xié)同工作的關(guān)鍵[1-2]。但由于無人機集群相對運動較為劇烈，拓撲變化較快，獲取全網(wǎng)拓撲的代價較大且?guī)捹Y源不充足，導(dǎo)致無人機集群網(wǎng)絡(luò)面臨許多問題，其中網(wǎng)絡(luò)環(huán)路問題尤為緊迫[3-4]。網(wǎng)絡(luò)環(huán)路將導(dǎo)致網(wǎng)絡(luò)開銷增加，甚至使報文無法轉(zhuǎn)發(fā)至目的節(jié)點[5]。

部分研究基于特定的路由協(xié)議解決環(huán)路問題，如靜態(tài)路由、OSPF等，極大地限制了上述網(wǎng)絡(luò)環(huán)路避免方法的應(yīng)用場景，不具備普適性，難以應(yīng)用于約束較多、拓撲隨任務(wù)變化的無人機集群網(wǎng)絡(luò)[6-8]。或采用人工智能算法進行環(huán)路檢測，但無人機計算資源較為欠缺，難以運行人工智能算法[9-10]。而基于環(huán)路探測或基于標(biāo)簽等方式避免網(wǎng)絡(luò)環(huán)路不限定拓撲形狀和路由協(xié)議，適用范圍較廣。環(huán)路探測通過發(fā)送環(huán)路檢測報文和環(huán)路檢測幀等完成，通過探測顯化網(wǎng)絡(luò)環(huán)路，從而針對性地解決環(huán)路問題；然而，頻繁變化的拓撲導(dǎo)致環(huán)路探測結(jié)果的有效期較短，但增加探測頻率將增加網(wǎng)絡(luò)開銷，且環(huán)路檢測報文并非在環(huán)路產(chǎn)生時觸發(fā)，即無環(huán)路問題時，進行環(huán)路檢測的開銷是不必要的[11-12]。當(dāng)采用路由標(biāo)簽避免環(huán)路問題時，要求將標(biāo)簽值全網(wǎng)同步，同樣存在不靈活和對帶寬要求高的問題[13]。

為了適應(yīng)無人機集群網(wǎng)絡(luò)拓撲變化快、帶寬資源不足的特點，且考慮到鏈狀拓撲在全網(wǎng)拓撲未知的條件下極其容易產(chǎn)生環(huán)路問題，即當(dāng)報文的目標(biāo)節(jié)點位于鏈狀拓撲中，其局部轉(zhuǎn)發(fā)路徑是唯一的，報文必須經(jīng)過該鏈狀拓撲的首節(jié)點才能轉(zhuǎn)發(fā)至鏈狀拓撲中的其他節(jié)點。

本文設(shè)計一種基于鄰居關(guān)系的網(wǎng)絡(luò)環(huán)路避免方法，該方法基于鄰居數(shù)量確定節(jié)點是否位于鏈狀拓撲中，完成身份判別后，鏈狀拓撲節(jié)點向特定的鄰居進行身份通告，建立鏈狀拓撲節(jié)點集合，身份通告僅在鏈狀拓撲節(jié)點和鏈狀拓撲首節(jié)點的鄰居之間完成，無需擴散至全網(wǎng)。當(dāng)鏈狀拓撲首節(jié)點的鄰居對目標(biāo)節(jié)點為鏈狀拓撲節(jié)點的報文進行轉(zhuǎn)發(fā)時，直接選擇鏈狀拓撲首節(jié)點為下一跳。當(dāng)鄰居關(guān)系或鏈狀拓撲節(jié)點身份發(fā)生變化時，通過身份通告進行鏈狀拓撲節(jié)點集合更新，或通過注銷報文刪除鏈狀拓撲節(jié)點集合。該網(wǎng)絡(luò)環(huán)路避免方法僅在鏈狀拓撲產(chǎn)生或改變時進行身份通告和注銷報文轉(zhuǎn)發(fā)，且上述報文的轉(zhuǎn)發(fā)僅在鏈狀拓撲節(jié)點及鏈狀拓撲首節(jié)點的鄰居之間完成，無需擴散到全網(wǎng)，極大地減小了控制開銷。

一、鏈狀拓撲節(jié)點建模

為了能夠識別無人機集群中的鏈狀拓撲節(jié)點，并對目的節(jié)點為鏈狀拓撲節(jié)點的尋路進行特殊處理，本小節(jié)對鏈狀拓撲節(jié)點進行建模。設(shè)無人機集群包含m個節(jié)點，其節(jié)點集合為。針對節(jié)點，其鄰居節(jié)點集合為。

定義1：設(shè)為鏈狀拓撲末端節(jié)點集合，的節(jié)點為鏈狀拓撲末端節(jié)點，即鏈狀拓撲末端節(jié)點為有且僅有1個鄰居的節(jié)點。設(shè)為鏈狀拓撲中間節(jié)點集合，的節(jié)點為鏈狀拓撲中間節(jié)點，即鏈狀拓撲中間節(jié)點有且僅有2個鄰居。

定義2：設(shè)為鏈狀拓撲首節(jié)點集合，的節(jié)點為鏈狀拓撲首節(jié)點，即鏈狀拓撲首節(jié)點為鄰居數(shù)量大于等于3并且至少其中一個鄰居為鏈狀拓撲中間節(jié)點或鏈狀拓撲末端節(jié)點。

顯然，當(dāng)目標(biāo)節(jié)點或，確定相應(yīng)的鏈狀拓撲首節(jié)點能夠避免環(huán)路，即鏈狀拓撲首節(jié)點需確認與其相關(guān)的鏈狀拓撲首節(jié)點或鏈狀拓撲中間節(jié)點，形成鏈狀拓撲節(jié)點集合。

定義3：鏈狀拓撲節(jié)點集合為由鏈狀拓撲末端節(jié)點、鏈狀拓撲中間節(jié)點、鏈狀拓撲首節(jié)點構(gòu)成的鏈路，其中由直接與節(jié)點Xe或節(jié)點Xo連接的節(jié)點、僅通過其他鏈狀拓撲中間節(jié)點與節(jié)點Xe或節(jié)點Xo連接的節(jié)點。

需要注意的是，允許。顯然，當(dāng)轉(zhuǎn)發(fā)目的節(jié)點的報文，且節(jié)點Xo為當(dāng)前節(jié)點的鄰居時，當(dāng)前節(jié)點必須選擇節(jié)點Xo作為下一跳，否則將形成環(huán)路。

二、鏈狀拓撲節(jié)點確認與解除

（一）鏈狀拓撲節(jié)點確認與身份通告

顯然，鏈狀拓撲首節(jié)點Xo需要確認與其相關(guān)的鏈狀拓撲節(jié)點集合，并將該集合通告至其鄰居節(jié)點，以便于其鄰居節(jié)點轉(zhuǎn)發(fā)相關(guān)報文時將其選為下一跳。為了減少控制開銷，鏈狀拓撲節(jié)點通告由鏈狀拓撲末端節(jié)點發(fā)起。各節(jié)點周期性確認本節(jié)點身份，有且只有1個鄰居的節(jié)點確認為鏈狀拓撲末端節(jié)點，有且只有2個鄰居的節(jié)點確認為鏈狀拓撲中間節(jié)點。鏈狀拓撲末端節(jié)點和鏈狀拓撲中間節(jié)點確認身份后，向其鄰居發(fā)送鏈狀拓撲節(jié)點身份通告報文。需要注意的是，鏈狀拓撲首節(jié)點的身份確認需要在接收到鄰居發(fā)送的身份通告報文后才能完成。需要注意的是，僅鏈狀拓撲末端節(jié)點能主動發(fā)起身份通告，鏈狀拓撲中間節(jié)點和鏈狀拓撲首節(jié)點需接收到鄰居發(fā)送的身份通告報文后，再向其鄰居發(fā)送身份通告報文，使身份通告報文從鏈狀拓撲末端節(jié)點向鏈狀拓撲首節(jié)點單向傳遞，減少控制開銷，簡化處理策略。當(dāng)鏈狀拓撲末端節(jié)點確認身份后，主動向唯一的鄰居發(fā)送身份通告報文；鏈狀拓撲中間節(jié)點接收到其中一個鄰居發(fā)送的身份通告報文后，將自己的身份信息加入該身份通告報文中，按協(xié)議整理后發(fā)送至另一個未給本節(jié)點發(fā)送身份通告報文的鄰居。

當(dāng)節(jié)點接收到鄰居發(fā)送的身份通告報文，且本節(jié)點非鏈狀拓撲末端節(jié)點和鏈狀拓撲中間節(jié)點，即本節(jié)點的鄰居數(shù)量大于等于3，則該節(jié)點確認為鏈狀拓撲首節(jié)點。同樣地，鏈狀拓撲首節(jié)點將自己的身份信息加入身份通告報文中，并發(fā)送至除鏈狀拓撲中間節(jié)點和鏈狀拓撲末端節(jié)點以外的所有鄰居。普通節(jié)點收到通告報文后，無需繼續(xù)進行轉(zhuǎn)發(fā)。普通節(jié)點通過路徑首節(jié)點發(fā)送的身份通告報文，知悉與其鄰居Xo相關(guān)的鏈狀拓撲，當(dāng)普通節(jié)點轉(zhuǎn)發(fā)報文的目的節(jié)點時，直接選擇鄰居Xo為下一跳。

（二）鏈狀拓撲節(jié)點變更與注銷

當(dāng)拓撲發(fā)生變化，節(jié)點的身份或者鄰居關(guān)系將發(fā)生變化，相應(yīng)的鏈狀拓撲可能改變甚至是消失，因此，需要對鏈狀拓撲節(jié)點的身份進行解除并通告給鄰居。

為了便于注銷或更新鏈狀拓撲節(jié)點集合，對鏈狀拓撲前向鄰居和后向鄰居進行定義：

定義4：鏈狀拓撲節(jié)點Xj的前向鄰居滿足，鏈狀拓撲節(jié)點Xi的前向鄰居滿足，其中hop（Xi， Xj）為節(jié)點Xi到鏈狀拓撲末端節(jié)點Xj的最小跳數(shù)。

即節(jié)點Xi的前向鄰居為其更靠近鏈狀拓撲末端節(jié)點Xe的鄰居，后向鄰居為其更靠近鏈狀拓撲首節(jié)點Xo的鄰居。顯然，鏈狀拓撲末端節(jié)點無前向鄰居，鏈狀拓撲首節(jié)點無后向鄰居。

當(dāng)鏈狀拓撲節(jié)點的拓撲狀態(tài)發(fā)生變化，在必要時需向相應(yīng)鄰居發(fā)送鏈狀拓撲節(jié)點集合注銷報文。當(dāng)節(jié)點收到鄰居發(fā)送的注銷報文時，直接根據(jù)報文中的鏈狀拓撲節(jié)點集合ID刪除本地存儲的相應(yīng)鏈狀拓撲節(jié)點集合。此外，假如收到注銷報文的節(jié)點為鏈狀拓撲中間節(jié)點，該節(jié)點需將注銷報文轉(zhuǎn)發(fā)至其后向鄰居；假如收到注銷報文的節(jié)點為鏈狀拓撲首節(jié)點，該節(jié)點需將注銷報文轉(zhuǎn)發(fā)至其所有非鏈狀拓撲節(jié)點鄰居。引起鏈狀拓撲節(jié)點集合變化的情況包括鄰居關(guān)系變化或鏈狀拓撲節(jié)點身份變更，針對不同的鏈狀拓撲節(jié)點，其處理策略不同。

1.鏈狀拓撲末端節(jié)點

鏈狀拓撲末端節(jié)點的連接關(guān)系變化后，其身份變更或鏈狀拓撲節(jié)點集合注銷工作流程圖1所示。當(dāng)其僅發(fā)生鄰居關(guān)系變化時，即該節(jié)點仍然只有1個鄰居，但該鄰居為新鄰居，此時鏈狀拓撲末端節(jié)點向新鄰居發(fā)起身份通告。當(dāng)鏈狀拓撲末端節(jié)點身份發(fā)生變化時，即變更為鏈狀拓撲中間節(jié)點、鏈狀拓撲首節(jié)點或普通節(jié)點時，假如原后向鄰居存在，則向后向鄰居發(fā)送注銷報文。

2.鏈狀拓撲中間節(jié)點

鏈狀拓撲中間節(jié)點的連接關(guān)系變化后，當(dāng)僅鄰居關(guān)系發(fā)生變化，即該節(jié)點仍有且僅有2個鄰居，但前向鄰居或后向鄰居發(fā)生變化，針對前向鄰居發(fā)生變化的情況，假如原后向鄰居存在，則向后向鄰居發(fā)送注銷報文；針對后向鄰居變化情況，假如原前向鄰居存在，則向新的后向鄰居發(fā)送身份通告，更新鏈狀拓撲節(jié)點集合。當(dāng)節(jié)點身份發(fā)生變化，假如變更為鏈狀拓撲末端節(jié)點，則向后向鄰居發(fā)送新的身份通告，形成新的鏈狀拓撲節(jié)點集合；假如變更為鏈狀拓撲首節(jié)點，當(dāng)原前向鄰居存在時，向非鏈狀拓撲節(jié)點的所有鄰居發(fā)送身份通告，當(dāng)原前向鄰居不存在且后向鄰居存在時，向原后向鄰居發(fā)送注銷報文；假如變更為普通節(jié)點，且后向鄰居不變，則向后向鄰居發(fā)送注銷報文。

3.鏈狀拓撲首節(jié)點

鏈狀拓撲首節(jié)點的連接關(guān)系變化后，當(dāng)僅鄰居關(guān)系發(fā)生變化時，假如前向鄰居保持不變，則向新的鄰居發(fā)送身份通告；否則，向所有非鏈狀拓撲節(jié)點鄰居發(fā)送注銷報文。對于節(jié)點身份的變更，如果變更為鏈狀拓撲末端節(jié)點，并且后向鄰居保持不變，那么向后向鄰居發(fā)送注銷報文并發(fā)起新的身份通告；否則，直接向后向鄰居發(fā)送身份通告。對于變更為鏈狀拓撲中間節(jié)點的情況，如果前向鄰居保持不變，那么向后向鄰居發(fā)送身份通告；否則，向原來的后向鄰居發(fā)送注銷報文。如果變更為普通節(jié)點，并且前向鄰居發(fā)生變化但后向鄰居保持不變，或者前向鄰居發(fā)生變化且后向鄰居發(fā)生變化，那么向后向鄰居發(fā)送注銷報文。

4.鏈狀拓撲首節(jié)點的鄰居

針對鏈狀拓撲首節(jié)點的鄰居，僅需鏈狀拓撲首節(jié)點是否仍為鄰居，如與鏈狀拓撲首節(jié)點的連接斷開，直接刪除本地存儲的相應(yīng)鏈狀拓撲節(jié)點集合。

三、基于鏈狀拓撲節(jié)點集合的選路策略

針對存在ns條鏈狀拓撲的網(wǎng)絡(luò)，該鏈狀拓撲首節(jié)點的所有鄰居均存儲了鏈狀拓撲節(jié)點集合，上述節(jié)點轉(zhuǎn)發(fā)報文基于鏈狀拓撲節(jié)點集合進行選路。即鏈狀拓撲首節(jié)點的所有鄰居對目的節(jié)點的報文進行轉(zhuǎn)發(fā)時，無需根據(jù)采用的路由算法，直接選擇鏈狀拓撲首節(jié)點為下一跳。

四、結(jié)束語

針對無人機集群網(wǎng)絡(luò)拓撲變化劇烈、無法獲取全網(wǎng)拓撲的情況，本文設(shè)計一種基于鄰居關(guān)系的環(huán)路避免方法，針對性解決鏈狀鏈路引起的網(wǎng)絡(luò)環(huán)路問題。通過鏈狀拓撲節(jié)點身份判別、鏈狀拓撲節(jié)點集合建立、變更與注銷策略，使鏈狀拓撲首節(jié)點的鄰居能識別鏈狀拓撲節(jié)點，并對目的節(jié)點為鏈狀拓撲節(jié)點的報文的下一跳選擇進行特殊處理，從而避免環(huán)路問題。該方法適用于任意拓撲，且節(jié)點身份信息無需擴散至全網(wǎng)，開銷較小。

作者單位：伍擎 中國電子科技集團公司第七研究所

參考文獻

[1]Wenfei Wang， Maolong Lv， Le Ru， Bo Lu， Shiguang Hu， Xiniong Chang. Multi-UAV Unbalanced Targets Coordinated Dynamic Task Allocation in Phases， Aerospace 2022， 9（9）， 491.

[2]Yong Li， Mohong Zheng. Routing prediction strategy for UAN swarm network using pigeon-inspired optimization based neural network[J]. International Journal of Aeronautical and Space Sciences.[2023-06-26].

[3]ZiweiYuan， Yanping Yang， Dong Wang， Xiaoping Ma. Energy-Efficient Trajectory Optimization for UAV-Enabled Cellular Communications Based on Physical-Layer Security. Aerospace 2022， 9（2）， 50; https：//doi.org/10.3390/aerospace9020050

[4]劉汪根，鄭淮城，榮國平.云環(huán)境下大規(guī)模分布式計算數(shù)據(jù)感知的調(diào)度系統(tǒng)[J].大數(shù)據(jù)， 2020.

[5]李龍飛，張涇周，王鵬德等.基于節(jié)點興趣和Q-learning的P2P網(wǎng)絡(luò)搜索機制[J].計算機科學(xué)， 2020， 47（2）：6.

[6]姚玉坤，劉江兵，李小勇等.LLN中基于環(huán)路避免的高效路由修復(fù)算法[J].系統(tǒng)工程與電子技術(shù)， 2018， 40（5）：7.

[7]黃德玲，嚴余松，彭大芹.城市車輛自組織網(wǎng)絡(luò)中基于預(yù)測的地理位置路由協(xié)議[J].計算機科學(xué)， 2019.

[8]張靚晶，鈕大騫.局域網(wǎng)網(wǎng)絡(luò)環(huán)路故障排查及解決措施[J].無線互聯(lián)科技， 2022（019-005）.

[9]李揚.基于移動群智感知的大規(guī)模網(wǎng)絡(luò)異常檢測[D].上海交通大學(xué)，2019.

[10]劉江兵.低功耗有損網(wǎng)絡(luò)中的RPL路由協(xié)議研究[D].重慶郵電大學(xué)，2018.

[11]范敏，魏書偉，張海霞.通過交換機檢測解決網(wǎng)絡(luò)環(huán)路的探索[J].無線互聯(lián)科技， 2022（004）：019.

[12]李琦，朱潔，陳艷毓等.檢測軟件定義網(wǎng)絡(luò)（SDN）中的路由環(huán)路的系統(tǒng)和方法：CN201810437997.5[P].CN108881005A[2023-06-26].

[13]王德兵，孫道遠.路由標(biāo)簽在規(guī)避路由環(huán)路與次優(yōu)路徑中的應(yīng)用研究[J].吉林工程技術(shù)師范學(xué)院學(xué)報， 2021.