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

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