蔡瑋 何鳳軍 王宇

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

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

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

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)生極大影響。由于群首在執(zhí)行群成員維護(hù)、任務(wù)分配、數(shù)據(jù)采集等管理功能的同時(shí)，還需要執(zhí)行基于群的路由轉(zhuǎn)發(fā)、移動(dòng)性管理、資源分配和信道接入等功能，負(fù)載較重，容易形成網(wǎng)絡(luò)瓶頸，因此群首的選取、委任將直接影響高動(dòng)態(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ù)分配的需要，必須實(shí)時(shí)維護(hù)各個(gè)群首及其群成員列表。

1群首委任算法

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)致群成員與群首之間的聯(lián)通關(guān)系可能會(huì)頻繁變化。需要研究當(dāng)群首位置發(fā)生變動(dòng)或由于自身電量等問題而無法承擔(dān)管理職能時(shí)，該群首需將管理職能委托給具有充足的能量資源、位置穩(wěn)定的群成員，從而維護(hù)管理分群的穩(wěn)定[1-3]。

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

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

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

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

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

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

1.2基于拍賣方式的群首維護(hù)算法

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

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

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

1.3分群場(chǎng)景下的群首委任算法

在分群場(chǎng)景中，群首委任機(jī)制如下：

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

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

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

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

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

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

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

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

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

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

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

2算法核心解析

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

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

3結(jié)束語

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

參考文獻(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]趙英，黃九梅，董小國，等.網(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（32）：160-163.