无线Mesh网络节点聚类属性分析

黄书强 张 震 周继鹏

(1暨南大学网络与教育技术中心，广州 510632)

(2暨南大学信息科学技术学院，广州 510632)

无线Mesh网络节点聚类属性分析

黄书强1张 震2周继鹏2

(1暨南大学网络与教育技术中心，广州 510632)

(2暨南大学信息科学技术学院，广州 510632)

通过分析无线Mesh网络节点空间属性，提出了一种改进的k-medoids网络节点聚类算法.该算法基于聚类思想，将无线Mesh网络中的网关部署问题转化为空间节点数据聚类问题.构建了网络拓扑图的邻接矩阵，并利用邻接矩阵选择具有最多一跳连接节点数的对象作为初始簇中心.然后以网络跳数代替传统聚类算法中的距离参数，将最小化跳数之和作为优化目标，通过迭代方法获得稳定的聚类和分组结果.实验结果表明，离散的网络节点在空间上具有聚类特性，利用该方法可以获得更小的平均跳数和最大跳数，因此可以较好地实现网络节点分组和网关发现.

无线Mesh网络;聚类;网络跳数;k-medoids算法

无线Mesh网络是一个网状网结构，其拓扑结构主要包含2种类型节点:普通AP(access point)节点和无线网关(gateway)节点.网关节点除了与AP节点一样具有为移动用户提供网络接入服务的功能外，还具有接入有线网(Internet)的功能;AP节点通过网关节点连入Internet.在无线网状网运行的过程中，所有用户都要最终通过网关节点接入Internet.为了扩大服务范围，AP节点采用了多跳技术，即靠近网关节点的AP节点可以作为中继点转发远离网关节点的AP节点所产生的流量.因此，一个用户通过网关节点接入Internet时可能经历了一跳或多跳.在给定的网络拓扑结构中，为了提供更好的QoS服务，应该尽可能使用户以较小的跳数接入到有线网络中，这就涉及到2个问题:①如何部署网关位置;② 如何让AP节点接入网关跳数最小.研究者从不同角度对这些问题进行了分析:文献［1］提出了基于递归的贪婪算法，计算最少需要部署的网关数，完成网络分簇;文献［2］在文献［1］的基础上，将网关数和网络跳数作为优化目标，对网络进行分割;文献［3］研究了在给定网关位置的条件下，利用数学规划方法给出基于直线和环的AP分簇算法;文献［4］研究了基于概率发现的Ad-hoc网络分簇方法，完成对拓扑结构的优化;文献［5］以最小化最大距离为目标，研究了在给定集合节点中寻找多个几何中心的方法;文献［6］研究了以最小网关数、最小跳数和最小负载均衡指数为优化目标的网关部署问题;文献［7-8］讨论了无线Mesh网络中网络拓扑结构、节点密度等因素对网关配置的影响.

本文通过分析无线Mesh网络节点的空间属性，发现其存在空间的聚类特性.基于此特性，提出利用数据聚类思想来解决网关部署问题.

1 问题描述及模型

本文从数据聚类的角度来考虑无线Mesh网络网关部署问题.给定一个由n个网络节点组成的随机网络拓扑结构，其中需要部署的网关共m个.如何选择网关节点以使普通AP节点获得较好的服务质量，是一个难点问题.

将最小跳数作为衡量网络服务质量的参数，给出如下的数学模型:用无向图G=(V，E)来表示无线网状网，其中V为所有顶点的集合，表示所有AP节点(包括潜在的网关节点)，E为所有边的集合，表示所有AP节点间的连通关系.AP节点之间是否能够连通和通信，与节点之间的距离有关.当2个AP节点间的距离大于最佳通信距离时，这2个节点无法连通;反之，则可以连通.

AP节点之间的连通关系可用数学符号表示.∀vi，vj∈V，设di，j为vi，vj间的距离，d为通信距离.用ei，j∈E来表示vi，vj间是否连通.若di，j≤d则连通，ei，j=1;否则，ei，j=0.

显然，网关节点数目越多，提供的网络接入服务的质量越好.但由于部署网关节点需要额外费用，部署的网关节点越多，花费就越大，因此需要在给定的费用约束下寻找一个最佳的网关节点部署方案，使得接入服务最佳.尽管多跳技术可以扩大服务范围，但同时也会造成信号干扰、流量衰减等影响，最终导致网络服务质量下降.为了获得较好的服务质量，各AP节点与网关节点间的最大跳数应存在上限hmax，同时，定义所有AP节点与网关节点间的总跳数为htotal，并以此衡量整体服务质量的好坏，最终目标是最小化htotal.本问题需要满足的约束如下:

1)网关节点个数约束 记I={I1，I2，…，Im}为网关节点所组成的集合，A={a1，a2，…，an－m}为普通AP节点组成的集合.

2)网关节点吞吐量限制 一个网关节点的吞吐量是存在上限的，因此接入的用户数量不能过多，否则网关节点将无法处理所有请求.设网关节点Ii的吞吐量上限为CGW(i)，通过该网关节点接入Internet的AP节点所组成的集合为φ(i)，接入节点aj的所有用户的总流量请求为Dj，则节点吞吐量约束可以表示为

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

∈φ(i)

3)AP节点吞吐量限制 与网关节点一样，AP节点的吞吐量也存在上限，节点ai的吞吐量上限记为CAP(i).可将经过节点ai的流量分为2个部分:①通过ai接入无线网状网的用户所产生的流量，记为本地流量tl(i)=Di;② 其他AP节点通过ai转发的流量.将与ai一跳相连且通过ai向网关节点传递流量的所有AP节点的集合记为ψ(i)，经过节点ai的所有流量为tt(i).假设1个AP节点只能通过1条路径与网关相连，则此约束可表示为

4)最大跳数约束 ∀Ii∈I，aj是通过Ii连入Internet的一个节点，即aj∈φ(i).设Ii与aj间的跳数为hi，j，最大跳数限制为hmax，则hi，j≤hmax，∀Ii∈I，aj∈φ(i).

5)AP节点路径约束 1个AP节点只能与1个网关节点相连.此外，假设网关节点的有线链路容量相对于无线链路容量是无限大的.

由此便可得到如下数学优化模型:

对于任意vi∈V，用0-1变量εi来表示vi是否被选为网关.εi的定义如下:

此外，对于任意的Ii∈I和aj∈A，定义0-1变量 ωi，j.如果aj经由Ii连入有线网，则 ωi，j=1;如果aj经由其他网关连入有线网，则 ωi，j=0.对于Ai，Aj∈A，同样定义 ωi，j=0.

如果假定所有的网关节点具有相同性能，所有的AP节点也具有相同性能，则CAP(j)=CAP，∀Ii∈I，记CGW(i)=CGW.

2 算法描述

与传统的聚类算法相比，标准k-medoids算法能够克服孤立点数据的影响，具有较好的聚类效果［9-10］.在网络节点聚类中，必须考虑节点间的连通关系，因此该算法不能直接应用于无线Mesh网络.为了解决无线Mesh网络网关选择的问题，本文提出了一种改进的k-medoids网关节点选择算法.

标准k-medoids算法的优化目标是使所有节点到簇中心距离和最小，可数学描述为

式中，s为原始划分空间中的数据集合，即给定节点数据对象;Ci为簇中心节点集合;oi为簇Ci中的数据对象集合.

算法1 改进的k-medoids节点聚类算法

输入:拓扑结构图和网关数m.

输出:网关位置和节点分组.

①构建网络拓扑图的邻接矩阵，利用邻接矩阵，将一跳范围内连接节点数最多的对象作为初始簇中心;

②剔除已选择的节点，重复步骤①，直到完成对m个簇中心的选择;

③将m个簇中心作为网关，根据网络节点与中心的最小跳数距离，依次将网络节点分配给最近的网关，直到所有节点都分配给某一网关;

④重新计算每个簇的中心，即簇内到其他所有节点跳数距离之和最小的节点;

⑤重新聚类，直到簇的中心不发生变化;

⑥以最小跳数为指标，将节点依次加入m个最终确定的簇中心;

⑦得到聚类结果，即网关位置和每个网关负责的分组节点.

2.1 初始簇中心的选择方法

为了获得较好的初始簇中心，首先根据网络拓扑图构建对应的邻接矩阵，依次搜索出在一跳范围内连接节点数目最多的节点，并将其作为网关节点;待全部网关节点选定后，采用广度优先搜索的方法，将网络节点依次加入到距离最近的网关，直到所有AP节点都加入某网关节点为止.

选择初始簇中心的详细步骤如下:

①计算所有n个节点的邻接矩阵Mn×n，且ki，j∈Mn×n.如果节点vi与vj间的距离小于最佳通信距离(即di，j≤d)，则在邻接矩阵 Ma中ki，j=1;否则，ki，j=0.在邻接矩阵 Ma中，将各行之和构成的向量记为行和向量pn×1，则pi表示节点vi通过一跳可以到达的节点的数目.

②将pn×1中最大元素的行下标所表示的节点作为第1个网关节点I1，并将所有与I1在一跳内相连的AP节点加入I1中，假设这些AP节点的数目为m1，由其组成的集合为 φ(1).重新计算p(n－m1)×1，I1和加入I1中的 AP 节点将不再计入剩余节点一跳可以连接节点的范围内.将新的pn×1中最大元素的行下标所表示的节点作为第2个网关节点I2，并将V－φ(1)中所有与I2在一跳内相连的AP节点加入I2中，假设这些AP节点的数目为m2，由其组成的集合为φ(2).以此类推，得到m个网关节点I1，I2，…，Im.在此过程中，将所有与各网关节点距离为一跳的AP节点加入到相应的网关节点分组中.

2.2 新的簇中心计算方法

将m个网关节点作为聚类中心点，保持节点网络连接特性的同时，将最小跳数作为距离参数，依次将节点加入到这m个网关节点中.按照I1，I2，…，Im的顺序依次给各网关节点加入AP节点，且每次给每个网关加入一个AP节点.如果节点同时与多个网关的跳数距离相等，则计算每个网关当前拥有的节点数，并将该节点加入到当前拥有节点数最少的网关节点中.以此类推，直到所有节点都被加入某个网关节点分组中.将簇范围内到其他所有节点的跳数距离之和最小的节点作为新的中心.重复上面步骤，直到m个簇中心不发生变化为止.

3 实验分析

图1所示为一个无线Mesh网络随机拓扑结构实例，该拓扑结构中共包含100个网络节点.要求在这些节点中选择10个节点作为网关节点，负责其他节点与有线网络的通信.根据本文算法，首先利用拓扑图的邻接矩阵，选择m个初始网关中心;然后根据网络跳数将节点依次加入到附近的网关节点中.

图1 无线Mesh网络随机拓扑结构实例

由图1(c)可知，所有AP节点都已加入某一个网关节点中.此时，网络节点到网关的平均跳数为1.79，最大跳数为4.

下面通过仿真实验对本文算法进行评价.利用Matlab软件随机生成网络拓扑结构，取100次实验的平均结果作为最终结果.为了衡量和对比算法聚类效果，引入平均跳数和最大跳数2个评价指标.当网络节点总数为100时，运用聚类算法前后网关节点个数与平均跳数、最大跳数的关系见图2.当网关数为10时，运用聚类算法前后网络节点总数与平均跳数、最大跳数的关系见图3.

图2 改变网关数的实验结果对比

图3 改变网络节点总数的实验结果对比

由图2和图3可知，当AP节点数一定时，网关节点数越多，平均跳数和最大跳数越小;当网关节点数一定时，AP节点数越多，平均跳数越大，最大跳数也越大.本文算法可以获得较小的平均跳数和最大跳数，从而较好地实现节点聚类和分组.节点通过较小跳数接入有线网络，可以大幅减少网络延时，保障网络服务质量.

4 结语

网络节点在空间上具有聚类属性.本文将聚类算法引入到无线Mesh网络节点聚类中，以解决网关选择和部署问题.在研究无线Mesh网络节点聚类时，应考虑到节点之间的连通关系.本文以最小网络跳数代替节点间的距离，取得了较好的效果.尽管最小跳数是衡量网络质量的重要参数之一，但是应该同时兼顾其他网络参数指标，这是下一步需要解决的问题.

［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］黄书强，周继鹏.基于聚类的无线Mesh网络网关选择及AP分组算法［J］.华南理工大学学报，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］邵峰晶，于忠清.数据挖掘原理与算法［M］.北京:中国水利水电出版社，2003.

［10］邓松，李文敬，刘海涛.数据挖掘原理与SPSS Clementine应用宝典［M］.北京:电子工业出版社，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.

黄书强(1977—)，男，博士，高级工程师，hsq2008@vip.sina.com.

广东省自然科学基金资助项目(S2011040003481，S2011010001525)、广东省高校优秀青年创新人才培养计划资助项目(LYM09029)、中央高校基本科研业务费专项资金资助项目(21611522).

黄书强，张震，周继鹏.无线Mesh网络节点聚类属性分析［J］.东南大学学报:自然科学版，2012，42(2):219-223.［doi:10.3969/j.issn.1001 －0505.2012.02.005］