无线mesh网络节点聚类属性分析-东南大学学报.pdf

第４２卷第２期 东南大学学报（自然科 学版 ） Ｖｏｌ．４２ Ｎｏ．２ 　 ２０１２年３月 ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） 　 Ｍａｒ．２０１２ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－０５０５．２０１２．０２．００５ 无线Ｍｅｓｈ网络节点聚类属性分析 黄书强１ 张　震２ 周继鹏２ １ （暨南大学网络与教育技术中心，广州５１０６３２） ２ （暨南大学信息科学技术学院，广州５１０６３２） 摘要：通过分析无线Ｍｅｓｈ网络节点空间属性，提出了一种改进的ｋｍｅｄｏｉｄｓ网络节点聚类算法． 该算法基于聚类思想，将无线Ｍｅｓｈ网络中的网关部署问题转化为空间节点数据聚类问题．构建 了网络拓扑图的邻接矩阵，并利用邻接矩阵选择具有最多一跳连接节点数的对象作为初始簇中 心．然后以网络跳数代替传统聚类算法中的距离参数，将最小化跳数之和作为优化目标，通过迭 代方法获得稳定的聚类和分组结果．实验结果表明，离散的网络节点在空间上具有聚类特性，利 用该方法可以获得更小的平均跳数和最大跳数，因此可以较好地实现网络节点分组和网关发现． 关键词：无线Ｍｅｓｈ网络；聚类；网络跳数；ｋｍｅｄｏｉｄｓ算法 中图分类号：ＴＰ３９３　　文献标志码：Ａ　　文章编号：１００１－０５０５（２０１２）０２０２１９０５ ＣｌｕｓｔｅｒｉｎｇａｔｔｒｉｂｕｔｅａｎａｌｙｓｉｓｏｎｎｏｄｅｓｏｆｗｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓ １ ２ ２ ＨｕａｎｇＳｈｕｑｉａｎｇ ＺｈａｎｇＺｈｅｎ ＺｈｏｕＪｉｐｅｎｇ １ （ＮｅｔｗｏｒｋａｎｄＥｄｕｃａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＣｅｎｔｅｒ，ＪｉｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０６３２，Ｃｈｉｎａ） ２ （ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＪｉｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０６３２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＢｙａｎａｌｙｚｉｎｇｔｈｅｓｐａｔｉａｌａｔｔｒｉｂｕｔｅｏｆｎｏｄｅｓｏｆｗｉｒｅｌｅｓｓＭｅｓｈｎｅｔｗｏｒｋｓ，ａｎｉｍｐｒｏｖｅｄｋｍｅ ｄｏｉｄｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄｏｎｃｌｕｓｔｅｒｉｎｇ，ｔｈｅａｌｇｏｒｉｔｈｍｃｏｎｖｅｒｔｓｔｈｅｐｒｏｂｌｅｍｏｆ ｇａｔｅｗａｙｄｅｐｌｏｙｍｅｎｔｏｆｗｉｒｅｌｅｓｓｍｅｓｈｎｅｔｗｏｒｋｉｎｔｏａｄａｔａｃｌｕｓｔｅｒｉｎｇｐｒｏｂｌｅｍ．Ｉｎｔｈｅａｌｇｏｒｉｔｈｍ，ａｎ ａｄｊａｃｅｎｃｙｍａｔｒｉｘｏｆｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｓｂｕｉｌｔａｎｄｔｈｅｎｏｄｅｓｗｉｔｈｍｏｓｔａｈｏｐｃｏｎｎｅｃｔｅｄｎｏｄｅｓａｒｅ ｇｒａｄｕａｌｌｙｓｅｌｅｃｔｅｄａｓｉｎｉｔｉａｌｃｌｕｓｔｅｒｃｅｎｔｅｒｓ．Ｔｈｅｎ，ｔｈｅｄｉｓｔａｎｃｅｐａｒａｍｅｔｅｒｂｅｔｗｅｅｎｔｈｅｎｏｄｅｓｉｎｔｈｅ ｔｒａｄｉｔｉｏｎａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｓｒｅｐｌａｃｅｄｂｙｔｈｅｈｏｐｏｆｎｅｔｗｏｒｋ．Ａｎｄｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｏｂｊｅｃｔｉｓａｂ ｓｔｒａｃｔｅｄａｓｍｉｎｉｍｉｚｉｎｇｔｈｅｓｕｍｈｏｐｓｏｆｔｈｅｎｅｔｗｏｒｋ．Ｔｈｅｎｏｄｅｓａｒｅａｄｄｅｄｉｎｔｏｄｉｆｆｅｒｅｎｔｃｌｕｓｔｅｒｓａｎｄ ｔｈｅｌａｓｔｓｔａｂｌｅｃｌｕｓｔｅｒｉｎｇａｎｄｇｒｏｕｐｉｎｇｒｅｓｕｌｔｓａｒｅｏｂｔａｉｎｅｄｂｙｉｔｅｒａｔｉｖｅｗａｙ．Ｔｈｅ