一種群維護(hù)算法研究

焦利彬 趙波 趙志軍

摘要：針對(duì)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化下的群結(jié)構(gòu)維護(hù)問題，提出了群首維護(hù)算法和群成員維護(hù)算法，詳細(xì)介紹了算法流程。群維護(hù)算法對(duì)群規(guī)模和群數(shù)量進(jìn)行控制，基于群結(jié)構(gòu)進(jìn)行自適應(yīng)調(diào)整，設(shè)定離群定時(shí)器同時(shí)周期性廣播群消息，群首與群成員交互的信息包含節(jié)點(diǎn)的各項(xiàng)屬性信息和資源信息，最終計(jì)算出綜合評(píng)判值，以此判斷最佳群首和群成員。

關(guān)鍵詞：群首維護(hù)；群成員維護(hù)；離群定時(shí)器；廣播群消息

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2020）02-57-4

0引言

戰(zhàn)場(chǎng)網(wǎng)絡(luò)節(jié)點(diǎn)具有高動(dòng)態(tài)性，隨時(shí)隨地向不同的方向移動(dòng)導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)連接關(guān)系頻繁變化、拓?fù)浣Y(jié)構(gòu)頻繁變化和重組、節(jié)點(diǎn)脫管失效及管理群結(jié)構(gòu)發(fā)生動(dòng)態(tài)變化，因此有必要研究管理群維護(hù)的相關(guān)內(nèi)容和算法，使群拓?fù)浣Y(jié)構(gòu)對(duì)群內(nèi)節(jié)點(diǎn)的移動(dòng)或位置變化具有實(shí)時(shí)感知和應(yīng)對(duì)能力，并且離群節(jié)點(diǎn)能夠迅速找到并加入新群或自組成群。

群管理維護(hù)旨在對(duì)動(dòng)態(tài)變化的管理群結(jié)構(gòu)進(jìn)行實(shí)時(shí)調(diào)整和管控，因此群管理維護(hù)的研究應(yīng)該確保變化且調(diào)整后的管理群規(guī)?？刂圃诤侠矸秶鷥?nèi)，首先要減少高動(dòng)態(tài)群實(shí)時(shí)維護(hù)和管理的消息開銷，同時(shí)動(dòng)態(tài)群的數(shù)量也要控制在合理范圍內(nèi)，確保整個(gè)網(wǎng)絡(luò)管理控制信息的帶寬占用和消耗。群維護(hù)算法主要聚焦管理群內(nèi)局部節(jié)點(diǎn)加入或離開所導(dǎo)致的整個(gè)群結(jié)構(gòu)部分或全部失效的現(xiàn)象，重點(diǎn)研究高動(dòng)態(tài)移動(dòng)節(jié)點(diǎn)脫離某個(gè)群或重新加入某個(gè)新群的實(shí)時(shí)管理方案，避免大規(guī)模節(jié)點(diǎn)移動(dòng)或離開而引起的大規(guī)模網(wǎng)絡(luò)重構(gòu)脫管。另外群管理維護(hù)方案也考慮實(shí)時(shí)性問題，離群節(jié)點(diǎn)需要盡快加入新群或重新自組成群，確保整體網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定和完整，進(jìn)而提升網(wǎng)絡(luò)的可靠性和抗毀性。

1群首維護(hù)算法

1.1算法消息格式

當(dāng)群首生成或群首變更引起群結(jié)構(gòu)發(fā)生變化時(shí)，網(wǎng)絡(luò)管理者需要實(shí)時(shí)維護(hù)并更新群結(jié)構(gòu)，確認(rèn)群首的管理功能及范圍。另外，考慮到網(wǎng)絡(luò)中的節(jié)點(diǎn)具有隨機(jī)移動(dòng)性，網(wǎng)絡(luò)拓?fù)湟矔?huì)隨之變化，導(dǎo)致群成員與群首之間的連通關(guān)系可能會(huì)頻繁變化。需要研究當(dāng)群首位置發(fā)生變動(dòng)或由于自身電量等問題而無法承擔(dān)管理職能時(shí)，該群首需將管理職能委托給具有充足的能量資源、位置穩(wěn)定的群成員，從而維護(hù)管理分群的穩(wěn)定。

在群結(jié)構(gòu)中，群節(jié)點(diǎn)通常有不屬于任何群、群首和群節(jié)點(diǎn)成員的3種存在狀態(tài)。在網(wǎng)絡(luò)拓?fù)涑跏家?guī)劃時(shí)，節(jié)點(diǎn)處于獨(dú)立存在狀態(tài)，基于規(guī)劃進(jìn)行管理分群或拓?fù)浞秩汉螅?jié)點(diǎn)的狀態(tài)由獨(dú)立節(jié)點(diǎn)變化或升級(jí)為群首或群節(jié)點(diǎn)，此后進(jìn)入正常的群運(yùn)行狀態(tài)。在群維護(hù)中，如果發(fā)生群首故障離群或群節(jié)點(diǎn)移動(dòng)離群事件，則節(jié)點(diǎn)的狀態(tài)會(huì)發(fā)生改變，在未分群、群首和群成員之間切換。

算法中使用的消息定義如下：①群首注銷請(qǐng)求消息由群首生成，用于向管理者通知自身不再為群首；②新群首注冊(cè)請(qǐng)求消息；③新群首注冊(cè)響應(yīng)消息由管理者生成，用于向新群首確認(rèn)其注冊(cè)信息；④群查詢請(qǐng)求消息由注冊(cè)終端發(fā)給群首，請(qǐng)求查詢?nèi)撼蓡T詳細(xì)信息；⑤群查詢響應(yīng)消息由群首將該群成員列表詳細(xì)信息發(fā)送給注冊(cè)終端。

1.2群首管理算法

群首一般有屬于或不屬于某個(gè)群2種狀態(tài)，如果群首不屬于某個(gè)群，則設(shè)定一個(gè)群首離群時(shí)間閾值，初始設(shè)置為（=1）min，為了保持管理實(shí)時(shí)性，群首基于線程與群內(nèi)節(jié)點(diǎn)進(jìn)行信息交互，發(fā)送心跳信息。將群首收到的不同群成員應(yīng)答消息的時(shí)間間隙設(shè)為_cnt min，群成員節(jié)點(diǎn)離開群的時(shí)間閾值設(shè)定為，初始化=1。

通常群成員節(jié)點(diǎn)信息由群首實(shí)時(shí)管理以列表形式存儲(chǔ)，包括群首與每個(gè)群成員的握手、心跳檢測(cè)和檢測(cè)反饋消息，交互消息的時(shí)間記錄信息以數(shù)組形式存儲(chǔ)于_cnt[]消息數(shù)組中，對(duì)應(yīng)的是該群成員節(jié)點(diǎn)確認(rèn)存活的最新時(shí)間。

設(shè)定一個(gè)接收群維護(hù)消息的超時(shí)計(jì)時(shí)器，記作為_cnt，該計(jì)時(shí)器由群首和群成員共同維護(hù)，將計(jì)時(shí)器的初始值設(shè)定為離群時(shí)間閾值，最小值初始化為=min（ ， ）。

群管理維護(hù)算法的步驟如下：

步驟1：基于固定周期的典型群管理，將群首相關(guān)信息進(jìn)行初始化配置，初始化配置內(nèi)容包括①群首發(fā)送的廣播信息的地址和端口號(hào)；②初始化群首離開群的時(shí)間計(jì)時(shí)器，離群時(shí)間變量設(shè)置為_cnt，初始化設(shè)定為當(dāng)前時(shí)間；③群首維護(hù)的群節(jié)點(diǎn)成員信息的列表計(jì)時(shí)數(shù)組設(shè)為_cnt[]，初始值設(shè)定為當(dāng)前時(shí)間。

步驟2：群首向所有群內(nèi)成員節(jié)點(diǎn)廣播群管理維護(hù)請(qǐng)求消息，目的是通過心跳消息確認(rèn)當(dāng)前所有群成員節(jié)點(diǎn)的實(shí)時(shí)狀態(tài)，即是存活還是死亡。當(dāng)群成員收到群管理維護(hù)的廣播消息后，經(jīng)分析是狀態(tài)確認(rèn)請(qǐng)求消息，則第一時(shí)間以點(diǎn)對(duì)點(diǎn)消息通信方式向群首返回群節(jié)點(diǎn)狀態(tài)，確認(rèn)維護(hù)響應(yīng)消息。

步驟3：當(dāng)群節(jié)點(diǎn)發(fā)送的狀態(tài)確認(rèn)群維護(hù)響應(yīng)消息被發(fā)送到群首時(shí)，群首以消息包攜帶的時(shí)間戳信息為依據(jù)，更新計(jì)時(shí)器數(shù)組中對(duì)應(yīng)的_cnt值。如果計(jì)時(shí)器出現(xiàn)越限情況，則計(jì)算超出時(shí)間差△=當(dāng)前時(shí)間- _cnt，并判斷超時(shí)時(shí)間△與時(shí)間閾值的大小。

如果超時(shí)時(shí)間△<，表明群首依然在群中，尚未離群，則轉(zhuǎn)入步驟3.1。在步驟3.1中群首當(dāng)前電量的實(shí)時(shí)情況是群首能否繼續(xù)任職的唯一判斷標(biāo)準(zhǔn)，如果群首電量即將耗盡，則群首立即向管理者發(fā)送群首委任卸任申請(qǐng)消息，管理者收到群首發(fā)送的委任申請(qǐng)消息后，立刻進(jìn)行群節(jié)點(diǎn)狀態(tài)查詢，選擇群節(jié)點(diǎn)狀態(tài)為正常且滿足要求的群成員節(jié)點(diǎn)，發(fā)送群首任命消息，宣布新的群首。

若超時(shí)差△>，則表明該群首由于種種原因目前已經(jīng)離開所在群，此時(shí)轉(zhuǎn)入步驟3.2。離開的群首在等待管理者發(fā)送的群首委任反饋消息的時(shí)間內(nèi)，如果收到非本群新成員節(jié)點(diǎn)發(fā)送的入群請(qǐng)求消息，則暫存該請(qǐng)求入群消息。

步驟3.1：判斷群首最新電池電量數(shù)值，比較電池電量與設(shè)定的閾值（假設(shè)=30%）并選擇不同的操作步驟。如果電池電量低于設(shè)定的閾值，則群首轉(zhuǎn)任申請(qǐng)消息由群首向管理者發(fā)送，如果新的接任群首已經(jīng)被指定，則轉(zhuǎn)入步驟3.1.3。

如果即將卸任的群首收到管理者發(fā)送的自主職能委托消息，則轉(zhuǎn)入步驟3.1.1；否則認(rèn)為群首目前電池電量充足，轉(zhuǎn)入步驟3.1.2。

步驟3.1.1：群首繼任者選擇通過多屬性拍賣方式進(jìn)行，群首向群成員節(jié)點(diǎn)廣播群首委托邀請(qǐng)信息，同時(shí)開啟計(jì)時(shí)器，等待群成員節(jié)點(diǎn)收到邀請(qǐng)消息后的反饋，即向群首發(fā)送響應(yīng)信息。

步驟3.1.2：如果群首的電池電量充足，具備能繼續(xù)擔(dān)任群首的條件，則轉(zhuǎn)入步驟4。

步驟3.1.3：如果管理者指定新群首，群首委托確認(rèn)消息由原群首發(fā)送至指定新群首，群首注銷請(qǐng)求消息也由原群首發(fā)送至管理者，目的是宣布自己不再擔(dān)任群首，同時(shí)釋放清空所存儲(chǔ)的群成員數(shù)組信息、本地線程和緩沖區(qū)中待處理新成員加入請(qǐng)求消息等，標(biāo)記自身狀態(tài)為群成員。

步驟3.2：若△>，表明群首已經(jīng)離群，注銷請(qǐng)求消息由群首發(fā)送至管理者，宣布自己不再是群首，同時(shí)釋放存儲(chǔ)的本地群成員數(shù)組信息、本地線程和緩沖區(qū)中待處理新成員加入請(qǐng)求消息等，此時(shí)標(biāo)記群首為獨(dú)立狀態(tài)。

步驟4：群首繼續(xù)執(zhí)行正常管理操作，首先判斷是否有群成員離開，依據(jù)時(shí)間差判斷，時(shí)間差的計(jì)算方式為計(jì)算△=當(dāng)前時(shí)間-群成員應(yīng)答時(shí)間數(shù)組值_cnt [ ]，如果時(shí)間差△大于初始設(shè)定的門限閾值，且△[ ]，則發(fā)生了節(jié)點(diǎn)離開事件，轉(zhuǎn)入步驟4.1；否則說明尚未發(fā)生節(jié)點(diǎn)離群事件，轉(zhuǎn)入步驟5。

步驟5：群首查看緩沖區(qū)中是否有新成員請(qǐng)求加入消息，如果沒有，則轉(zhuǎn)入步驟6，否則表明有新成員請(qǐng)求事件發(fā)生，此時(shí)判斷當(dāng)前群成員個(gè)數(shù)，如果個(gè)數(shù)達(dá)到群規(guī)模規(guī)定的最大閾值（假設(shè)每個(gè)群規(guī)模閾值為），表明群規(guī)模已經(jīng)達(dá)到規(guī)定的范圍，轉(zhuǎn)入步驟5.1，否則表明群還可以再容納新成員，轉(zhuǎn)入步驟5.2。

步驟5.1：將拒絕群成員加入消息反饋發(fā)送至待加入的節(jié)點(diǎn)，轉(zhuǎn)入步驟6。

步驟5.2：待加入的節(jié)點(diǎn)收到群成員加入響應(yīng)消息。啟動(dòng)等待計(jì)時(shí)器_cnt，如果在超時(shí)之前收到新成員加入確認(rèn)消息，則更新本地群成員相關(guān)數(shù)組信息和群個(gè)數(shù)，轉(zhuǎn)入步驟6；若超時(shí)仍未收到任何確認(rèn)消息，則執(zhí)行步驟6。

步驟6：群首向管理者發(fā)送新群成員加入更新消息，轉(zhuǎn)入步驟2，重復(fù)執(zhí)行群維護(hù)算法。

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

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

群成員維護(hù)算法的詳細(xì)步驟如下：

步驟1：離群計(jì)時(shí)器l_cnt由群成員開啟（計(jì)時(shí)器將群首發(fā)送群管理消息的周期時(shí)長(zhǎng)設(shè)定為初始值），通過計(jì)時(shí)器判斷自身與當(dāng)前所在的群的關(guān)系，即在群中還是已經(jīng)離群。與上一次相比，如果群首廣播的群管理請(qǐng)求消息，等待時(shí)長(zhǎng)越限，則轉(zhuǎn)入步驟3；否則判斷群成員是否已經(jīng)離群，轉(zhuǎn)入步驟2進(jìn)行判斷操作。

步驟2：群首進(jìn)行周期性廣播群管理請(qǐng)求消息，如果群成員收到廣播消息，則表明自己尚未離開原始群，群成員向群首發(fā)送群維護(hù)響應(yīng)消息，同時(shí)將l_cnt值更新，并轉(zhuǎn)入步驟1。

如果群成員收到群首委托請(qǐng)求消息，將自身各項(xiàng)資源狀態(tài)更新，并發(fā)送響應(yīng)消息至群首，轉(zhuǎn)入步驟1；如果群成員收到群首委托確認(rèn)消息，則宣布自己為群首，以群首身份執(zhí)行群管理工作。

步驟3：若l_cnt超出閾值，則群成員處于獨(dú)立狀態(tài)，此時(shí)該群成員查詢距離自身為一跳距離的鄰居節(jié)點(diǎn)的狀態(tài)，并進(jìn)行狀態(tài)判斷，如果這些節(jié)點(diǎn)也處于獨(dú)立的未分群狀態(tài)，既不是群首也不是群節(jié)點(diǎn)，則轉(zhuǎn)入步驟3.1，否則轉(zhuǎn)入步驟3.2。

步驟3.1：若存在未分群的一跳鄰居節(jié)點(diǎn)，說明當(dāng)前群脫離管理處于失控狀態(tài)，則所有不屬于某個(gè)群的獨(dú)立節(jié)點(diǎn)重新入群組群。

步驟3.2：查詢鄰居表中是否有群首存在，若群中沒有群首，則未分群的一跳鄰居節(jié)點(diǎn)自組成新的群；若存在群首，則孤立節(jié)點(diǎn)向群首發(fā)送新入群請(qǐng)求消息，并啟動(dòng)消息接收線程和計(jì)時(shí)器等待群首響應(yīng)，轉(zhuǎn)入步驟4。

步驟4：假設(shè)群首cluser同意某孤立群節(jié)點(diǎn)加入，當(dāng)群首收到第一個(gè)群節(jié)點(diǎn)反饋的加入響應(yīng)消息時(shí)，將該節(jié)點(diǎn)信息更新存儲(chǔ)至本地群節(jié)點(diǎn)信息數(shù)組中，并轉(zhuǎn)入步驟1。

若在規(guī)定時(shí)間內(nèi)請(qǐng)求入群的群成員收到群首的拒絕消息，則該群成員開啟線程計(jì)時(shí)器，繼續(xù)等待接收新消息；若已經(jīng)超時(shí)且未收到任何同意加入響應(yīng)消息，表明沒有任何群首同意該節(jié)點(diǎn)入群，此時(shí)該群節(jié)點(diǎn)繼續(xù)尋找新的距離自己最近的群并申請(qǐng)加入。

群成員開啟離群計(jì)時(shí)器l_cnt，設(shè)定離群計(jì)時(shí)器初始值為群首發(fā)送群維護(hù)消息的周期時(shí)長(zhǎng)，當(dāng)離群計(jì)時(shí)器的值超出計(jì)時(shí)器的計(jì)時(shí)上限值時(shí)，說明群成員自身已經(jīng)離群，無法接受群首管理，則群成員將自身狀態(tài)標(biāo)記為離群節(jié)點(diǎn)，進(jìn)行重新加入另外一個(gè)群的入群請(qǐng)求申請(qǐng)操作。

2.2算法核心解析

當(dāng)有新節(jié)點(diǎn)申請(qǐng)入群時(shí)，群首判斷群內(nèi)節(jié)點(diǎn)個(gè)數(shù)，如未達(dá)到所規(guī)定的群規(guī)模上限閾值，則同意該節(jié)點(diǎn)加入，同時(shí)更新群節(jié)點(diǎn)數(shù)組信息并上報(bào)管理者。

群首進(jìn)行群維護(hù)需要判斷是否離群，離群的群首不能繼續(xù)對(duì)群內(nèi)成員進(jìn)行管理。如果群首已經(jīng)離群，則立刻進(jìn)入未分群狀態(tài)，獲取其他群首的實(shí)時(shí)信息，設(shè)置自身狀態(tài)為新的群成員，同時(shí)向新群廣播群成員加入請(qǐng)求信息。

當(dāng)群首處于自身電量不足、高動(dòng)態(tài)及受到威脅攻擊不安全時(shí)，進(jìn)行職能委任或者宣布自己不再擔(dān)任群首。群首職責(zé)委托減少大規(guī)模網(wǎng)絡(luò)重構(gòu)所帶來的額外網(wǎng)絡(luò)流量，避免節(jié)點(diǎn)失控。另外算法實(shí)時(shí)性強(qiáng)，提升在高動(dòng)態(tài)環(huán)境下的管理時(shí)效性。

群首維護(hù)算法和群成員維護(hù)算法設(shè)計(jì)的核心思想在于以拍賣方式進(jìn)行，群首可以獲取實(shí)時(shí)的群成員資源信息狀況，以便選擇出能夠勝任群首職能的最優(yōu)繼任者，實(shí)時(shí)性較強(qiáng)；其二，相比較于直接選擇某個(gè)委任者而言，拍賣方式為群成員提供了公平的競(jìng)爭(zhēng)機(jī)會(huì)，最大程度考慮了負(fù)載平衡問題；最后，對(duì)群首即將轉(zhuǎn)任而進(jìn)行的拍賣方式，只需耗費(fèi)一輪競(jìng)拍交互的網(wǎng)絡(luò)流量，避免了大規(guī)模網(wǎng)絡(luò)重構(gòu)所導(dǎo)致的節(jié)點(diǎn)失控或脫離管理，大大提升管理效率。

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

在高動(dòng)態(tài)的典型應(yīng)用環(huán)境下，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化和網(wǎng)絡(luò)大規(guī)模重組的情形隨時(shí)可見，對(duì)網(wǎng)絡(luò)穩(wěn)定性和可靠性產(chǎn)生很大影響，同時(shí)給網(wǎng)絡(luò)管理帶來了極大的影響，導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)脫離管理。本文設(shè)計(jì)的群維護(hù)算法，從控制群規(guī)模和群數(shù)量的根本點(diǎn)出發(fā)進(jìn)行設(shè)計(jì)控制，一方面可以根據(jù)網(wǎng)絡(luò)規(guī)模，控制所劃分的管理群的個(gè)數(shù)和每個(gè)群的規(guī)模，另一方面在管理群和每個(gè)群設(shè)定好之后，可以通過設(shè)定群首、群成員的狀態(tài)，以及判斷每個(gè)群節(jié)點(diǎn)的位置、節(jié)點(diǎn)電量、節(jié)點(diǎn)與群的距離（以一跳為基準(zhǔn)距離）等自身屬性，進(jìn)而判斷節(jié)點(diǎn)是入群還是離群?jiǎn)栴}。通過上述2個(gè)設(shè)計(jì)點(diǎn)，解決了局部節(jié)點(diǎn)移動(dòng)或離群所引起的群結(jié)構(gòu)失效問題，同時(shí)能夠根據(jù)被管網(wǎng)絡(luò)的規(guī)模合理劃分管理群，群過多會(huì)造成管理信息的海量增加，群過少會(huì)導(dǎo)致入群離群的時(shí)效性問題，不僅有效控制網(wǎng)絡(luò)，同時(shí)也大大提高了管理時(shí)效性。

參考文獻(xiàn)

[1]薛明.基于SNMP局域網(wǎng)流量監(jiān)測(cè)系統(tǒng)的應(yīng)用研究[D].鄭州：鄭州大學(xué)，2006.

[2]李濤，張亞群，劉岱平.面向服務(wù)的校園網(wǎng)流量監(jiān)控系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2009（1）：154-156.

[3]宋進(jìn)紅，沈云琴.使用CactiEZ輕松構(gòu)建校園網(wǎng)絡(luò)流量監(jiān)控系統(tǒng)[J].河南城建學(xué)院學(xué)報(bào)，2009，18（4）：57-59.

[4]段宗濤，林莎.基于SNMP的網(wǎng)絡(luò)流量監(jiān)控系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用，2001（11）：25-27.

[5]董加敏，王斌.基于SNMP協(xié)議的高校網(wǎng)絡(luò)流量監(jiān)控管理系統(tǒng)的研究[J].廣州大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，8（1）：53-57.

[6]張彤，吳世榮.基于SNMP計(jì)算機(jī)網(wǎng)絡(luò)流量監(jiān)控系統(tǒng)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（1）：88-91.

[7]徐鶴，王汝傳.一種P2P流量監(jiān)控系統(tǒng)的設(shè)計(jì)及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（10）：6-10.

[8]趙英，黃九梅，董小國(guó)，等.網(wǎng)絡(luò)流量監(jiān)控系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2004（S1）：32-33.

[9]張衛(wèi)東，王偉，韓維桓.網(wǎng)絡(luò)流量測(cè)量與監(jiān)控系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（32）：160-163.