A new distributed topology control algorithm based on optimization of delay and energy in wireless networks

被引:31
作者
Gui, Jinsong [1 ]
Liu, Anfeng [1 ]
机构
[1] Cent South Univ, Sch Informat Sci & Engn, Changsha 410083, Hunan, Peoples R China
基金
中国国家自然科学基金;
关键词
Topology control; Delay; Energy consumption; Optimization; AD HOC; NEIGHBORHOOD GRAPH;
D O I
10.1016/j.jpdc.2012.04.007
中图分类号
TP301 [理论、方法];
学科分类号
080201 [机械制造及其自动化];
摘要
Topology Control (TC) is one of the most important techniques used in wireless networks to obtain the desired network property. Most existing works with regard to TC focus on reducing energy consumption. Even though there are some works to consider delay in their resulting topologies, they do not consider the effect of radio interference on delay. Aiming at wireless sensor networks, we model a link delay as a function of the signal to interference noise ratio of the receiving node in this link and its packet forwarding time, and take a weight sum of delay and energy consumption as weight of edge (or link). The minimum weight sum of any edge can be solved by using the Get_min-cost_of_edge_(i, j) algorithm proposed in this paper. An Optimal Edge-cost Topology Control (OETC) algorithm is proposed to ensure that all approximate minimum-edge-cost paths exist in final topology. We also propose a Distributed Symmetric Link Maintenance (DSLM) algorithm to ensure that all links are symmetric in final topology if all links in original topology are symmetric. We prove that the communication complexity and computational complexity in OETC + DLSM are O(N-u) and O(N-e * N-u(2)) respectively, where N-u denotes the number of any node u's neighbors and N-e denotes the times of executing the Get_min-cost_of_edge_(i, j) algorithm. Furthermore, we verify through simulation that the network topologies produced by OETC + DLSM show good performance in terms of expected average link delay and node hop-count while keeping average energy consumption at an acceptable level. (C) 2012 Elsevier Inc. All rights reserved.
引用
收藏
页码:1032 / 1044
页数:13
相关论文
共 25 条
[1]
A survey on wireless multimedia sensor networks [J].
Akyildiz, Ian F. ;
Melodia, Tommaso ;
Chowdhury, Kaushik R. .
COMPUTER NETWORKS, 2007, 51 (04) :921-960
[2]
Bacci G., 2007, ARXIV E PRINTS, V705
[3]
BORBASH SA, 2002, P 2002 WORLD C COMP
[4]
Cormen T., 2001, Introduction to Algorithms
[5]
A NEW STATISTICAL APPROACH TO GEOGRAPHIC VARIATION ANALYSIS [J].
GABRIEL, KR ;
SOKAL, RR .
SYSTEMATIC ZOOLOGY, 1969, 18 (03) :259-&
[6]
Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks [J].
Hajiaghayi, Mohammad Taghi ;
Immorlica, Nicole ;
Mirrokni, Vahab S. .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2007, 15 (06) :1345-1358
[7]
The r-neighborhood graph:: An adjustable structure for topology control in wireless ad hoc networks [J].
Jeng, Andy An-Kai ;
Jan, Rong-Hong .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2007, 18 (04) :536-549
[8]
Adaptive Topology Control for Mobile Ad Hoc Networks [J].
Jeng, Andy An-Kai ;
Jan, Rong-Hong .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (12) :1953-1960
[9]
Jia XH, 2004, IEEE INFOCOM SER, P1264
[10]
Li L, 2001, 2001 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-10, CONFERENCE RECORD, P278, DOI 10.1109/ICC.2001.936317