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

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

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

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

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

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

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

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

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

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

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

1 問題描述及模型

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

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

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

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

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

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

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

∈φ(i)

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

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

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

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

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

此外，對于任意的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.對于Ai，Aj∈A，同樣定義 ωi，j=0.

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

2 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 初始簇中心的選擇方法

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

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

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

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

2.2 新的簇中心計算方法

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

3 實驗分析

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

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

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

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

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

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

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

4 結(jié)語

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

［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］黃書強(qiáng)，周繼鵬.基于聚類的無線Mesh網(wǎng)絡(luò)網(wǎng)關(guān)選擇及AP分組算法［J］.華南理工大學(xué)學(xué)報，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］.北京:中國水利水電出版社，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.

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

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

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