Clustering wireless ad hoc networks with weakly connected dominating set

The increasing popular personal communications and mobile computing require a wireless network infrastructure that supports self-configuration and self-management. Efficient clustering protocol for constructing virtual backbone is becoming one of the most important issues in wireless ad hoc networks. The weakly connected dominating set   (WCDS) is very suitable for cluster formation. As finding the minimum WCDS in an arbitrary graph is a NP-Hard problem, we propose an area-based distributed algorithm for WCDS construction in wireless ad hoc networks with time and message complexity O(n)$O(n)$. This Area algorithm is divided into three phases: area partition, WCDS construction for each area and adjustment along the area borders. We confirm the effectiveness of our algorithm through analysis and comprehensive simulation study. The number of nodes in the WCDS constructed by this Area algorithm is up to around 50% less than that constructed by the previous well-known algorithm.     

无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。     

Distributed wireless power transfer in sensor networks with multiple Mobile Chargers

We investigate the problem of efficient wireless power transfer in wireless sensor networks. In our approach, special mobile entities (called the Mobile Chargers) traverse the network and wirelessly replenish the energy of sensor nodes. In contrast to most current approaches, we envision methods that are distributed and use limited network information. We propose four new protocols for efficient charging, addressing key issues which we identify, most notably (i) what are good coordination procedures for the Mobile Chargers and (ii) what are good trajectories for the Mobile Chargers. Two of our protocols (DC, DCLK) perform distributed, limited network knowledge coordination and charging, while two others (CC, CCGK) perform centralized, global network knowledge coordination and charging. As detailed simulations demonstrate, one of our distributed protocols outperforms a known state of the art method, while its performance gets quite close to the performance of the powerful centralized global knowledge method.     

Clustering the wireless Ad Hoc networks: A distributed learning automata approach

In Ad Hoc networks, the performance is significantly degraded as the size of the network grows. The network clustering by which the nodes are hierarchically organized on the basis of the proximity relieves this performance degradation. Finding the weakly connected dominating set (WCDS) is a promising approach for clustering the wireless Ad Hoc networks. Finding the minimum WCDS in the unit disk graph is an NP-Hard problem, and a host of approximation algorithms has been proposed. In this article, we first proposed a centralized approximation algorithm called DLA-CC based on distributed learning automata (DLA) for finding a near optimal solution to the minimum WCDS problem. Then, we propose a DLA-based clustering algorithm called DLA-DC for clustering the wireless Ad Hoc networks. The proposed cluster formation algorithm is a distributed implementation of DLA-CC, in which the dominator nodes and their closed neighbors assume the role of the cluster-heads and cluster members, respectively. In this article, we compute the worst case running time and message complexity of the clustering algorithm for finding a near optimal cluster-head set. We argue that by a proper choice of the learning rate of the clustering algorithm, a trade-off between the running time and message complexity of algorithm with the cluster-head set size (clustering optimality) can be made. The simulation results show the superiority of the proposed algorithms over the existing methods.     

An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks

The connected dominating set (CDS) is widely used as a virtual backbone in mobile ad hoc networks. Although many distributed algorithms for constructing the CDS have been proposed, nearly all of them require two or more separated phases, which may cause problems such as long delay in the later phases when the network size is large. This paper proposes a Distributed Single-Phase algorithm for constructing a connected dominating set, DSP-CDS, in ad hoc networks. The DSP-CDS is an asynchronous distributed algorithm and converges quickly in a single phase. Each node uses one-hop neighborhood information and makes a local decision on whether to join the dominating set. Each node bases its decision on a key variable, strength, which guarantees that the dominating set is connected when the algorithm converges. The rules for computing strength can be changed to accommodate different application needs. The DSP-CDS adapts well to dynamic network topologies, upon which the algorithm makes only necessary local updates to maintain the CDS of the network. The performance of the DSP-CDS can be tuned by adjusting two main parameters. Extensive simulations have demonstrated that those parameters can affect the CDS size, the CDS diameter, and number of rounds for the algorithm to converge. Comparisons with other multiple-phase CDS algorithms have shown that the DSP-CDS converges fast and generates a CDS of comparable size.     

Distributed clustering algorithms for data-gathering in wireless mobile sensor networks

One critical issue in wireless sensor networks is how to gather sensed information in an energy-efficient way since the energy is a scarce resource in a sensor node. Cluster-based architecture is an effective architecture for data-gathering in wireless sensor networks. However, in a mobile environment, the dynamic topology poses the challenge to design an energy-efficient data-gathering protocol. In this paper, we consider the cluster-based architecture and provide distributed clustering algorithms for mobile sensor nodes which minimize the energy dissipation for data-gathering in a wireless mobile sensor network. There are two steps in the clustering algorithm: cluster-head election step and cluster formation step. We first propose two distributed algorithms for cluster-head election. Then, by considering the impact of node mobility, we provide a mechanism to have a sensor node select a proper cluster-head to join for cluster formation. Our clustering algorithms will achieve the following three objectives: (1) there is at least one cluster-head elected, (2) the number of cluster-heads generated is uniform, and (3) all the generated clusters have the same cluster size. Last, we validate our algorithms through an extensive experimental analysis with Random Walk Mobility (RWM) model, Random Direction Mobility (RDM) model, and a Simple Mobility (SM) model as well as present our findings.     

Quorum and connected dominating sets based location service in wireless ad hoc, sensor and actuator networks

Location service provides position of mobile destination to source node to enable geo-routing. In existing quorum-based location service protocols, destination node registers its location along a ‘column’ while source node makes a query along a ‘row’. Grid and quorum-based location service is based on division of network into square grids, and selecting ‘leader’ location server node in each grid. Location updates, leader reelection and information transfer are performed whenever destination and leader nodes are moving to a different grid. We propose here to apply connected dominating sets (DS) as an alternative to grids. We also improved basic quorum, and applied on DS-quorum (DS based quorum) better criterion for triggering local information exchanges and global location updates, by meeting two criteria: certain distance movement and certain number of observed link changes with (DS) nodes. Backbones created by DS nodes (using 1-hop neighborhood information) are small size, do not have a parameter like grid size, and preserve network connectivity without the help of other nodes. Location updates and destination searches are restricted to backbone nodes. Both methods use ‘hello’ messages to learn neighbors. While this suffices to construct DS, grid leader (re)election requires additional messages. Simulation results show that using DS as backbone for quorum construction is superior to using grid as backbone or no backbone at all. The proposed DS-quorum location service can achieve higher (or similar) success rate with much less communication overhead than grid-based approaches.     

Distributed data source verification in wireless sensor networks

In-network data aggregation is favorable for wireless sensor networks (WSNs): It allows in-network data processing while reducing the network traffic and hence saving the sensors energy. However, due to the distributed and unattended nature of WSNs, several attacks aiming at compromising the authenticity of the collected data could be perpetrated. For example, an adversary could capture a node to create clones of the captured one. These clones disseminated through the network could provide malicious data to the aggregating node, thus poisoning/disrupting the aggregation process. In this paper we address the problem of detecting cloned nodes; a requirement to be fulfilled to provide authenticity of the data fusion process.First, we analyze the desirable properties a distributed clone detection protocol should meet. Specifically: It should avoid having a single point of failure; the load should be totally distributed across the nodes in the network; the position of the clones in the network should not influence the detection probability. We then show that current solutions do not meet the exposed requirements. Next, we propose the Information Fusion Based Clone Detection Protocol (ICD). ICD is a probabilistic, completely distributed protocol that efficiently detects clones. ICD combines two cryptographic mechanisms: The pseudo-random key pre-distribution, usually employed to secure node pairwise communications, with a sparing use of asymmetric crypto primitives. We show that ICD matches all the requirements above mentioned and compare its performance with current solutions in the literature; experimental results show that ICD has better performance than existing solutions for all the cost parameters considered: Number of messages sent, per sensor storage requirement, and signature verification. These savings allow to increase the network operating lifetime. Finally, note that ICD protocol could be used as an independent layer by any data aggregation mechanism.     

无线传感器网络分布式节点定位算法研究

深入分析比较了在无线传感器网络领域中有代表性的4种分布式定位算法,着重关注了算法的能量消耗问题。节点的能量消耗主要由计算和通讯开销组成,对于算法的计算复杂度和通讯开销,做出了定量的分析。在此基础上,对未来的研究与算法的改进提出了建议。     

Link scheduling in wireless sensor networks: Distributed edge-coloring revisited

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our algorithm consists of two phases. The first phase involves edge-coloring: an assignment of a color to each edge in the network such that no two edges incident on the same node are assigned the same color. Our main result for the first phase is a distributed edge-coloring algorithm that needs at most (Δ+1) colors, where Δ is the maximum degree of the network. To our knowledge, this is the first distributed algorithm that can edge-color a graph using at most (Δ+1) colors. The second phase uses the edge-coloring solution for link scheduling. We map each color to a unique timeslot and attempt to assign a direction of transmission along each edge such that the hidden terminal problem is avoided; an important result we obtain is a characterization of network topologies for which such an assignment exists. Next, we consider topologies for which a feasible transmission assignment does not exist for all edges, and obtain such an assignment using additional timeslots. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments, we obtain a TDMA MAC schedule which enables two-way communication between every pair of adjacent sensor nodes. For acyclic topologies, we prove that at most 2(Δ+1) timeslots are required. Results for general topologies are demonstrated using simulations; for sparse graphs, we show that the number of timeslots required is around 2(Δ+1). We show that the message and time complexity of our algorithm is O(nΔ²+n²m), where n is the number of nodes and m is the number of edges in the network. Through simulations, we demonstrate that the energy consumption of our solution increases linearly with Δ. We also propose extensions to account for non-ideal radio characteristics.     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

An interference-aware fair scheduling for multicast in wireless mesh networks

Multicast is a fundamental routing service in wireless mesh networks (WMNs) due to its many potential applications such as video conferencing, online games, and webcast. Recently, researchers proposed using link-quality-based routing metrics for finding high-throughput paths for multicast routing. However, the performance of such link-quality-based multicast routing is still limited by severe unfairness. Two major artifacts that exist in WMNs are fading which leads to low quality links, and interference which leads to unfair channel allocation in the 802.11 MAC protocol. These artifacts cause the multicast application to behave unfairly with respect to the performance achieved by the multicast receivers.     

Distributed control for energy-efficient and fast consensus in wireless sensor networks

The paper proposes a distributed control of nodes transmission radii in energy-harvesting wireless sensor networks for simultaneously coping with energy consumption and consensus responsiveness requirement. The stability of the closed-loop network under the proposed control law is proved. Simulation validations show the effectiveness of the proposed approach in nominal scenario as well as in the presence of uncertain node power requirements and harvesting system supply.     

Probabilistic analysis of upper bounds for 2-connected distance -dominating sets in graphs

A small virtual backbone which is modeled as the minimum connected dominating set (CDS) problem has been proposed to alleviate the broadcasting storm for efficiency in wireless ad hoc networks. In this paper, we consider a general fault tolerant CDS problem, called an h-connected distance k-dominating set (HCKDS) to balance high efficiency and fault tolerance, and study the upper bound for HCKDS with a probabilistic method for small h and improve the current best results.     

基于最小连通支配集的无线传感器网络容错研究

过多的跳数对于无线传感器网络容错是不利的。无线传感器网络以往的研究中最小连通支配集主要是作为骨干网来使用,通过结合度来构建最小连通支配集,使得所构建的最小连通支配集不仅具备骨干网的功能,还具有容错的作用。提出了构建具有容错作用的基于度的最小连通支配集算法,仿真证明该算法可以有效地减少无线传感器网络的跳数,从而达到增强无线传感器网络容错的目的。     

Improved algorithms for latency minimization in wireless networks

In the interference scheduling problem, one is given a set of n communication requests described by source-destination pairs of nodes from a metric space. The nodes correspond to devices in a wireless network. Each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.We introduce an instance-based measure of interference, denoted by I, that enables us to improve on previous results for the interference scheduling problem. We prove the upper and lower bounds in terms of I on the number of steps needed for scheduling a set of requests. For general power assignments, we prove a lower bound of Ω(I/(logΔlogn)) steps, where Δ denotes the aspect ratio of the metric. When restricting to the two-dimensional Euclidean space (as in the previous work) the bound improves to Ω(I/logΔ). Alternatively, when restricting to linear power assignments, the lower bound improves even to Ω(I). The lower bounds are complemented by an efficient algorithm computing a schedule for linear power assignments using only O(Ilogn) steps. A more sophisticated algorithm computes a schedule using even only O(I+log²n) steps. For dense instances in the two-dimensional Euclidean space, this gives a constant factor approximation for scheduling under linear power assignments, which shows that the price for using linear (and, hence, energy-efficient) power assignments is bounded by a factor of O(logΔ).In addition, we extend these results for single-hop scheduling to multi-hop scheduling and combined scheduling and routing problems, where our analysis generalizes the previous results towards general metrics and improves on the previous approximation factors.     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。     

Approximating minimum independent dominating sets in wireless networks

We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.     

Channel allocation in multi-channel wireless mesh networks

In this article, we survey the latest progress in multi-channel wireless mesh networks, focusing on wireless interference models and channel allocation algorithms with the goal of maximizing the network performance. We present the studies of different interference models and illustrate how they could affect the design of channel assignment. We also summarize channel allocation algorithms with different strategies in both omni-directional and directional antenna networks. We conclude that both static and dynamic channel allocation strategies have advantages and disadvantages, and the design of channel allocation algorithms strongly depends on the interference model and the assumption of network traffic.