從網(wǎng)絡(luò)安全的角度出發(fā)提出了一種新的群頭選擇算法，并結(jié)合相應(yīng)的負(fù)載平衡措施改善該算法的性能。該算法以圖論為理論背景，使用Kruskal算法求出無線Ad hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最小生成樹，在最小生成樹上生成群，確保群內(nèi)結(jié)點(diǎn)間通訊的代價(jià)保持在一個(gè)較低的水平。該算法采取的負(fù)載平衡措施最大限度地延長了群頭的生命周期，并可在新老群頭交替時(shí)保持整個(gè)網(wǎng)絡(luò)的穩(wěn)定性。
關(guān) 鍵 詞 群頭; 選擇算法; 無線Ad hoc網(wǎng)絡(luò)

由于移動(dòng)自組網(wǎng)具有動(dòng)態(tài)的拓?fù)洹⒂邢薜膸捈半姵?a target='_blank' class='arckwlink_none'>供電等諸多特性，導(dǎo)致路由在節(jié)點(diǎn)數(shù)目增多時(shí)開銷增大，擴(kuò)展性較差。分群是解決Ad hoc網(wǎng)絡(luò)可擴(kuò)展性的有效方法，如構(gòu)建一個(gè)無線中樞結(jié)
構(gòu)[1-3]，現(xiàn)有的分群算法分為兩類：(1) 指定或計(jì)算節(jié)點(diǎn)的權(quán)值，根據(jù)權(quán)值的大小確立群頭地位，具體的原則包括最小ID (Min ID)[4]、最大度(Max Dgr)[5]、最大能量[6]、最大穩(wěn)定度[7]等；(2) 隨機(jī)策略，所有節(jié)點(diǎn)公平競(jìng)爭(zhēng)群頭地位，如隨機(jī)競(jìng)爭(zhēng)[8]、基于支配集求解[9]等。
許多分群算法都有分群數(shù)目過多、群間重疊、分群效率低的問題。基于節(jié)點(diǎn)權(quán)值的分群算法中，任何在一跳范圍內(nèi)權(quán)值最大的節(jié)點(diǎn)都可以成為群頭，群間重疊多，相鄰群之間存在大量公共節(jié)點(diǎn)，重復(fù)的信息傳遞浪費(fèi)了網(wǎng)絡(luò)資源，每個(gè)節(jié)點(diǎn)在決定自己的身份之前需要等待相鄰的具有更大權(quán)值的節(jié)點(diǎn)做決定，造成了分群過程的慢收斂[8]；采用隨機(jī)策略，若允許群重疊，公共節(jié)點(diǎn)也可能很多；若不允許重疊，則可能會(huì)出現(xiàn)大量包含很少節(jié)點(diǎn)的群。
本文從網(wǎng)絡(luò)安全的角度提出了一種新的群頭選擇算法，并結(jié)合相應(yīng)的負(fù)載平衡措施來改善該算法的性能，確保群內(nèi)節(jié)點(diǎn)間通信的代價(jià)保持在一個(gè)較低的水平。該算法采取的負(fù)載平衡措施可最大限度地延長群頭的生命周期，并在新老群頭交替時(shí)保持整個(gè)網(wǎng)絡(luò)的穩(wěn)定性。