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

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