无线自组网中基于离散粒子群优化的睡眼调度感知最小功率广播

doi:10.3969/j.issn.1000-436X.2013.06.003

摘要/Abstract

摘要：

针对当网络使用睡眠调度并且节点的传输功率连续可调节时的最小功率广播调度问题，首先给出了一种计算节点内部最优发送调度的递归方法，然后提出了一种构造最小功率广播调度的离散粒子群算法。该算法搜索最优广播树结构，并融合基于最小广播功率增量的贪心算法和基于启发式调整广播树结构的局部优化算法以提高收敛速度和求解质量。模拟实验结果表明所提算法能够有效地减少广播功率。

关键词: 无线自组网, 睡眠调度, 最小功率, 广播调度, 离散粒子群优化

Abstract:

For the minimum power broadcast scheduling problem where network uses sleep scheduling and each node's transmission power is continuously adjustable,a recursive approach to compute the optimal transmission scheduling of a node was firstly presented,and then a discrete particle swarm optimization algorithm to construct the minimum power broadcast scheduling was proposed.This algorithm searches for the optimal broadcast arborescence,and utilizes the greedy algorithm based on the minimization of the broadcast's power increment and the local optimization algorithm based on the heuristic adjustment of the broadcast arborescence to improve the convergence speed and the result quality.The simulation results show that the proposed algorithm is able to effectively reduce the broadcast power.

Key words: wireless ad hoc networks, sleep scheduling, minimum power, broadcast scheduling, discrete particle swarm optimization

朱晓建,沈军. 无线自组网中基于离散粒子群优化的睡眼调度感知最小功率广播[J]. 通信学报, 2013, 34(6): 16-28.

Xiao-jian ZHU,Jun SHEN. Sleep scheduling-aware minimum power broadcast in wireless ad hoc networks based on discrete particle swarm optimization[J]. Journal on Communications, 2013, 34(6): 16-28.

图/表 5

图1

图2

图3

图4

表1

对于节点数为50的基准测试实例鲁算法计算结果"

实例	最优解					算法
		ELS(with LS(2))^[10]		GA-2s^[12]		ACO^[11]		PSO^[15]		SCLPSODCMPBS-6s
		平均超出率/%	计算出最优解的次数	平均超出率/%	计算出最优解的次数	平均超出率/%	计算出最优解的次数	平均超出率/%	计算出最优解的次数	平均超出率/%	计算出最优解的次数
0	399 074.64	0.41	15/30	0.88	6/30	0	30/30	0	30/30	0	30/30
1	≤373 565.15	0.16	5/30	0.36	9/30	0	30/30	0	30/30	0	30/30
2	393 641.09	0.28	13/30	0	30/30	0	30/30	0	30/30	0	30/30
3	316 801.09	1.71	11/30	0	30/30	0	30/30	0	30/30	0	30/30
4	≤325 774.22	0.3	25/30	0.4	8/30	0	30/30	0	30/30	0	30/30
5	382 235.90	0.83	16/30	0	30/30	0	30/30	0	30/30	0	30/30
6	≤384 438.46	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
7	≤401 836.85	0.54	24/30	1.46	1/30	0	30/30	0	30/30	0	30/30
8	334 418.45	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
9	≤346 732.05	3.29	0/30	1.24	17/30	0	30/30	0	30/30	0	30/30
10	416 783.45	1.16	13/30	0	30/30	0	30/30	0	30/30	0	30/30
11	≤369 869.41	2.87	1/30	0.32	25/30	0	30/30	0	30/30	0	30/30
12	≤392 326.01	0.57	7/30	0.9	20/30	0	30/30	0	30/30	0	30/30
13	≤400 563.83	0.04	29/30	0.09	11/30	0	30/30	0	30/30	0	30/30
14	388 714.91	0.34	3/30	0	30/30	0.01	29/30	0.47	28/30	0	30/30
15	371 694.65	0.2	5/30	0	30/30	0	30/30	0	30/30	0	30/30
16	≤414 587.42	0.3	26/30	1.24	1/30	0	30/30	0	30/30	0	30/30
17	355 937.07	1.88	17/30	0.03	28/30	0	30/30	0	30/30	0	30/30
18	≤376 617.33	0.24	8/30	0	24/30	0	30/30	0	29/30	0	30/30
19	335 059.72	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
20	≤414 768.96	0.15	0/30	0.13	4/30	0.04	21/30	0	30/30	0.01	28/30
21	≤361 354.27	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
22	329 043.51	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
23	383 321.04	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
24	404 855.92	0.07	17/30	0	30/30	0	30/30	0	30/30	0	30/30
25	363 200.32	0	30/30	0	30/30	0	30/30	0	30/30	0	30/30
26	406 631.51	2.17	2/30	0.30	27/30	0	30/30	0	30/30	0	30/30
27	≤451 059.62	0.18	22/30	0.01	29/30	0	30/30	0	30/30	0	30/30
28	≤415 832.44	0.47	23/30	0.16	27/30	0	30/30	0	30/30	0	30/30
29	380 492.77	0.08	27/30	0	30/30	0	30/30	0	30/30	0	30/30
	总平均	0.6117.3/30		0.2522.9/30		029.67/30		0.0229.9/30		029.93/30

表1

参考文献 29

[1]	WIESELTHIER J E , NGUYEN G D , EPHREMIDES A . On the construction of energy-efficient broadcast and multicast trees in wireless networks[A]. Proceedings of the IEEE INFOCOM'2000[C]. Tel Aviv,Israel, 2000. 585-594.
[2]	WAN P J , CALINESCU G , LI X Y , et al. Minimum-energy broadcast routing in static ad hoc wireless networks[A]. Proceedings of the IEEE INFOCOM'2001[C]. Anchorage,Alaska,USA, 2001. 1162-1171.
[3]	DAS A K , MARKS R J , EL-SHARKAWI M , et al. Minimum power broadcast trees for wireless networks: integer programming formulations[A]. Proceedings of the IEEE INFOCOM'2003[C]. San Francisco,CA,USA, 2003. 1001-1010.
[4]	CAGALJ M , HUBAUX J P , ENZ C . Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues[A]. Proceedings of the Eighth Annual International Conference on Mobile Computing and Networking[C]. Atlanta,Georgia,USA, 2002. 172-182.
[5]	MIN M , PARDALOS P M . Total energy optimal multicasting in wireless ad hoc networks[J]. Journal of Combinatorial Optimization, 2007,13(4): 365-378.
[6]	DAS A K , MARKS R J , EL-SHARKAWI M , et al. R-shrink: a heuristic for improving minimum power broadcast trees in wireless networks[A]. Proceedings of the 2003 IEEE Global Telecommunications Conference[C]. San Francisco,CA,USA, 2003. 523-527.
[7]	LIANG W . Constructing minimum-energy broadcast trees in wireless ad hoc networks[A]. Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing[C]. Lausanne,Switzerland, 2002. 112-122.
[8]	AL-SHIHABI S , MERZ P , WOLF S . Nested partitioning for the minimum energy broadcast problem[A]. Proceedings of the Second International Conference on Learning and Intelligent Optimization (LION 2007 II)[C]. Trento,Italy, 2007. 1-11.
[9]	MONTEMANNI R , GAMBARDELLA L M , DAS A K . The minimum power broadcast problem in wireless networks: a simulated annealing approach[A]. Proceedings of the 2005 IEEE Wireless Communications and Networking Conference[C]. New Orleans,LA,USA, 2005. 2057-2062.
[10]	WOLF S , MERZ P . Evolutionary local search for the minimum energy broadcast problem[A]. Proceedings of the 8th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2008)[C]. Naples,Italy, 2008. 61-72.
[11]	HERNANDEZ H , BLUM C . Ant colony optimization for multicasting in static wireless ad-hoc networks[J]. Swarm Intelligence, 2009,3(2): 125-148.
[12]	SINGH A , BHUKYA W N . A hybrid genetic algorithm for the mini-mum energy broadcast problem in wireless ad hoc networks[J]. Applied Soft Computing, 2011,11(1): 667-674.
[13]	YUAN P , JI C , ZHANG Y , et al. POptimal multicast routing in wireless ad hoc sensor networks[A]. Proceedings of the 2004 IEEE International Conference on Networking,Sensing and Control[C]. 2004. 367-371.
[14]	朱晓建, 沈军, . 基于粒子群优化的ad hoc网络最小能耗多播路由算法[J]. 通信学报, 2012,33(3):52-58. ZHU X J , SHEN J . Minimum energy consumption multicast routing in ad hoc networks based on particle swarm optimization[J]. Journal on Communications, 2012,33(3):52-58.
[15]	HSIAO P C , CHIANG T C , FU L C . Particle swarm optimization for the minimum energy broadcast problem in wireless ad-hoc networks[A]. Proceedings of the 2012 IEEE Congress on Evolutionary Computation[C]. Brisbane,Australia, 2012. 1-8.
[16]	PALCHAUDHURI S , JOHNSON D B . Power mode scheduling for ad hoc networks[A]. Proceedings of the 10th IEEE International Conference on Network Protocols[C]. Paris,France, 2002. 192-193.
[17]	BUETTNER M , YEE G V , ANDERSON E . X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[A]. Proceedings of the 4th International Conference on Embedded Net-worked Sensor Systems[C]. Boulder,Colorado,USA, 2006. 307-320.
[18]	GU Y , HE T . Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[A]. Proceedings of the 5th International Conference on Embedded Networked Sensor Systems[C]. Sydney,Australia, 2007. 321-334.
[19]	GUO S , GU Y , JIANG B , et al. Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links[A]. Proceedings of the 15th Annual International Conference on Mobile Computing and Networking[C]. Beijing,China, 2009. 133-144.
[20]	HONG J , CAO J , LI W , et al. Minimum-transmission broadcast in uncoordinated duty-cycled wireless ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2010,59(1): 307-318.
[21]	WANG F , LIU J . Duty-cycle-aware broadcast in wireless sensor net-works[A]. Proceedings of the IEEE INFOCOM'2009[C]. Rio de Janeiro,Brazil, 2009. 468-476.
[22]	SU L , DING B , YANG Y , et al. OCast: optimal multicast routing protocol for wireless sensor networks[A]. Proceedings of the 17th IEEE International Conference on Network Protocols[C]. Princeton,New Jersey,USA, 2009. 151-160.
[23]	HAN K , LIU Y , LUO J . Duty-cycle-aware minimum-energy multicasting in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2013,21(3): 910-923.
[24]	CHEN W N , ZHANG J , CHUNG H S H , et al. A novel set-based particle swarm optimization method for discrete optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2010,14(2): 278-300.
[25]	KENNEDY J , EBERHART R . Particle swarm optimization[A]. Proceedings of the 1995 IEEE International Conference on Neural Networks[C]. Perth,Australia, 1995. 1942-1948.
[26]	EBERHART R , KENNEDY J . A new optimizer using particle swarm theory[A]. Proceedings of the Sixth International Symposium on Micro Machine and Human Science[C]. Nagoya,Japan, 1995. 39-43.
[27]	SHI Y , EBERHART R . A modified particle swarm optimizer[A]. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation[C]. Anchorage,AK,USA, 1998. 69-73.
[28]	GONG Y J , ZHANG J , LIU O , et al. Optimizing the vehicle routing problem with time windows: a discrete particle swarm optimization approach[J]. IEEE Transactions on Systems,Man,and Cybernetics,Part C: Applications and Reviews, 2012,42(2): 254-267.
[29]	LIANG J J , QIN A K , SUGANTHAN P N , et al. Comprehensive learning particle swarm optimizer for global optimization of multimo-dal functions[J]. IEEE Transactions on Evolutionary Computation, 2006,10(3): 281-295.