Construction and maintenance of virtual backbone in wireless networks

In ad hoc wireless networks, there is no predefined infrastructure and nodes communicate with each other via peer communications. In order to make routing efficient in such networks the connected dominating set (CDS) can act as virtual backbone for the network. A smaller virtual backbone suffers less from the interference problem and incurs less maintenance overhead. Computing minimum CDS backbone is proven to be NP-Hard, it is therefore desirable to use efficient heuristic algorithms to find a virtual backbone of small size. Diameter and average backbone path length (ABPL) are other major criteria for evaluation of the backbone produced by an algorithm. In this paper, after giving a brief survey of classical CDS algorithms, two new centralized algorithms are described for the construction of the virtual backbone and their performance has been compared with five recent algorithms (two centralized and three distributed) along the parameters: size, diameter, and ABPL. The new algorithms perform better on most of the criteria. The re-construction of entire CDS upon movement or failure of a few nodes is very costly in terms of processing power, battery utilization, bandwidth utilization etc., as compared to maintaining the CDS for the affected nodes, since the re-construction of the CDS is to be performed for the whole network while maintenance involves the affected nodes and their neighbours only. A new distributed algorithm is described that maintains the virtual backbone on movement or failure of a single node. The overhead of CDS maintenance with this algorithm compares very favourably against that of re-construction.     

Rotation of CDS via Connected Domatic Partition in Ad Hoc Sensor Networks

Wireless ad hoc and sensor networks (WSNs) often require a connected dominating set (CDS) as the underlying virtual backbone for efficient routing. Nodes in a CDS have extra computation and communication load for their role as dominator, subjecting them to an early exhaustion of their battery. A simple mechanism to address this problem is to switch from one CDS to another fresh CDS, rotating the active CDS through a disjoint set of CDSs. This gives rise to the connected domatic partition (CDP) problem, which essentially involves partitioning the nodes V(G) of a graph G into node disjoint CDSs. We have developed a distributed algorithm for constructing the CDP using our maximal independent set (MIS)-based proximity heuristics, which depends only on connectivity information and does not rely on geographic or geometric information. We show that the size of a CDP that is identified by our algorithm is at least lfloor{frac{delta+1}{beta(c+1)}}rfloor-f, where delta is the minimum node degree of G, betaleq 2, cleq 11 is a constant for a unit disk graph (UDG), and the expected value of f is epsilondelta|V|, where epsilon ll 1 is a positive constant, and delta geq 48. Results of varied testing of our algorithm are positive even for a network of a large number of sensor nodes. Our scheme also performs better than other related techniques such as the ID-based scheme.     

The first constant factor approximation for minimum partial connected dominating set problem in growth-bounded graphs

The idea of virtual backbone has emerged to improve the efficiency of flooding based routing algorithms for wireless networks. The effectiveness of virtual backbone can be improved as its size decreases. The minimum connected dominating set (CDS) problem was used to compute minimum size virtual backbone. However, as this formulation requires the virtual backbone nodes to connect all other nodes, even the size of minimum virtual backbone can be large. This observation leads to consider the minimum partial CDS problem, whose goal is to compute a CDS serving only more than a certain portion of the nodes in a given network. So far, the performance ratio of the best approximation algorithm for the problem is \(O(\ln \varDelta ),\) where \(\varDelta\) is the maximum degree of the input general graph. In this paper, we first assume the input graph is a growth-bounded graph and introduce the first constant factor approximation for the problem. Later, we show that our algorithm is an approximation for the problem in unit disk graph with a much smaller performance ratio, which is of practical interest since unit disk graph is popular to abstract homogeneous wireless networks. Finally, we conduct simulations to evaluate the average performance of our algorithm.     

DUCR: Distributed unequal cluster‐based routing algorithm for heterogeneous wireless sensor networks

Designing energy efficient communication protocols for wireless sensor networks (WSNs) to conserve the sensors' energy is one of the prime concerns. Clustering in WSNs significantly reduces the energy consumption in which the nodes are organized in clusters, each having a cluster head (CH). The CHs collect data from their cluster members and transmit it to the base station via a single or multihop communication. The main issue in such mechanism is how to associate the nodes to CHs and how to route the data of CHs so that the overall load on CHs are balanced. Since the sensor nodes operate autonomously, the methods designed for WSNs should be of distributed nature, i.e., each node should run it using its local information only. Considering these issues, we propose a distributed multiobjective‐based clustering method to assign a sensor node to appropriate CH so that the load is balanced. We also propose an energy‐efficient routing algorithm to balance the relay load among the CHs. In case any CH dies, we propose a recovery strategy for its cluster members. All our proposed methods are completely distributed in nature. Simulation results demonstrate the efficiency of the proposed algorithm in terms of energy consumption and hence prolonging the network lifetime. We compare the performance of the proposed algorithm with some existing algorithms in terms of number of alive nodes, network lifetime, energy efficiency, and energy population.     

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.     

Zone-based virtual backbone formation in wireless ad hoc networks

Efficient protocol for clustering and backbone formation is one of the most important issues in wireless ad hoc networks. Connected dominating set (CDS) formation is a promising approach for constructing virtual backbone. However, finding the minimum CDS in an arbitrary graph is a NP-Hard problem. In this paper, we present a novel zone-based distributed algorithm for CDS formation in wireless ad hoc networks. In this Zone algorithm, we combine the zone and level concepts to sparsify the CDS constructed by previous well-known approaches. Therefore, this proposed algorithm can significantly reduce the CDS size. Particularly, we partition the wireless network into different zones, construct a dominating tree for each zone and connect adjacent zones by inserting additional connectors into the final CDS (at the zone borders). Our comprehensive simulation study using a custom simulator shows that this zone-based algorithm is more effective than previous approaches. The number of nodes in the CDS formed by this Zone algorithm is up to around 66% less than that constructed by others. Moreover, we also compare the performance of Zone algorithm with some recently proposed CDS formation protocols in ns2 simulator.     

无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.     

基于图着色的无线自组网极小连通支配集算法

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。     

Connected dominating sets in disk graphs with bidirectional links

In this paper, we study the connected dominating set (CDS) problem in disk graphs. The CDS problem has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in unit disk graphs, in which each node has the same transmission range. However, in wireless ad hoc networks, the transmission ranges of all nodes are not necessary equal. In this paper, we introduce the CDS problem in disk graphs and present a constant approximation algorithm which can be implemented as a distributed algorithm.     

RECA: Referenced energy‐based CDS algorithm in wireless sensor networks

Connected dominating sets (CDS) can be used to form virtual backbones for the hierarchical routing to save energy in the wireless sensor networks. The existing algorithms for CDS can only be used to the topologies that have larger vertex connective degrees. Besides, most of them do not consider the energy characteristics of the virtual backbones constructed by the dominating sets. In this paper, a referenced energy‐based CDS algorithm (RECA) is proposed, which can generate smaller CDS in random topologies without the limitation of vertex connective degrees. At the same time, the algorithm introduces Referenced Energy as a parameter for nodes when making the decision whether they are chosen to be the dominators or not. Therefore, as the experimental results show, the energy characteristic of the dominating set is improved and routing in the virtual backbones constructed by such CDSs will have a better performance. Copyright © 2009 John Wiley & Sons, Ltd.     

A distributed battery recovery aware topology control algorithm for wireless sensor networks

Battery recovery effect is a phenomenon that the available capacity of a battery could increase if the battery can sleep for a certain period of time since its last discharging. Accordingly, the battery can work for a longer time when it takes some rests between consecutive discharging processes than when it works all the time. However, this effect has not been considered in the design of energy‐efficient topology control algorithms for wireless sensor networks. In this paper, we propose a distributed battery recovery effect aware connected dominating set constructing algorithm (BRE‐CDS) for wireless sensor networks. In BRE‐CDS, each network node periodically decides to join the connected dominating set or not. Nodes that have slept in the preceding round have priority to join the connected dominating set in the current round while nodes that have worked in the preceding round are encouraged to take sleep in the current round for battery recovery. Detailed algorithm design is presented. The computational complexity of BRE‐CDS is deduced to be O(D²), where D is node degree. Simulation results show that BRE‐CDS can significantly prolong the network lifetime as compared with existing work. Copyright © 2016 John Wiley & Sons, Ltd.     

时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。     

Non-Euclidian geographic routing in wireless networks

Greedy geographic routing is attractive for large multi-hop wireless networks because of its simple and distributed operation. However, it may easily result in dead ends or hotspots when routing in a network with obstacles (regions without sufficient connectivity to forward messages). In this paper, we propose a distributed routing algorithm that combines greedy geographic routing with two non-Euclidian distance metrics, chosen so as to provide load balanced routing around obstacles and hotspots. The first metric, Local Shortest Path, is used to achieve high probability of progress, while the second metric, Weighted Distance Gain, is used to select a desirable node among those that provide progress. The proposed Load Balanced Local Shortest Path (LBLSP) routing algorithm provides loop freedom, guarantees delivery when a path exists, is able to efficiently route around obstacles, and provides good load balancing.     

Connected Dominating Sets in Wireless Networks with Different Transmission Ranges

Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which all nodes have the same transmission ranges. However, in practice, the transmission ranges of all nodes are not necessarily equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present two efficient approximation algorithms to obtain a minimum CDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. These algorithms can be implemented as distributed algorithms. Furthermore, we show a size relationship between a maximal independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.     

Utility‐driven construction of balanced data routing trees in wireless sensor networks

In wireless sensor networks, achieving load balancing in an energy‐efficient manner to improve the network lifetime as much as possible is still a challenging problem because in such networks, the only energy resource for sensor nodes is their battery supplies. This paper proposes a game theoretical‐based solution in the form of a distributed algorithm for constructing load‐balanced routing trees in wireless sensor networks. In our algorithm, load balancing is realized by adjusting the number of children among parents as much as possible, where child adjustment is considered as a game between the parents and child nodes; parents are considered as cooperative players, and children are considered as selfish players. The gained utility by each node is determined by means of some utility functions defined per role, which themselves determine the behavior of nodes in each role. When the game is over, each node gains the maximum benefit on the basis of its utility function, and the balanced tree is constructed. The proposed method provides additional benefits when in‐network aggregation is applied. Analytical and simulation results are provided, demonstrating that our proposed algorithm outperform two recently proposed benchmarking algorithms [1, 2], in terms of time complexity and communication overhead required for constructing the load‐balanced routing trees. Copyright © 2012 John Wiley & Sons, Ltd.     

Adaptive Backbone Based Cooperative Caching in Mobile Ad hoc Networks

Existing cooperative caching algorithms for mobile ad hoc networks face serious challenges due to message overhead and scalability issues. To solve these issues, we propose an adaptive virtual backbone based cooperative caching that uses a connective dominating set (CDS) to find the desired location of cached data. Message overhead in cooperative caching is mainly due to cache lookup process used for cooperative caching. The idea in this scheme is to reduce the number of nodes involved in cache look up process, by constructing a virtual backbone adaptive to the dynamic topology in mobile ad hoc networks. The proposed algorithm is decentralized and the nodes in the CDS perform data dissemination and discovery. Simulation results show that the message overhead created by the proposed cooperative caching technique is very less compared to other approaches. Moreover, due to the CDS based cache discovery we applied in this work, the proposed cooperative caching has the potential to increase the cache hit ratio and reduce average delay.     

Fuzzy chessboard clustering and artificial bee colony routing method for energy‐efficient heterogeneous wireless sensor networks

Energy is an extremely critical resource for battery‐powered wireless sensor networks (WSNs), thus making energy‐efficient protocol design a key challenging problem. However, uneven energy consumption is an inherent problem in WSNs caused by multi‐hop routing and many‐to‐one traffic pattern among sensors. In this paper, we therefore propose a new clustering method called fuzzy chessboard clustering (FFC), which is capable to overcome the bottleneck problem and addressing the uneven energy consumption problem in heterogeneous WSNs. We also propose an energy‐efficient routing method called artificial bee colony routing method (ABCRM) to find the optimal routing path for the heterogeneous WSNs. ABCRM seeks to investigate the problems of balancing energy consumption and maximization of network lifetime. To demonstrate the effectiveness of FCC‐ABCRM in terms of lessening end‐to‐end delay, balancing energy consumption, and maximization of heterogeneous network lifetime, we compare our method with three approaches namely, chessboard clustering approach, PEGASIS, and LEACH. Simulation results show that the network lifetime achieved by FCC‐ABCRM could be increased by nearly 25%, 45%, and 60% more than that obtained by chessboard clustering, PEGASIS, and LEACH, respectively. Copyright © 2013 John Wiley & Sons, Ltd.     

Distributed Topology Construction in ZigBee Wireless Networks

Topology control is one of the important techniques in wireless multi-hop networks to preserve connectivity and extend the network lifetime. This is more significant in ZigBee, since the address assignment scheme is tightly coupled with topology construction. For example, there can be orphan nodes that cannot receive the network address and isolated from the network due to predefined network configurations. In this paper, we propose a distributed topology construction algorithm that controls the association time of each node in order to solve the orphan node problem in ZigBee as well as construct an efficient routing tree topology. The main idea of the distributed topology construction algorithm is to construct primary backbone nodes by propagating the invitation packets and controlling the association time based on the link quality. Since the dynamically selected primary nodes are spread throughout the network, they can provide backbone to accept the association requests from the remaining secondary nodes which are majority in a network. In the performance evaluation, we show that the proposed topology construction algorithm effectively solves the orphan node problem regardless of network density as well as provides efficient tree routing cost comparable to the approximation algorithm for degree constrained minimum routing cost tree (DC-MRCT) problem.     

An energy‐efficient utility‐based distributed data routing scheme for heterogenous sensor networks

A utility‐based distributed data routing algorithm is proposed and evaluated for heterogeneous wireless sensor networks. It is energy efficient and is based on a game‐theoretic heuristic load‐balancing approach. It runs on a hierarchical graph arranged as a tree with parents and children. Sensor nodes are considered heterogeneous in terms of their generated traffic, residual energy and data transmission rate and the bandwidth they provide to their children for communication. The proposed method generates a data routing tree in which child nodes are joined to parent nodes in an energy‐efficient way. The principles of the Stackelberg game, in which parents as leaders and children as followers, are used to support the distributive nature of sensor networks. In this context, parents behave cooperatively and help other parents to adjust their loads, while children act selfishly. Simulation results indicate the proposed method can produce on average more load‐balanced trees, resulting in over 30% longer network lifetime compared with the cumulative algorithm proposed in the literature. Copyright © 2014 John Wiley & Sons, Ltd.     

Weighted Steiner Connected Dominating Set and its Application to Multicast Routing in Wireless MANETs

In this paper, we first propose three centralized learning automata-based heuristic algorithms for approximating a near optimal solution to the minimum weight Steiner connected dominating set (WSCDS) problem. Finding the Steiner connected dominating set of the network graph is a promising approach for multicast routing in wireless ad-hoc networks. Therefore, we present a distributed implementation of the last approximation algorithm proposed in this paper (Algorithm III) for multicast routing in wireless mobile ad-hoc networks. The proposed WSCDS algorithms are compared with the well-known existing algorithms and the obtained results show that Algorithm III outperforms the others both in terms of the dominating set size and running time. Our simulation experiments also show the superiority of the proposed multicast routing algorithm over the best previous methods in terms of the packet delivery ratio, multicast route lifetime, and end-to-end delay.