基于最优能耗多播树构造的Ad hoc网络节点路由算法研究

计算机科学 ›› 2013, Vol. 40 ›› Issue (4): 115-118.

基于最优能耗多播树构造的Ad hoc网络节点路由算法研究

李渊,杨立波

太原大学计算机工程系太原030009;太原大学计算机工程系太原030009

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(J1526987435)资助

Ad hoc Network Node Routing Algorithm Based on the Optimal Energy Consumption Multicast Tree Structure

LI Yuan and YANG Li-bo

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对Ad hoc网络中最小能耗多播树的生成和优化问题,提出了基于最优能耗多播树构造的Ad hoc网络节点路由算法。在该算法中,首先将最小能耗多播树生成问题转化为不同中继节点集合幂空间中的动态寻优问题,构建基于最优能耗多播树求解模型；然后利用改进的粒子群算法对不同维度空间上代表中继节点链路的粒子的权值进行映射和修正计算,再依据粒子适应度值对粒子的局部极值和全局极值进行更新；最后根据粒子位置和速度更新机制进行迭代计算,将最终的全局极值点和极值作为最优多播树的节点位置和能耗值。实验仿真证明,该算法具有较好的粒子多样性,全局搜索和局部搜索能力较好,并且优化能力较强。

关键词: Ad hoc网络,多播树,粒子群,最优能耗

Abstract: In order to solve Ad hoc least energy consumption multicast tree generation and optimization problems, this paper put forward Ad hoc network node routing algorithm based on the optimal energy consumption multicast tree structure. In this algorithm, the minimum cost multicast tree generation problem is first transformed into different relay node set power space of the dynamic optimization problem, and solving model based on the optimal energy consumption multicast tree is built. And the improved particle swarm optimization (pso) algorithm is used to make mapping and correction calculation for the right value of particle representing relay point link in different dimension space and then according to the particle fitness value, the particle's local extremum and global extremum are updated. Accor-ding to the particle position and velocity update mechanism of the iterative calculation, eventually global extreme value point and extreme value are used as the most optimal multicast tree node position and energy consumption value. The simulation results show that this algorithm has better particle diversity and global search and local search ability are good, and the optimization ability is strong.

Key words: Ad hoc working group on the network,Multicast tree,Particle swarm,Optimal energy consumption

李渊,杨立波. 基于最优能耗多播树构造的Ad hoc网络节点路由算法研究[J]. 计算机科学, 2013, 40(4): 115-118. https://doi.org/

LI Yuan and YANG Li-bo. Ad hoc Network Node Routing Algorithm Based on the Optimal Energy Consumption Multicast Tree Structure[J]. Computer Science, 2013, 40(4): 115-118. https://doi.org/

参考文献

[1] Wieselthier J E,Nguyen G D,Ephremides A．On the construction of energy-efficient broadcast and multicast trees in wireless networks [C]∥Proceedings of IEEE INFOCOM’．Tel Aviv,Israel,2000:585-594
[2] Montemanni R,Gambardella L M,Das A K．The minimum po-wer broadcast problem in wireless networks:a simulated annealing approach[C]∥Proceedings of the 2005IEEE Wireless Communications and Networking Conference．New Orleans,LA,USA,2005:2057-2062
[3] Hernandez H,Blum C．Energy-efficient multicasting in wireless ad-hoc networks:an ant colony optimization approach[C]∥Proceedings of the 2008IEEE International Symposium on Wireless Communication Systems．Reykjavik,Iceland,2008:667-671
[4] Das A K,Marks R J,El-Sharkawi M,et al．R-shrink:a heuristic for improving minimum power broadcast trees in wireless networks[C]∥Proceedings of IEEE GLOBECOM’03．San Francisco,A,USA,2003:523-527
[5] Zhong W L,Huang J,Zhang J．A novel particle swarm optimization for the Steiner tree problem in graphs[C]∥Proceedings of the 2008IEEE Congress on Evolutionary Computation．Hong Kong,China,2008:2460-2467
[6] 黄泽霞,俞攸红,黄德才．惯性权自适应调整的量子粒子群优化算法[J].上海交通大学学报,2012,2:228-232
[7] EBERHART R．Fuzzy adaptive particle swarm optimization[C]∥Proceedings of 2001IEEE International Conference on Evolutionary Computation．San Francisco:IEEE Press,2001:101-106
[8] 阳春华,谷丽姗,桂卫华.自适应变异的粒子群优化算法[J].计算机工程,2008,6:188-190
[9] Wieselthier J E,Nguyen G D,Ephremides A．Energy-awarewireless networking with directional antennas:the case of session-based broadcasting and multicasting[J]．IEEE Transactions on Mobile Computing,2002,1(3):176-191
[10] 朱晓建,沈军．基于粒子群优化的ad hoc 网络最小能耗多播路由算法[J]．通信学报,2012,3(3):52-58
[11] Kennedy J,Eberhart R．A discrete binary version of the particle swarm algorithm[C]∥Proceedings of the 1997IEEE International Conference on Systems,Man,and Cybernetics．Orlando,FL,USA,1997:4104-4108
[12] 袁辉勇,阙清贤,羊四清.传感器网络中基于能耗均衡的节点优化部署[J].计算机仿真,2010,7(8):100-102
[13] 杨春德,邓超.一种动态的时延约束费用优化多播路由算法[J].重庆邮电大学学报:自然科学版,2011,3(1):96-100

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed