基于消息線程的群管理研究

謝志敏 梁進君 嚴宏舉 霍永華

摘要：針對節點局部移動或離開所在群所引起的群布局部分和全部失效問題，研究群維護算法和群首維護算法。群維護算法設計了離群節點快速入群或重新組群的算法，確定算法中涉及的消息格式，設計了節點在正常擔任群首職責期間對群成員的維護流程。通過設定群成員存活最新時間，定期進行心跳檢測，實時更新群成員列表，基于消息線程分時同步處理群消息，實現了群管理的實時性和準確性，維護群結構的穩定性。

關鍵詞：群首；分群結構；多屬性拍賣；消息線程

中圖分類號：TP393文獻標志碼：A文章編號：1008-1739（2018）15-67-3

Study on the Cluster Management Based on Message Threading

XIE Zhimin1， LIANG Jinjun2， YAN Hongju3， HUO Yong hua4（1. Special Office of PLA Marine Environment， Beijing 100181， China； 2. System Engineering Research Institute， Academy of Military Science， Beijing 100141， China； 3.Unit 31679， PLA， Xinxiang Henan 453000， China； 4. The 54th Research Institute of CETC， Shijiazhuang Hebei 050081， China）

0引言

在軍事應用環境下，節點移動性較強，導致網絡拓撲動態變化，分群結構頻繁變動對網絡運行性能和管理的效率產生極大的影響。提出的群維護算法和群成員維護算法，可以解決局部節點移動或離群所引起的群結構部分或全部失效問題，從而降低群成員或群首的離群對網絡性能的影響，并且離群節點能夠迅速加入新群或自組成群，從而避免重新調用分群算法而引起的大規模全網群重構。

1算法消息格式

解決節點部分移動所引起的群結構部分摧毀或全部摧毀問題，在群維護算法中，考慮了游離節點快速加入群或重新生成一個新群的方案的2種情況，避免重新調用分群算法所導致的全網重組。該算法提出以拍賣方式來解決群首委托問題，群首委托[1]是指由于設備處理能力變化、電量限制、安全能力限制及隸屬關系變化等原因，群首無法繼續執行群首職能，在其離群期限截止前由管理者指定或者群首選擇一個新的群首來替代其職能，令該群的管理和任務不受群首離群影響而繼續正常執行。

節點的3種狀態有未分群、群首和群成員狀態。節點在初始化時處于未分群狀態，經過分群后，節點的角色成為群首或群成員，此后進入群維護狀態。在群維護狀態中，群首或群成員如果離群，則有可能直接在群維護中轉變角色，或進入到未分群狀態[2-3]。

2群首維護算法

假設群首離群時限設置為（=1）min，收到的前一群成員應答消息的時間戳為_。群成員離群時限設置為（=1）分鐘，群首記錄更新一個群成員列表，該列表存儲著每個群成員的應答和反饋消息[4-5]，記錄應答消息的時間列表_[]，記錄該群成員的最新確認存活時間。在群首和群成員都維護一個接收群維護消息的超時計時器為_，該時限=（ ， ）。

群維護算法流程：

步驟1：周期性的群維護場景下，群首進行初始化，設置廣播信息的地址和端口，群首計時器設置初值_=當前時間，在群成員列表中，計時數組為_[]=當前時間。

步驟2：群首向群成員發送群維護請求消息包，以便確定當前群成員是否正常存在。群成員收到群首發送的群維護請求包后，要盡快向群首返回群維護響應包。

步驟3：群首每收到一個群維護響應包時，根據收到該包的當前時間，更新群維護計時器值_。當計時器值超過時限

后，超時時間△=當前時間- _。若△<，說明群首還在本群未離開，則需轉到步驟3.1，在該步驟中根據群首當前電量即將耗盡等原因進行群首委托的判斷，若群首無法繼續擔任該群的群首，則需要向管理者申請在群成員中選擇一個合適的群成員作為新的群首；若△>，則說明該群首已離群，轉步驟3.2，在此期間，如果群首收到新成員加入該群的請求消息，則將該消息進行暫存。

步驟3.1：判斷群首電池電量是否低于某個閾值（假設

=30%），若群首電池電量低于閾值，則向管理者提出群首轉任申請，若管理者指定新的群首，則轉入步驟3.1.3；若管理者回復群首自主進行職能委托，則轉到步驟3.1.1；否則電量充足，轉到步驟3.1.2。

步驟3.1.2：群首具有充足電量繼續擔任群首職能，執行步驟4。

步驟3.1.3：若管理者指定群首，原群首則對指定群首發送群首委托確認消息，并向管理者發送群首注銷請求消息以注銷自己的群首職能，同時釋放本地群成員列表信息、本地線程和緩沖區中待處理新成員加入請求消息等，將自身狀態轉為群成員狀態。

步驟3.2：若△>，則說明群首已離群，則向管理者發群首注銷請求消息以注銷自己群首職能，同時釋放本地群成員列表信息、本地線程和緩沖區中待處理新成員加入請求消息等，群首進入未分群狀態。

步驟4：群首繼續執行群維護功能，判斷本群群成員時候有離群操作。通過計算△=當前時間-群成員應答時間數組值_[ ]，判斷△與門限值的關系。若△[ ]≥，表示群成員有離群操作，轉入步驟4.1；否則標識該群中沒有群成員離群，轉入步驟5。

步驟5：判斷緩沖區中是否有新成員加入請求消息；若無請求消息，則轉到步驟6，若有請求消息，則進一步判斷當前群成員是否達到群上限（假設定義每個群規模限定成員最大個數為），若已經達到群上限，執行步驟5.1，否則若未達到群上限，則執行步驟5.2。

步驟5.1：群首發送群成員被拒絕消息，到待加入的群節點，繼續執行步驟6。

步驟5.2：發送群成員加入響應消息給待加入的節點。啟動等待計時器_，如果在計時器范圍內收到新成員加入確認消息，則更新本地群成員列表，執行步驟6；如超過計時器范圍，則直接執行步驟6。

步驟6：群首發送群成員更新消息給管理者，轉到步驟2，重復執行群維護過程。

在上述步驟中，群首委托是指當設備處理能力變化、電量限制、安全能力限制、隸屬關系變化等原因，可能導致群首無法繼續擔任群首職能。該群首需要在離群期限截止前選擇一個新的群首，并通告給管理者和原群成員。當某個群首選擇群首繼任者時，采用單輪、多屬性英式拍賣方式向群成員廣播群首委托邀請信息，群成員評估自身資源狀態，填入到群首委托響應消息，并回復給群首。群首評估各個群成員返回的各項屬性值，根據當前網絡需求調整的各個屬性權重因子，并選擇

最小的群成員作為群首繼任者。原群首向管理者注銷當前身份，并轉為普通群成員狀態。新群首需向管理者注冊，更新群成員列表。

設計了當群首發現自身電量不足、移動速度過大或安全能力[6-7]受到威脅時，需將群首職責委托給其他群成員。算法采用拍賣思想進行群首職責拍賣，各個群成員必須返回其值。通過群首職責委托，避免了大規模重新分群所帶來的額外網絡流量，大大減少了控制信息的數量。另外算法實時性強，可盡快選取新的群首實現對群成員的管理和維護。

設計了節點在正常擔任群首職責期間，對群成員的維護流程。群首處理新節點的入群請求，如未達到該群的規模上限，則返回群成員加入響應信息給新節點。當收到該節點的群成員加入確認信息后，獲取該節點當前狀態信息，更新群成員列表并上報給管理者。

3群成員維護算法

群成員維護算法步驟如下：

步驟1：群成員開啟離群的計時器_（計時器取值為群首發送群維護消息的周期時長），用以判斷自己是否已經離開當前所在的群。如果距離群首前一次廣播的群維護請求消息的等待時長已超出計時器范圍，則轉到步驟3進行離群判斷，否則轉到步驟2。

步驟2：如果收到群首周期性廣播的群維護請求消息，判定自己仍處于群中，給群首返回群維護響應消息，_取值更新為當前取值，并轉到步驟1；如果收到群首委托請求消息，根據自身各項資源狀態填入群首委托響應消息，并發送給群首，轉到步驟1；如果收到群首委托確認消息，則進入群首維護狀態，維護本地群成員列表。

步驟3：若當前取值_超出范圍，則判斷為群成員已經離群。群首查詢距離自己距離為一跳的鄰居節點是否也處于未分群狀態，若處于未分群狀態，則轉到步驟3.1，否則為已分群狀態，轉到步驟3.2。

步驟3.1：若群首發現有未分群的距離為一跳鄰居節點存在，說明群首離群導致當前群失效，則處于未分群狀態的所有節點均重新執行分群算法進行重新組群。

步驟3.2：群成員查詢鄰居表中是否有群首。若無群首，該節點自組成新群。若有群首，則向群首發送群成員加入請求消息并等待群首應答，同時啟動消息接收線程和計時器，進入步驟4。

步驟4：當收到第一個群成員回復的加入響應消息時（假設群首同意群成員加入），則發送群成員加入群的確認消息給群首。同時把群信息加入到本地群成員列表，轉步驟1；若收到群首發送的拒絕入群消息，且收到消息時并未超時，則群首繼續在消息線程中等待接收新的群成員響應消息；若未收到任何群成員加入響應消息且已經超時，即沒有任何群首同意新群成員加入，則該群節點自組成新群。

離群的計時器_的設置周期等同于群首發送群維護消息的周期時長，當超出計時器范圍時，說明自身已不處于群首的管轄范圍，需按離群節點重新加入某一個群。

4結束語

群維護算法對分群算法完成后的分級網絡結構進行支撐和調整，群維護算法的設計需要盡量確保調整后網絡中的群規模不超過上限，從而節省群首維護控制開銷，并且群數量維持在恰當數量，從而減少全網控制信息的交互能耗。另外實時性也是考察群維護算法的重要指標之一，離群節點需要盡快加入新群或重新自組成群，從而維護整個分級網絡結構的穩定和完整，增強了軍事網絡的魯棒性和抗毀性。

參考文獻

[1]鄭相全等編著.無線自組網技術實用教程[M].北京：清華大學出版社，2004.

[2]王海濤，田暢，鄭少仁.一種新型的Ad Hoc網絡分簇算法及其性能仿真[J].系統仿真學報，2003，15（2）：193-197.

[3]蒲瀟.戰術自組網網絡結構及分群算法研究[D].大連：大連理工大學，2009.

[4]林軍.Ad Hoc按需加權自適應（AOW）算法的改進研究[D].天津：天津大學，2006.

[5]程偉明，周新運.一個用于Ad Hoc網絡的分簇方法[J].計算機學報，2005，28（5）：864-869.

[6]程偉明，鄭健平，盛凌志.一個Ad Hoc網絡中的簇結構模式[J].計算機研究與發展，2004，41（4）：674-678.

[7]胡光明.簇結構移動自組網絡安全關鍵技術研究[D].長沙：國防科學技術大學，2007.