Research On Virtual Backbone Construction Algorithms In Heterogeneous Wireless Ad Hoc Networks

Wireless ad hoc network brings up a revolution for information sensing and interactions for recent years due to its characteristics such as low cost,distributed,and ad hoc.Meanwhile,it has a wide range of applications in the fields of intelligent transportation,environment monitoring,disaster forcasting and rescue,smart health care,battlefield surveillance,mobile conference,etc.Nevertheless,due to the limitation of battery power,the computation ability and communication overhead of the nodes in wireless ad hoc networks are still limited.To address this problem,a wireless ad hoc network usually relies on virtual backbones for the communications among nodes.Simply speaking,a virtual backbone is a subset of a wireless ad hoc network that the routing tasks are restricted on the backbone nodes.The non-backbone nodes are in a sleeping mode when they are idle.A vritual backbone can not only save energy,but can also reduce the communication cost and alleviate the signal interference and channel competition problems.Currently,Connected Dominating Sets(CDSs)are the major method to generate virtual backbones of wireless ad hoc networks.Since small virtual backbones can better improve the communication efficiency of the network,most of existing virtual backbone generation algorithms focus on constructing small virtual backbones.Thus can be abstracted as a Minimum Connected Dominating Set(MCDS)problem of a graph.The MCDS problem is an NP-hard problem.Therefore,approximation algorithms are used to generate MCDSs.Existing works on CDSs mostly focused on homogeneous wireless ad hoc networks.But real-world wireless ad hoc networks are usually heterogeneous.Therefore,this dissertation studies the CDS construction problem in heterogeneous wireless ad hoc networks.This dissertation models heterogeneous wirelss ad hoc networks in following three aspects,whereby MCDS approximation algorithms are designed:(1)Communication latency.Besides the number of nodes in a virtual backbone,communication latency is also an important factor of virtual backbones.This problem is especially critical in high-latency wireless ad hoc networks.For example,in underwater ad hoc networks,since electromagnetic waves decay quickly in water,underwater ad hoc networks usually use sonars for acoustic communications.However,acoustic signals have low propagation speed(1.5×10~3 m/second)compared to radio signals(3×10~8 m/second).Therefore,in underwater ad hoc networks,the latency among nodes cannot be measured by“hops”as terrestrial ad hoc networks based on electromagnetic wave communications.To address this problem,this dissertation abstracts wireless ad hoc network with high node-to-node communication latency as graphs with weighted edges,and designs three algorithms(CDS-LO-1,CDS-LO-2,CDS-LO-3)to optimize the size of a CDS while optimizing its latency.Two parameters are often used to evaluate the communication latency of a network:diameter(the longest shortest path in the network)and routing cost(the shortest paths among any pair of nodes in the network).CDS-LO-1 has approximation raito 2 to CDS diameter,but has no constant approximation ratio to CDS size;CDS-LO-2 has approximation ratio 140 to CDS size,and has approximation ratio 6 to the routing cost;CDS-LO-3has approximation ratio 10.197 to CDS size,and approximation ratio 12 to CDS diameter.(2)Transmission range.In scenarios such as disaster rescue that require fast response or the communication devices may be damaged,wireless ad hoc networks have significant advantages because of its flexible and simple deployment.However,restricted by the objective conditions(such as the response time,equipment cost),wireless nodes have different communication capabilities,which is directly reflected on the differences of transmission ranges.For wireless ad hoc network with different transmission ranges,existing works cannot obtain CDS construction algorithms with low approximation ratios.Based on the classical mathematical problems“circle packing”,“sphere packing”,and“spherical code”,this dissertation proposes constant approximation MCDS construction algorithms for wireless ad hoc networks with heterogeneous transmission ranges.With the proposed results,in two-dimensional networks,when the transmission range ratio is(1,1.152],(1.152,1.307],…,this dissertation proposes CDS algorithms with approximation ratio 9.9459,11.0794,…,where the transmission range ratio is defined as the ratio over the maximum transmission range to the minimum transmission range.Thus sigficantly improves the best-known approximation ratio 19.708 in existing works.In three-dimensional networks,when the transmission range ratio is(1,1.023],(1.023,1.055],…,this dissertation proposes CDS algorithms with approximation ratio 16.02,17.02,…,the first time.(3)Remaining energy.For virtual backbone-based ad hoc networks,a non-backbone node can go into a sleep mode to save energy.Therefore,the backbone nodes bear more communication tasks as relays,meanwhile consume more energy.The differences between backbone nodes and non-backbone nodes lead to the differences of remaining energy of nodes.If a fixed backbone is used,then the backbone nodes will be out of power soon and be failed,leading to the failure of the entire network.To address this problem,this dissertation proposes two problems(CDS-LL and E-CDS-LL)to balance the loads of nodes,in order to improve the lifetime of the network.CDS-LL achieves trade-offs between size and lifetime of a CDS through tunning parameters.With the loss of about 8%size,CDS-LL can rise the lifetime about 6 times.E-CDS-LL is an extension of CDS-LL.It dynamically generates CDSs to further prolong the network lifetime.In contrast of CDS-LL,E-CDS-LL can increase about 66%of the network lifetime.In all,based on the network models with different node-to-node communication latency,transmission ranges of nodes,and remaining energy of nodes,this dissertation studies the CDS construction algorithms.On the theoretical value,this dissertation promotes the researches on the fundmental mathematical problem of MCDS in graph theory with edge-weighted graphs,non-unit disk graphs,and non-unit ball grpahs;In practical value,besides the size of CDSs,this dissertation optimizes the communication latency and lifetime of networks,and demonstrates the efficiency of the algorithms through experiments.