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

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

關(guān)鍵詞：群首；分群結(jié)構(gòu)；多屬性拍賣；消息線程

中圖分類號：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引言

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

1算法消息格式

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

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

2群首維護算法

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

群維護算法流程：

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

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

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

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

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

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

步驟3.1.2：群首具有充足電量繼續(xù)擔任群首職能，執(zhí)行步驟4。

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

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

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

步驟5：判斷緩沖區(qū)中是否有新成員加入請求消息；若無請求消息，則轉(zhuǎn)到步驟6，若有請求消息，則進一步判斷當前群成員是否達到群上限（假設(shè)定義每個群規(guī)模限定成員最大個數(shù)為），若已經(jīng)達到群上限，執(zhí)行步驟5.1，否則若未達到群上限，則執(zhí)行步驟5.2。

步驟5.1：群首發(fā)送群成員被拒絕消息，到待加入的群節(jié)點，繼續(xù)執(zhí)行步驟6。

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

步驟6：群首發(fā)送群成員更新消息給管理者，轉(zhuǎn)到步驟2，重復執(zhí)行群維護過程。

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

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

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

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

3群成員維護算法

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

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

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

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

步驟3.1：若群首發(fā)現(xiàn)有未分群的距離為一跳鄰居節(jié)點存在，說明群首離群導致當前群失效，則處于未分群狀態(tài)的所有節(jié)點均重新執(zhí)行分群算法進行重新組群。

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

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

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

4結(jié)束語

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

參考文獻

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

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

[3]蒲瀟.戰(zhàn)術(shù)自組網(wǎng)網(wǎng)絡結(jié)構(gòu)及分群算法研究[D].大連：大連理工大學，2009.

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

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

[6]程偉明，鄭健平，盛凌志.一個Ad Hoc網(wǎng)絡中的簇結(jié)構(gòu)模式[J].計算機研究與發(fā)展，2004，41（4）：674-678.

[7]胡光明.簇結(jié)構(gòu)移動自組網(wǎng)絡安全關(guān)鍵技術(shù)研究[D].長沙：國防科學技術(shù)大學，2007.