基于改进A*算法的无线Mesh网拓扑状态实时监控方法

doi:10.3724/SP.J.1087.2012.00074

计算机应用 ›› 2012, Vol. 32 ›› Issue (01): 74-77.DOI: 10.3724/SP.J.1087.2012.00074

• 第四届中国计算机网络与信息安全学术会议论文(CCNIS’2011) • 上一篇下一篇

基于改进A*算法的无线Mesh网拓扑状态实时监控方法

牛玲,郭渊博,刘伟

信息工程大学电子技术学院，郑州 450004

收稿日期:2011-08-01 修回日期:2011-08-31 发布日期:2012-02-06 出版日期:2012-01-01
通讯作者: 牛玲
作者简介:牛玲(1985-),女，宁夏银川人，硕士研究生，主要研究方向：无线网络安全和管理；郭渊博(1975-)，男，陕西周至人，副教授，博士，主要研究方向：容忍入侵、无线网络安全、协议安全；刘伟(1963-)，男，河南开封人，副教授，硕士，主要研究方向：信息系统应用与安全。
基金资助:
河南省科技创新杰出青年计划项目(104100510025)

Real-time monitoring method based on improved A* algorithm for topology state of wireless mesh network

NIU Ling,GUO Yuan-bo,LIU Wei

Institute of Electronic Technology, Information Engineering University, Zhengzhou Henan 450004, China

Received:2011-08-01 Revised:2011-08-31 Online:2012-02-06 Published:2012-01-01
Contact: NIU Ling

摘要/Abstract

摘要： 针对无线Mesh网络(WMN)边界难以确定，拓扑结构灵活多变，从而导致拓扑信息的收集和拓扑重构延迟较大，WMN监控精确性和实时性难以保证的问题，提出了一种基于改进A算法的WMN拓扑状态的实时监控方法来了解网络的实时状态，从而对网络可能出现的异常作出反应。通过缩短A搜索过程中的路径长度、缩小搜索范围，将重复搜索的边数作为影响因素增加到启发式中，解决了拓扑实时监控中存在的路径重复覆盖、搜索路径较长的问题。仿真表明，和原算法相比，当网络拓扑结构发生变化时，改进算法的拓扑收敛速度较高，可以在较短时间内完成对全网拓扑结构的更新。

关键词: 实时监控, 收敛, A*搜索算法, 拓扑重构

Abstract: Since it is difficult to determine the network boundaries and topology is very flexible in Wireless Mesh Network (WMN), topology information collection and reconstruction have great delay, so that real-time WMN monitoring accuracy can not be ensured. This paper proposed a real-time monitoring method based on improved A algorithm for the topology state of WMN to get the real-time state and give out response to abnormity. Through limiting the path length, reducing the search scope and adding the number of repeated searched edges to heuristic of A, the method solved the problem that path may be recovered and too long for topology real-time monitoring. The simulation results show that compared with the original algorithm, the improved algorithm has a higher speed in convergence, and it can update the topology construction in shorter time.

Key words: real-time monitoring, convergence, A * search algorithm, topology reconstruction

中图分类号:

TP393.06

牛玲郭渊博刘伟. 基于改进A*算法的无线Mesh网拓扑状态实时监控方法[J]. 计算机应用, 2012, 32(01): 74-77.

NIU Ling GUO Yuan-bo LIU Wei. Real-time monitoring method based on improved A* algorithm for topology state of wireless mesh network[J]. Journal of Computer Applications, 2012, 32(01): 74-77.

参考文献

[1]

WANG XUDONG, LIM A O. IEEE 802.11s wireless mesh net-works: Framework and challenges ［J］. IEEE Transactions on Mobile Computing, 2009, 6(6): 970-984.

[2]

PINTO R. WMM-Wireless mesh monitoring ［J］. Ad Hoc Network, 2009, 6(6): 445-487.

[3]

刘少伟，罗丹彦，向琳，等.能量均衡的无线传感器网络拓扑控制算法［J］.电子科学技术大学学报，2010,39(S1)：89-93.

[4]

RAGHAVENDRA R, ACHARYA P, BELDING E M, et al. MeshMon: A multi-tiered framework for wireless mesh network monitoring ［C］// MobiHoc S3'09: Proceedings of the 2009 MobiHoc S3 Workshop on MobiHoc S3. New York: ACM Press, 2009: 134-138.

[5]

ATHANASIOU G, KORAKIS T, ERCETIN O, et al. A cross-layer framework for association control in wireless mesh networks ［J］. IEEE Transactions on Mobile Computing, 2009, 8(4): 952-957.

[6]

BREDEL M, FIDLER M. A measurement study of bandwidth esti-mation in IEEE 802.11g wireless LANs using the DCF ［C］// NETWORKING'08: Proceedings of the 7th International IFIP-TC6 Networking Conference on Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet. Berlin: Springer-Verlag, 2008: 314-325.

[7]

RAMACHANDRAN K N, BELDING-ROYER E M, ALMEROTH K C. DAMON: A distributed architecture for monitoring multi-hop mobile networks ［C］// IEEE SECON 2004: Proceedings of the First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. Washington, DC: IEEE Computer Society, 2004: 347-357.

[8]

SCHOR L, SOMMER P, WATTENHOFER R. Towards a zero-configuration wireless sensor network architecture for smart buildings ［C］// BuildSys'09: Proceedings of the First ACM Workshop on Embedded Sensing Systems for Energy-Efficiency in Buildings. New York: ACM Press, 2009: 762-769.

[9]

刘浩,鲍远律.A算法在矢量地图最优路径搜索中的应用［J］.计算机仿真，2008,25(4)：253-257.

[10]

PATRICK K-W. On path of decomposition of complete graphs ［D］. Burnaby, British Columbia: Simon Fraser University, Department of Mathematics and Statistics, 2004.

[11]

PYBER L. Covering the edges of a connected graph by paths ［J］. Journal of Combinatorial Theory: Series B, 1966, 66(1): 152-159.

[12]

ZHAI MING-QING, L CHANG-HONG. Path decomposition of graphs with given path length ［J］. Acta Mathematicae Applicatae Sinica: English Series, 2006, 22(4): 633-638.

[13]

TEYPAZ N, RAPINE C. Graph decomposition into paths under length constraints ［EB/OL］. ［2011-04-10］. http://hal.archives-ouvertes.fr/docs/00/27/81/89/PDF/article.pdf.

[14]

周影,曹菡,李军霞.一种限制区域的最短路径查找算法［J］.微电子学与计算机，2007,24(8)：110-112.

[1]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[2]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[3]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[4]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[5]	刘静姝, 王莉, 刘惊雷. 无需特征分解的快速谱聚类算法[J]. 计算机应用, 2020, 40(12): 3413-3422.
[6]	陈维兴, 刘清涛, 孙习习, 陈斌. 机坪感知网络的快速收敛平均一致性时间同步算法[J]. 计算机应用, 2020, 40(11): 3407-3412.
[7]	韦姗姗, 胡圣波, 鄢婷婷, 莫金容. 基于分步小波变换的对流层电波传播特性和分析软件[J]. 计算机应用, 2019, 39(6): 1792-1798.
[8]	李人敏, 黄劲松, 陈琛, 吴君钦. 基于改进粒子群算法的毫米波大规模MIMO混合预编码方案[J]. 计算机应用, 2018, 38(8): 2365-2369.
[9]	徐光宪, 赵越, 赖俊宁. 基于网络编码的确定性逐层构造算法[J]. 计算机应用, 2018, 38(3): 769-775.
[10]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.
[11]	吕立国, 季伟东. 结合质心思想和柯西变异策略的粒子群优化算法[J]. 计算机应用, 2017, 37(5): 1369-1375.
[12]	欧阳宁, 曾梦萍, 林乐平. 基于并列卷积神经网络的超分辨率重建[J]. 计算机应用, 2017, 37(4): 1174-1178.
[13]	梁本来, 杨忠明, 秦勇, 蔡昭权. 引入梯度下降的蚁群算法求解多约束服务质量路由[J]. 计算机应用, 2017, 37(3): 722-729.
[14]	林凯, 陈国初, 张鑫. 多交互式人工蜂群算法及其收敛性分析[J]. 计算机应用, 2017, 37(3): 760-765.
[15]	刘竹松, 杨张杰. 基于布隆过滤器所有权证明的高效安全可去重云存储方案[J]. 计算机应用, 2017, 37(3): 766-770.

基于改进A*算法的无线Mesh网拓扑状态实时监控方法

Real-time monitoring method based on improved A* algorithm for topology state of wireless mesh network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics