蔡瑋 何鳳軍 王宇

摘要：針對網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化下的群首選舉問題，研究分群以及群首委托典型場景下的群首選舉算法，設(shè)計管理者-群首/群首-群成員之間進行群首自主選擇、管理者委任群首、群首自動卸任與注銷，以及群首職能拍賣與委托過程期間的步驟流程與交互協(xié)議，研究基于多屬性的節(jié)點綜合評判值，采用單輪多屬性拍賣方式進行群首的委任，以及在動態(tài)分群中的群首委任/卸任流程，實現(xiàn)群管理的快速性和穩(wěn)定性。

關(guān)鍵詞：群首委任；職能委托；單輪多屬性拍賣；分群場景

中圖分類號：TP393文獻標(biāo)志碼：A文章編號：1008-1739（2021）02-53-3

0引言

在特殊應(yīng)用環(huán)境下，節(jié)點移動性較強，導(dǎo)致網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化，因而分群結(jié)構(gòu)頻繁變動，對網(wǎng)絡(luò)運行性能和管理效率產(chǎn)生極大影響。由于群首在執(zhí)行群成員維護、任務(wù)分配、數(shù)據(jù)采集等管理功能的同時，還需要執(zhí)行基于群的路由轉(zhuǎn)發(fā)、移動性管理、資源分配和信道接入等功能，負(fù)載較重，容易形成網(wǎng)絡(luò)瓶頸，因此群首的選取、委任將直接影響高動態(tài)網(wǎng)絡(luò)的性能。

在分層網(wǎng)絡(luò)中，為減少大規(guī)模分群開銷，網(wǎng)絡(luò)管理分群沿用網(wǎng)絡(luò)層的通信分群。但是由于網(wǎng)絡(luò)拓?fù)渥兓杆?，?dāng)通信分群重構(gòu)后，管理群的群首以及群成員也相應(yīng)發(fā)生改變。管理者為了網(wǎng)絡(luò)管理和作戰(zhàn)任務(wù)分配的需要，必須實時維護各個群首及其群成員列表。

1群首委任算法

1.1算法消息格式

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

在群結(jié)構(gòu)中，節(jié)點有未分群、群首和群成員3種狀態(tài)。在網(wǎng)絡(luò)拓?fù)涑跏蓟瘯r節(jié)點處于未分群狀態(tài)，管理分群或拓?fù)浞秩汉?，?jié)點的狀態(tài)由未分群成為群首或群成員，此后進入拓?fù)浠蛉壕S護狀態(tài)。在群維護中[4-5]，如果群首或群成員離群，則節(jié)點的狀態(tài)會發(fā)生改變，在未分群、群首和群成員之間切換。

算法中使用的消息格式定義如下：

①群首轉(zhuǎn)任請求消息：

該消息由群首生成，用于向管理者申請群首卸任，并委托給其他群成員。

②群首轉(zhuǎn)任響應(yīng)消息：

該消息由管理者生成，用于向群首通知自行進行群首委托或者指定群首ID，默認(rèn)自行委托則標(biāo)識為0。

1.2基于拍賣方式的群首維護算法

群首在群成員中選擇一個最優(yōu)的群成員作為群首的繼任者。原群首將職能委托處理結(jié)果上報給管理員，并向繼任者轉(zhuǎn)移群首職能內(nèi)容（更新群成員列表、采集群內(nèi)任務(wù)執(zhí)行結(jié)果等）后，標(biāo)志著本次多屬性拍賣結(jié)束。

采用拍賣方式進行群首職能的委托，主要出于下述考慮：①以拍賣方式進行，群首可以獲取實時的群成員的資源信息狀況，以便選擇出能夠勝任群首職能的最優(yōu)的繼任者，實時性較強；②相比較于直接選擇某個委任者而言，拍賣方式為群成員提供了公平的競爭機會，最大程度考慮了負(fù)載平衡問題；③對群首即將轉(zhuǎn)任而進行的拍賣方式，只需耗費一輪競拍交互的網(wǎng)絡(luò)流量，避免了大規(guī)模重新分群所導(dǎo)致的群重構(gòu)代價，明顯加快群結(jié)構(gòu)維護的反應(yīng)效率。

以一個包含若干節(jié)點的動態(tài)變化網(wǎng)絡(luò)為例，其網(wǎng)絡(luò)初始拓?fù)淙鐖D1所示，節(jié)點1和節(jié)點2為2個群的群首。圖2為節(jié)點1和節(jié)點2失效進行拍賣后，委任群首為節(jié)點6和節(jié)點7。

1.3分群場景下的群首委任算法

在分群場景中，群首委任機制如下：

步驟1：在分布式的群首選舉之前，管理者指定有指揮權(quán)的節(jié)點作為群首。管理者廣播群首委任請求消息，相應(yīng)節(jié)點接收到該消息后，判斷自身是否有指揮權(quán)。如果有指揮權(quán)的話，則該節(jié)點成為群首并向管理者發(fā)送群首委任確認(rèn)消息。

步驟2：管理者指定指揮權(quán)高的節(jié)點成為群首并邀請群成員加入后，對于剩下的未分群節(jié)點，如果其值是周圍鄰居節(jié)點的最小值，則該節(jié)點宣布自己成為群首并邀請群成員加入。分群完成后，新群首向管理者發(fā)送新群首注冊消息，向管理者報告群首及該群成員的信息。管理者收到該消息后，返回新群首注冊響應(yīng)消息[8-9]。

群首委托場景中，群首委任機制的詳細(xì)步驟如下：

①通信群首由于電量限制等原因需要進行群首職能轉(zhuǎn)任，向管理者發(fā)起群首轉(zhuǎn)任請求消息。

②管理者確認(rèn)該申請合法，回復(fù)群首轉(zhuǎn)任響應(yīng)消息：由群首自行委托轉(zhuǎn)任或者直接在該群中指定某個群成員。

③群首向群成員拍賣廣播/定向發(fā)送群首委托邀請信息。

④群成員回復(fù)群首委托響應(yīng)信息。

⑤委任后的群首向群成員發(fā)送群首委托確認(rèn)消息，該消息除了包含確認(rèn)群首職能轉(zhuǎn)換功能，還包含群首相關(guān)信息（如該群群成員信息列表，當(dāng)前群任務(wù)執(zhí)行進度和分派信息等）等，執(zhí)行職能和任務(wù)管理權(quán)限的全權(quán)轉(zhuǎn)移。

⑥原群首向管理者發(fā)起群首注銷申請。至此，該群首作為群首的職能轉(zhuǎn)接結(jié)束，自身轉(zhuǎn)移到離群/群成員狀態(tài)。

⑦群成員收到⑤中的消息后，轉(zhuǎn)自身狀態(tài)為群首，作為新群首向網(wǎng)絡(luò)管理者發(fā)起新群首注冊信息。此后將執(zhí)行群首職能，繼續(xù)完成群內(nèi)的任務(wù)執(zhí)行和管理。

群首維護算法流程如圖3所示。重新分群后的拓?fù)鋱D群首委任如圖4所示。

2算法核心解析

在分層網(wǎng)絡(luò)中，由于群首擔(dān)任群成員管理與維護、群內(nèi)/群間信息的路由轉(zhuǎn)發(fā)、接收上層管理者的指揮指令并分配給群成員、將群成員任務(wù)執(zhí)行結(jié)果上報等重要功能，因此群首的選擇、委任和卸任，以及群首功能的委托也影響了分層群結(jié)構(gòu)的變化。本文所提出的群首委任機制針對分群以及群首委托等不同的網(wǎng)絡(luò)場景，設(shè)計管理者-群首/群首-群成員之間進行群首自主選擇、管理者委任群首、群首自動卸任與注銷以及群首職能拍賣與委托過程間的步驟流程與交互協(xié)議。通過有效的群首委任機制，動態(tài)、實時維護分級的網(wǎng)絡(luò)管理架構(gòu)，加強網(wǎng)絡(luò)管理與維護的靈活性。

由于群首處理能力變化、電量限制、安全能力限制及隸屬關(guān)系變化等原因?qū)⑷菏茁毮芪薪o合適的群成員。群首以英式拍賣的方式向群成員拍賣該群首職能，避免了大規(guī)模重新分群所導(dǎo)致的群重構(gòu)代價，明顯提高群結(jié)構(gòu)維護的反應(yīng)效率。

3結(jié)束語

動態(tài)網(wǎng)絡(luò)的頻繁變動給運維管理帶來了管理困難，體現(xiàn)在拓?fù)浣Y(jié)構(gòu)的動態(tài)變化，因此如何在拓?fù)鋭討B(tài)變化的情況下（包括節(jié)點被摧毀、節(jié)點移動等導(dǎo)致的拓?fù)渥兓┱瓶厝滞負(fù)涫鞘滓鉀Q的問題；其次，對于群首而言，它是本群的管理中心，管理層級和地位僅次于管理中心，擔(dān)負(fù)著本群的所有管理工作，由于群首負(fù)載較重，因此電量不足、移動性等原因?qū)е氯菏鬃儎拥耐瑫r，也影響了分層群結(jié)構(gòu)的變化。本文提出了分群和群首委任典型場景下的基于單輪多屬性拍賣的群首拍賣、群首委任和卸任算法流程，從而維護整個分級網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定和完整，增強了動態(tài)網(wǎng)絡(luò)的可靠性和抗毀性。

參考文獻

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

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

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

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

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

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

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

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

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