黃書(shū)強(qiáng) 張 震 周繼鵬

(1暨南大學(xué)網(wǎng)絡(luò)與教育技術(shù)中心，廣州 510632)

(2暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州 510632)

無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)聚類屬性分析

黃書(shū)強(qiáng)1張 震2周繼鵬2

(1暨南大學(xué)網(wǎng)絡(luò)與教育技術(shù)中心，廣州 510632)

(2暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州 510632)

通過(guò)分析無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)空間屬性，提出了一種改進(jìn)的k-medoids網(wǎng)絡(luò)節(jié)點(diǎn)聚類算法.該算法基于聚類思想，將無(wú)線Mesh網(wǎng)絡(luò)中的網(wǎng)關(guān)部署問(wèn)題轉(zhuǎn)化為空間節(jié)點(diǎn)數(shù)據(jù)聚類問(wèn)題.構(gòu)建了網(wǎng)絡(luò)拓?fù)鋱D的鄰接矩陣，并利用鄰接矩陣選擇具有最多一跳連接節(jié)點(diǎn)數(shù)的對(duì)象作為初始簇中心.然后以網(wǎng)絡(luò)跳數(shù)代替?zhèn)鹘y(tǒng)聚類算法中的距離參數(shù)，將最小化跳數(shù)之和作為優(yōu)化目標(biāo)，通過(guò)迭代方法獲得穩(wěn)定的聚類和分組結(jié)果.實(shí)驗(yàn)結(jié)果表明，離散的網(wǎng)絡(luò)節(jié)點(diǎn)在空間上具有聚類特性，利用該方法可以獲得更小的平均跳數(shù)和最大跳數(shù)，因此可以較好地實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)分組和網(wǎng)關(guān)發(fā)現(xiàn).

無(wú)線Mesh網(wǎng)絡(luò);聚類;網(wǎng)絡(luò)跳數(shù);k-medoids算法

無(wú)線Mesh網(wǎng)絡(luò)是一個(gè)網(wǎng)狀網(wǎng)結(jié)構(gòu)，其拓?fù)浣Y(jié)構(gòu)主要包含2種類型節(jié)點(diǎn):普通AP(access point)節(jié)點(diǎn)和無(wú)線網(wǎng)關(guān)(gateway)節(jié)點(diǎn).網(wǎng)關(guān)節(jié)點(diǎn)除了與AP節(jié)點(diǎn)一樣具有為移動(dòng)用戶提供網(wǎng)絡(luò)接入服務(wù)的功能外，還具有接入有線網(wǎng)(Internet)的功能;AP節(jié)點(diǎn)通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)連入Internet.在無(wú)線網(wǎng)狀網(wǎng)運(yùn)行的過(guò)程中，所有用戶都要最終通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)接入Internet.為了擴(kuò)大服務(wù)范圍，AP節(jié)點(diǎn)采用了多跳技術(shù)，即靠近網(wǎng)關(guān)節(jié)點(diǎn)的AP節(jié)點(diǎn)可以作為中繼點(diǎn)轉(zhuǎn)發(fā)遠(yuǎn)離網(wǎng)關(guān)節(jié)點(diǎn)的AP節(jié)點(diǎn)所產(chǎn)生的流量.因此，一個(gè)用戶通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)接入Internet時(shí)可能經(jīng)歷了一跳或多跳.在給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，為了提供更好的QoS服務(wù)，應(yīng)該盡可能使用戶以較小的跳數(shù)接入到有線網(wǎng)絡(luò)中，這就涉及到2個(gè)問(wèn)題:①如何部署網(wǎng)關(guān)位置;② 如何讓AP節(jié)點(diǎn)接入網(wǎng)關(guān)跳數(shù)最小.研究者從不同角度對(duì)這些問(wèn)題進(jìn)行了分析:文獻(xiàn)［1］提出了基于遞歸的貪婪算法，計(jì)算最少需要部署的網(wǎng)關(guān)數(shù)，完成網(wǎng)絡(luò)分簇;文獻(xiàn)［2］在文獻(xiàn)［1］的基礎(chǔ)上，將網(wǎng)關(guān)數(shù)和網(wǎng)絡(luò)跳數(shù)作為優(yōu)化目標(biāo)，對(duì)網(wǎng)絡(luò)進(jìn)行分割;文獻(xiàn)［3］研究了在給定網(wǎng)關(guān)位置的條件下，利用數(shù)學(xué)規(guī)劃方法給出基于直線和環(huán)的AP分簇算法;文獻(xiàn)［4］研究了基于概率發(fā)現(xiàn)的Ad-hoc網(wǎng)絡(luò)分簇方法，完成對(duì)拓?fù)浣Y(jié)構(gòu)的優(yōu)化;文獻(xiàn)［5］以最小化最大距離為目標(biāo)，研究了在給定集合節(jié)點(diǎn)中尋找多個(gè)幾何中心的方法;文獻(xiàn)［6］研究了以最小網(wǎng)關(guān)數(shù)、最小跳數(shù)和最小負(fù)載均衡指數(shù)為優(yōu)化目標(biāo)的網(wǎng)關(guān)部署問(wèn)題;文獻(xiàn)［7-8］討論了無(wú)線Mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)密度等因素對(duì)網(wǎng)關(guān)配置的影響.

本文通過(guò)分析無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)的空間屬性，發(fā)現(xiàn)其存在空間的聚類特性.基于此特性，提出利用數(shù)據(jù)聚類思想來(lái)解決網(wǎng)關(guān)部署問(wèn)題.

1 問(wèn)題描述及模型

本文從數(shù)據(jù)聚類的角度來(lái)考慮無(wú)線Mesh網(wǎng)絡(luò)網(wǎng)關(guān)部署問(wèn)題.給定一個(gè)由n個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)組成的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中需要部署的網(wǎng)關(guān)共m個(gè).如何選擇網(wǎng)關(guān)節(jié)點(diǎn)以使普通AP節(jié)點(diǎn)獲得較好的服務(wù)質(zhì)量，是一個(gè)難點(diǎn)問(wèn)題.

將最小跳數(shù)作為衡量網(wǎng)絡(luò)服務(wù)質(zhì)量的參數(shù)，給出如下的數(shù)學(xué)模型:用無(wú)向圖G=(V，E)來(lái)表示無(wú)線網(wǎng)狀網(wǎng)，其中V為所有頂點(diǎn)的集合，表示所有AP節(jié)點(diǎn)(包括潛在的網(wǎng)關(guān)節(jié)點(diǎn))，E為所有邊的集合，表示所有AP節(jié)點(diǎn)間的連通關(guān)系.AP節(jié)點(diǎn)之間是否能夠連通和通信，與節(jié)點(diǎn)之間的距離有關(guān).當(dāng)2個(gè)AP節(jié)點(diǎn)間的距離大于最佳通信距離時(shí)，這2個(gè)節(jié)點(diǎn)無(wú)法連通;反之，則可以連通.

AP節(jié)點(diǎn)之間的連通關(guān)系可用數(shù)學(xué)符號(hào)表示.?vi，vj∈V，設(shè)di，j為vi，vj間的距離，d為通信距離.用ei，j∈E來(lái)表示vi，vj間是否連通.若di，j≤d則連通，ei，j=1;否則，ei，j=0.

顯然，網(wǎng)關(guān)節(jié)點(diǎn)數(shù)目越多，提供的網(wǎng)絡(luò)接入服務(wù)的質(zhì)量越好.但由于部署網(wǎng)關(guān)節(jié)點(diǎn)需要額外費(fèi)用，部署的網(wǎng)關(guān)節(jié)點(diǎn)越多，花費(fèi)就越大，因此需要在給定的費(fèi)用約束下尋找一個(gè)最佳的網(wǎng)關(guān)節(jié)點(diǎn)部署方案，使得接入服務(wù)最佳.盡管多跳技術(shù)可以擴(kuò)大服務(wù)范圍，但同時(shí)也會(huì)造成信號(hào)干擾、流量衰減等影響，最終導(dǎo)致網(wǎng)絡(luò)服務(wù)質(zhì)量下降.為了獲得較好的服務(wù)質(zhì)量，各AP節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)間的最大跳數(shù)應(yīng)存在上限hmax，同時(shí)，定義所有AP節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)間的總跳數(shù)為htotal，并以此衡量整體服務(wù)質(zhì)量的好壞，最終目標(biāo)是最小化htotal.本問(wèn)題需要滿足的約束如下:

1)網(wǎng)關(guān)節(jié)點(diǎn)個(gè)數(shù)約束 記I={I1，I2，…，Im}為網(wǎng)關(guān)節(jié)點(diǎn)所組成的集合，A={a1，a2，…，an－m}為普通AP節(jié)點(diǎn)組成的集合.

2)網(wǎng)關(guān)節(jié)點(diǎn)吞吐量限制 一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)的吞吐量是存在上限的，因此接入的用戶數(shù)量不能過(guò)多，否則網(wǎng)關(guān)節(jié)點(diǎn)將無(wú)法處理所有請(qǐng)求.設(shè)網(wǎng)關(guān)節(jié)點(diǎn)Ii的吞吐量上限為CGW(i)，通過(guò)該網(wǎng)關(guān)節(jié)點(diǎn)接入Internet的AP節(jié)點(diǎn)所組成的集合為φ(i)，接入節(jié)點(diǎn)aj的所有用戶的總流量請(qǐng)求為Dj，則節(jié)點(diǎn)吞吐量約束可以表示為

j∑Dj≤CGW(i)，?Ii∈I.

∈φ(i)

3)AP節(jié)點(diǎn)吞吐量限制 與網(wǎng)關(guān)節(jié)點(diǎn)一樣，AP節(jié)點(diǎn)的吞吐量也存在上限，節(jié)點(diǎn)ai的吞吐量上限記為CAP(i).可將經(jīng)過(guò)節(jié)點(diǎn)ai的流量分為2個(gè)部分:①通過(guò)ai接入無(wú)線網(wǎng)狀網(wǎng)的用戶所產(chǎn)生的流量，記為本地流量tl(i)=Di;② 其他AP節(jié)點(diǎn)通過(guò)ai轉(zhuǎn)發(fā)的流量.將與ai一跳相連且通過(guò)ai向網(wǎng)關(guān)節(jié)點(diǎn)傳遞流量的所有AP節(jié)點(diǎn)的集合記為ψ(i)，經(jīng)過(guò)節(jié)點(diǎn)ai的所有流量為tt(i).假設(shè)1個(gè)AP節(jié)點(diǎn)只能通過(guò)1條路徑與網(wǎng)關(guān)相連，則此約束可表示為

4)最大跳數(shù)約束 ?Ii∈I，aj是通過(guò)Ii連入Internet的一個(gè)節(jié)點(diǎn)，即aj∈φ(i).設(shè)Ii與aj間的跳數(shù)為hi，j，最大跳數(shù)限制為hmax，則hi，j≤hmax，?Ii∈I，aj∈φ(i).

5)AP節(jié)點(diǎn)路徑約束 1個(gè)AP節(jié)點(diǎn)只能與1個(gè)網(wǎng)關(guān)節(jié)點(diǎn)相連.此外，假設(shè)網(wǎng)關(guān)節(jié)點(diǎn)的有線鏈路容量相對(duì)于無(wú)線鏈路容量是無(wú)限大的.

由此便可得到如下數(shù)學(xué)優(yōu)化模型:

對(duì)于任意vi∈V，用0-1變量εi來(lái)表示vi是否被選為網(wǎng)關(guān).εi的定義如下:

此外，對(duì)于任意的Ii∈I和aj∈A，定義0-1變量 ωi，j.如果aj經(jīng)由Ii連入有線網(wǎng)，則 ωi，j=1;如果aj經(jīng)由其他網(wǎng)關(guān)連入有線網(wǎng)，則 ωi，j=0.對(duì)于Ai，Aj∈A，同樣定義 ωi，j=0.

如果假定所有的網(wǎng)關(guān)節(jié)點(diǎn)具有相同性能，所有的AP節(jié)點(diǎn)也具有相同性能，則CAP(j)=CAP，?Ii∈I，記CGW(i)=CGW.

2 算法描述

與傳統(tǒng)的聚類算法相比，標(biāo)準(zhǔn)k-medoids算法能夠克服孤立點(diǎn)數(shù)據(jù)的影響，具有較好的聚類效果［9-10］.在網(wǎng)絡(luò)節(jié)點(diǎn)聚類中，必須考慮節(jié)點(diǎn)間的連通關(guān)系，因此該算法不能直接應(yīng)用于無(wú)線Mesh網(wǎng)絡(luò).為了解決無(wú)線Mesh網(wǎng)絡(luò)網(wǎng)關(guān)選擇的問(wèn)題，本文提出了一種改進(jìn)的k-medoids網(wǎng)關(guān)節(jié)點(diǎn)選擇算法.

標(biāo)準(zhǔn)k-medoids算法的優(yōu)化目標(biāo)是使所有節(jié)點(diǎn)到簇中心距離和最小，可數(shù)學(xué)描述為

式中，s為原始劃分空間中的數(shù)據(jù)集合，即給定節(jié)點(diǎn)數(shù)據(jù)對(duì)象;Ci為簇中心節(jié)點(diǎn)集合;oi為簇Ci中的數(shù)據(jù)對(duì)象集合.

算法1 改進(jìn)的k-medoids節(jié)點(diǎn)聚類算法

輸入:拓?fù)浣Y(jié)構(gòu)圖和網(wǎng)關(guān)數(shù)m.

輸出:網(wǎng)關(guān)位置和節(jié)點(diǎn)分組.

①構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D的鄰接矩陣，利用鄰接矩陣，將一跳范圍內(nèi)連接節(jié)點(diǎn)數(shù)最多的對(duì)象作為初始簇中心;

②剔除已選擇的節(jié)點(diǎn)，重復(fù)步驟①，直到完成對(duì)m個(gè)簇中心的選擇;

③將m個(gè)簇中心作為網(wǎng)關(guān)，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)與中心的最小跳數(shù)距離，依次將網(wǎng)絡(luò)節(jié)點(diǎn)分配給最近的網(wǎng)關(guān)，直到所有節(jié)點(diǎn)都分配給某一網(wǎng)關(guān);

④重新計(jì)算每個(gè)簇的中心，即簇內(nèi)到其他所有節(jié)點(diǎn)跳數(shù)距離之和最小的節(jié)點(diǎn);

⑤重新聚類，直到簇的中心不發(fā)生變化;

⑥以最小跳數(shù)為指標(biāo)，將節(jié)點(diǎn)依次加入m個(gè)最終確定的簇中心;

⑦得到聚類結(jié)果，即網(wǎng)關(guān)位置和每個(gè)網(wǎng)關(guān)負(fù)責(zé)的分組節(jié)點(diǎn).

2.1 初始簇中心的選擇方法

為了獲得較好的初始簇中心，首先根據(jù)網(wǎng)絡(luò)拓?fù)鋱D構(gòu)建對(duì)應(yīng)的鄰接矩陣，依次搜索出在一跳范圍內(nèi)連接節(jié)點(diǎn)數(shù)目最多的節(jié)點(diǎn)，并將其作為網(wǎng)關(guān)節(jié)點(diǎn);待全部網(wǎng)關(guān)節(jié)點(diǎn)選定后，采用廣度優(yōu)先搜索的方法，將網(wǎng)絡(luò)節(jié)點(diǎn)依次加入到距離最近的網(wǎng)關(guān)，直到所有AP節(jié)點(diǎn)都加入某網(wǎng)關(guān)節(jié)點(diǎn)為止.

選擇初始簇中心的詳細(xì)步驟如下:

①計(jì)算所有n個(gè)節(jié)點(diǎn)的鄰接矩陣Mn×n，且ki，j∈Mn×n.如果節(jié)點(diǎn)vi與vj間的距離小于最佳通信距離(即di，j≤d)，則在鄰接矩陣 Ma中ki，j=1;否則，ki，j=0.在鄰接矩陣 Ma中，將各行之和構(gòu)成的向量記為行和向量pn×1，則pi表示節(jié)點(diǎn)vi通過(guò)一跳可以到達(dá)的節(jié)點(diǎn)的數(shù)目.

②將pn×1中最大元素的行下標(biāo)所表示的節(jié)點(diǎn)作為第1個(gè)網(wǎng)關(guān)節(jié)點(diǎn)I1，并將所有與I1在一跳內(nèi)相連的AP節(jié)點(diǎn)加入I1中，假設(shè)這些AP節(jié)點(diǎn)的數(shù)目為m1，由其組成的集合為 φ(1).重新計(jì)算p(n－m1)×1，I1和加入I1中的 AP 節(jié)點(diǎn)將不再計(jì)入剩余節(jié)點(diǎn)一跳可以連接節(jié)點(diǎn)的范圍內(nèi).將新的pn×1中最大元素的行下標(biāo)所表示的節(jié)點(diǎn)作為第2個(gè)網(wǎng)關(guān)節(jié)點(diǎn)I2，并將V－φ(1)中所有與I2在一跳內(nèi)相連的AP節(jié)點(diǎn)加入I2中，假設(shè)這些AP節(jié)點(diǎn)的數(shù)目為m2，由其組成的集合為φ(2).以此類推，得到m個(gè)網(wǎng)關(guān)節(jié)點(diǎn)I1，I2，…，Im.在此過(guò)程中，將所有與各網(wǎng)關(guān)節(jié)點(diǎn)距離為一跳的AP節(jié)點(diǎn)加入到相應(yīng)的網(wǎng)關(guān)節(jié)點(diǎn)分組中.

2.2 新的簇中心計(jì)算方法

將m個(gè)網(wǎng)關(guān)節(jié)點(diǎn)作為聚類中心點(diǎn)，保持節(jié)點(diǎn)網(wǎng)絡(luò)連接特性的同時(shí)，將最小跳數(shù)作為距離參數(shù)，依次將節(jié)點(diǎn)加入到這m個(gè)網(wǎng)關(guān)節(jié)點(diǎn)中.按照I1，I2，…，Im的順序依次給各網(wǎng)關(guān)節(jié)點(diǎn)加入AP節(jié)點(diǎn)，且每次給每個(gè)網(wǎng)關(guān)加入一個(gè)AP節(jié)點(diǎn).如果節(jié)點(diǎn)同時(shí)與多個(gè)網(wǎng)關(guān)的跳數(shù)距離相等，則計(jì)算每個(gè)網(wǎng)關(guān)當(dāng)前擁有的節(jié)點(diǎn)數(shù)，并將該節(jié)點(diǎn)加入到當(dāng)前擁有節(jié)點(diǎn)數(shù)最少的網(wǎng)關(guān)節(jié)點(diǎn)中.以此類推，直到所有節(jié)點(diǎn)都被加入某個(gè)網(wǎng)關(guān)節(jié)點(diǎn)分組中.將簇范圍內(nèi)到其他所有節(jié)點(diǎn)的跳數(shù)距離之和最小的節(jié)點(diǎn)作為新的中心.重復(fù)上面步驟，直到m個(gè)簇中心不發(fā)生變化為止.

3 實(shí)驗(yàn)分析

圖1所示為一個(gè)無(wú)線Mesh網(wǎng)絡(luò)隨機(jī)拓?fù)浣Y(jié)構(gòu)實(shí)例，該拓?fù)浣Y(jié)構(gòu)中共包含100個(gè)網(wǎng)絡(luò)節(jié)點(diǎn).要求在這些節(jié)點(diǎn)中選擇10個(gè)節(jié)點(diǎn)作為網(wǎng)關(guān)節(jié)點(diǎn)，負(fù)責(zé)其他節(jié)點(diǎn)與有線網(wǎng)絡(luò)的通信.根據(jù)本文算法，首先利用拓?fù)鋱D的鄰接矩陣，選擇m個(gè)初始網(wǎng)關(guān)中心;然后根據(jù)網(wǎng)絡(luò)跳數(shù)將節(jié)點(diǎn)依次加入到附近的網(wǎng)關(guān)節(jié)點(diǎn)中.

圖1 無(wú)線Mesh網(wǎng)絡(luò)隨機(jī)拓?fù)浣Y(jié)構(gòu)實(shí)例

由圖1(c)可知，所有AP節(jié)點(diǎn)都已加入某一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)中.此時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)到網(wǎng)關(guān)的平均跳數(shù)為1.79，最大跳數(shù)為4.

下面通過(guò)仿真實(shí)驗(yàn)對(duì)本文算法進(jìn)行評(píng)價(jià).利用Matlab軟件隨機(jī)生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，取100次實(shí)驗(yàn)的平均結(jié)果作為最終結(jié)果.為了衡量和對(duì)比算法聚類效果，引入平均跳數(shù)和最大跳數(shù)2個(gè)評(píng)價(jià)指標(biāo).當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為100時(shí)，運(yùn)用聚類算法前后網(wǎng)關(guān)節(jié)點(diǎn)個(gè)數(shù)與平均跳數(shù)、最大跳數(shù)的關(guān)系見(jiàn)圖2.當(dāng)網(wǎng)關(guān)數(shù)為10時(shí)，運(yùn)用聚類算法前后網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)與平均跳數(shù)、最大跳數(shù)的關(guān)系見(jiàn)圖3.

圖2 改變網(wǎng)關(guān)數(shù)的實(shí)驗(yàn)結(jié)果對(duì)比

圖3 改變網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的實(shí)驗(yàn)結(jié)果對(duì)比

由圖2和圖3可知，當(dāng)AP節(jié)點(diǎn)數(shù)一定時(shí)，網(wǎng)關(guān)節(jié)點(diǎn)數(shù)越多，平均跳數(shù)和最大跳數(shù)越小;當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)數(shù)一定時(shí)，AP節(jié)點(diǎn)數(shù)越多，平均跳數(shù)越大，最大跳數(shù)也越大.本文算法可以獲得較小的平均跳數(shù)和最大跳數(shù)，從而較好地實(shí)現(xiàn)節(jié)點(diǎn)聚類和分組.節(jié)點(diǎn)通過(guò)較小跳數(shù)接入有線網(wǎng)絡(luò)，可以大幅減少網(wǎng)絡(luò)延時(shí)，保障網(wǎng)絡(luò)服務(wù)質(zhì)量.

4 結(jié)語(yǔ)

網(wǎng)絡(luò)節(jié)點(diǎn)在空間上具有聚類屬性.本文將聚類算法引入到無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)聚類中，以解決網(wǎng)關(guān)選擇和部署問(wèn)題.在研究無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)聚類時(shí)，應(yīng)考慮到節(jié)點(diǎn)之間的連通關(guān)系.本文以最小網(wǎng)絡(luò)跳數(shù)代替節(jié)點(diǎn)間的距離，取得了較好的效果.盡管最小跳數(shù)是衡量網(wǎng)絡(luò)質(zhì)量的重要參數(shù)之一，但是應(yīng)該同時(shí)兼顧其他網(wǎng)絡(luò)參數(shù)指標(biāo)，這是下一步需要解決的問(wèn)題.

［1］ Bassam Aoun.Topology optimization in wireless mesh networks［D］.Ontario，Canada:University of Waterloo，2006.

［2］He B，Xie B，Agrawal D P.Optimizing deployment of Internet gateway in wireless mesh networks［J］.Computer Communications，2008，31(7):1259-1275.

［3］ Zhang Yan，Luo Jijun，Hu Honglin.Wireless mesh networking:architectures，protocols and standards［M］.New York，USA:Auerbach Publications，2008.

［4］ Jason L C，Jose E R.Optimal design of cluster-based ad-hoc networks using probabilistic solution discovery［J］.Reliability Engineering＆System Safety，2009，94(2):218-228.

［5］ Durocher S，Jampani K R，Lubiwb A，et al.Modelling gateway placement in wireless networks:geometrickcenters of unit disc graphs［J］.Computational Geometry，2011，44(6):286-302.

［6］黃書(shū)強(qiáng)，周繼鵬.基于聚類的無(wú)線Mesh網(wǎng)絡(luò)網(wǎng)關(guān)選擇及AP分組算法［J］.華南理工大學(xué)學(xué)報(bào)，2011，39(4):38-43.Huang Shuqiang，Zhou Jipeng.Wireless mesh gateway selecting and AP clustering algorithm based on clustering［J］.Journal of South China University of Technology，2011，39(4):38-43.(in Chinese)

［7］ Ekram Hossain，Kin Leung.Wireless mesh networks architectures and protocols［M］.New York，USA:Springer，2008.

［8］ Robinson J，Knightly E W.A performance study of deployment factors in wireless mesh networks［C］//The26th IEEE International Conference on Computer Communications.Alaska，USA，2007:2054-2062.

［9］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京:中國(guó)水利水電出版社，2003.

［10］鄧松，李文敬，劉海濤.數(shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典［M］.北京:電子工業(yè)出版社，2009.

Clustering attribute analysis on nodes of wireless Mesh networks

Huang Shuqiang1Zhang Zhen2Zhou Jipeng2

(1Network and Education Technology Center，Jinan University，Guangzhou 510632，China)(2College of Information Science and Technology，Jinan University，Guangzhou 510632，China)

By analyzing the spatial attribute of nodes of wireless Mesh networks，an improvedk-medoids clustering algorithm is proposed.Based on clustering，the algorithm converts the problem of gateway deployment of wireless mesh network into a data clustering problem.In the algorithm，an adjacency matrix of network topology is built and the nodes with most a hop connected nodes are gradually selected as initial cluster centers.Then，the distance parameter between the nodes in the traditional clustering algorithm is replaced by the hop of network.And the optimization object is abstracted as minimizing the sum hops of the network.The nodes are added into different clusters and the last stable clustering and grouping results are obtained by iterative way.The experimental results show that the discrete network nodes have a property of clustering in space.The average hops of networks and the maximum hops of network become smaller by using the proposed algorithm，which can realize reasonable clustering of the network nodes and gateway discovering.

wireless Mesh networks;clustering;hop of network;k-medoids algorithm

TP393

A

1001－0505(2012)02-0219-05

10.3969/j.issn.1001 －0505.2012.02.005

2011-09-30.

黃書(shū)強(qiáng)(1977—)，男，博士，高級(jí)工程師，hsq2008@vip.sina.com.

廣東省自然科學(xué)基金資助項(xiàng)目(S2011040003481，S2011010001525)、廣東省高校優(yōu)秀青年創(chuàng)新人才培養(yǎng)計(jì)劃資助項(xiàng)目(LYM09029)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(21611522).

黃書(shū)強(qiáng)，張震，周繼鵬.無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)聚類屬性分析［J］.東南大學(xué)學(xué)報(bào):自然科學(xué)版，2012，42(2):219-223.［doi:10.3969/j.issn.1001 －0505.2012.02.005］