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

謝志敏 梁進(jìn)君 嚴(yán)宏舉 霍永華

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

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

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)志碼：A文章編號(hào)：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引言

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

1算法消息格式

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

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

2群首維護(hù)算法

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

群維護(hù)算法流程：

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

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

步驟3：群首每收到一個(gè)群維護(hù)響應(yīng)包時(shí)，根據(jù)收到該包的當(dāng)前時(shí)間，更新群維護(hù)計(jì)時(shí)器值_。當(dāng)計(jì)時(shí)器值超過(guò)時(shí)限

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3群成員維護(hù)算法

群成員維護(hù)算法步驟如下：

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

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

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

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

步驟3.2：群成員查詢(xún)鄰居表中是否有群首。若無(wú)群首，該節(jié)點(diǎn)自組成新群。若有群首，則向群首發(fā)送群成員加入請(qǐng)求消息并等待群首應(yīng)答，同時(shí)啟動(dòng)消息接收線程和計(jì)時(shí)器，進(jìn)入步驟4。

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

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

[5]程偉明，周新運(yùn).一個(gè)用于Ad Hoc網(wǎng)絡(luò)的分簇方法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（5）：864-869.

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

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