Power-efficient and interference-free link scheduling algorithms for connected wireless sensor networks

A fundamental aspect in performance engineering of wireless sensor networks (WSN) is optimizing the set of links that can be concurrently activated to meet a given signal-to-interference-plus-noise ratio (SINR) threshold. The solution of this combinatorial problem is a key element in wireless link scheduling. Another key architectural goal in WSN is connectivity. The connectivity of sensor nodes is critical for WSN, as connected graphs can be used for both data collection and data dissemination. In this paper, we investigate the joint scheduling and connectivity problem in WSN assuming the SINR model. We propose algorithms to build connected communication graphs with power-efficient links to be scheduled simultaneously in one time slot. The algorithms aiming at minimizing the number of time slots needed to successfully schedule all the given links such that the nodes can communicate without interference in the SINR model. While power-efficient and interference-free schedules reduce energy consumption, minimization of the schedule length (shortest link scheduling) has the effect of maximizing network throughput. We propose one greedy randomized constructive heuristic, two local search procedures, and three greedy randomized adaptive search procedures metaheuristics. We report computational experiments comparing the effectiveness of the proposed algorithms. Our simulation also shows the trade-off between power consumption and schedule length and the results indicate that not only the overall performance of our algorithms, but also show that the total power and schedule length value of its solutions are better than the existing work.

     

Performance evaluation of sensor deployment using optimization techniques and scheduling approach for K-coverage in WSNs

In the wireless sensor networks, sensor deployment and coverage are the vital parameter that impacts the network lifetime. Network lifetime can be increased by optimal placement of sensor nodes and optimizing the coverage with the scheduling approach. For sensor deployment, heuristic algorithm is proposed which automatically adjusts the sensing range with overlapping sensing area without affecting the high degree of coverage. In order to demonstrate the network lifetime, we propose a new heuristic algorithm for scheduling which increases the network lifetime in the wireless sensor network. Further, the proposed heuristic algorithm is compared with the existing algorithms such as ant colony optimization, artificial bee colony algorithm and particle swarm optimization. The result reveals that the proposed heuristic algorithm with adjustable sensing range for sensor deployment and scheduling algorithm significantly increases the network lifetime.     

Fault-tolerant monitor placement for out-of-band wireless sensor network monitoring

Monitoring a sensor network to quickly detect faults is important for maintaining the health of the network. Out-of-band monitoring, i.e., deploying dedicated monitors and transmitting monitoring traffic using a separate channel, does not require instrumenting sensor nodes, and hence is flexible (can be added on top of any application) and energy conserving (not consuming resources of the sensor nodes). In this paper, we study fault-tolerant out-of-band monitoring for wireless sensor networks. Our goal is to place a minimum number of monitors in a sensor network so that all sensor nodes are monitored by k distinct monitors, and each monitor serves no more than w sensor nodes. We prove that this problem is NP-hard. For small-scale network, we formulate the problem as an Integer Linear Programming (ILP) problem, and obtain the optimal solution. For large-scale network, the ILP is not applicable, and we propose two algorithms to solve it. The first one is a ln(kn) approximation algorithm, where n is the number of sensor nodes. The second is a simple heuristic scheme that has much shorter running time. We evaluate our algorithms using extensive simulation. In small-scale networks, the latter two algorithms provide results close to the optimal solution from the ILP for relatively dense networks. In large-scale networks, the performance of these two algorithms are similar, and for relatively dense networks, the number of monitors required by both algorithms is close to a lower bound.     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

Energy efficient path selection for mobile sink and data gathering in wireless sensor networks

Mobile sink (MS) has drawn significant attention for solving hot spot problem (also known as energy hole problem) that results from multihop data collection using static sink in wireless sensor networks (WSNs). MS is regarded as a potential solution towards this problem as it significantly reduces energy consumption of the sensor nodes and thus enhances network lifetime. In this paper, we first propose an algorithm for designing efficient trajectory for MS, based on rendezvous points (RPs). We next propose another algorithm for the same problem which considers delay bound path formation of the MS. Both the algorithms use k-means clustering and a weight function by considering several network parameters for efficient selection of the RPs by ensuring the coverage of the entire network. We also propose an MS scheduling technique for effective data gathering. The effectiveness of the proposed algorithms is demonstrated through rigorous simulations and comparisons with some of the existing algorithms over several performance metrics.     

Optimal load balanced clustering in homogeneous wireless sensor networks

Balancing the load among sensor nodes is a major challenge for the long run operation of wireless sensor networks. When a sensor node becomes overloaded, the likelihood of higher latency, energy loss, and congestion becomes high. In this paper, we propose an optimal load balanced clustering for hierarchical cluster‐based wireless sensor networks. We formulate the network design problem as mixed‐integer linear programming. Our contribution is 3‐fold: First, we propose an energy aware cluster head selection model for optimal cluster head selection. Then we propose a delay and energy‐aware routing model for optimal inter‐cluster communication. Finally, we propose an equal traffic for energy efficient clustering for optimal load balanced clustering. We consider the worst case scenario, where all nodes have the same capability and where there are no ways to use mobile sinks or add some powerful nodes as gateways. Thus, our models perform load balancing and maximize network lifetime with no need for special node capabilities such as mobility or heterogeneity or pre‐deployment, which would greatly simplify the problem. We show that the proposed models not only increase network lifetime but also minimize latency between sensor nodes. Numerical results show that energy consumption can be effectively balanced among sensor nodes, and stability period can be greatly extended using our models.     

Design and analysis of asynchronous wakeup for wireless sensor networks

In wireless sensor networks, scheduling the sleep duration of each node is one of the key elements for controlling critical performance metrics such as energy consumption and latency. Since the wakeup interval is a primary parameter for determining the sleeping schedule, how to tune the wakeup interval is crucial for the overall network performance. In this paper, we present an effective framework for tuning asynchronous wakeup intervals of IEEE 802.15.4 sensor networks from the energy consumption viewpoint. First, we derive an energy consumption model of each node as an explicit function of the wakeup interval, and empirically validate the derived model. Second, based on the proposed model, we formulate the problem of tuning the wakeup interval with the following two objectives: to minimize total energy consumption and to maximize network lifetime. We show that these two problems can be optimally solved by an iterative algorithm with global information by virtue of the convexity of the problem structure. Finally, as practical solutions, we further propose heuristic optimization algorithms that only exploit local information. In order to develop heuristic algorithms, we propose two broadcasting schemes, which are entitled as maximum wakeup interval broadcasting and efficient local maximum broadcasting. These broadcasting algorithms enable nodes in the network to have heterogeneous wakeup intervals.     

Energy-aware scheduling with probabilistic deadline constraints in wireless networks

In a shared-medium wireless network, an effective technique that allows for a tradeoff of message transmission time for energy savings is to transmit messages over multiple smaller hops as opposed to using the long direct source-destination hop. In this context, we address the problem of scheduling messages with probabilistic deadline constraints. Unlike most other works in this area, we consider the practical aspects of the erroneous channel condition and the receiver energy consumption while solving the scheduling problem. Our solution is three fold – first we prove that the problem is NP-hard. We then present an Integer Linear Program (ILP) formulation for the scheduling problem. Finally, we present efficient heuristic scheduling algorithms which minimize the energy consumption while providing the required guarantees. Our simulation studies show that the proposed heuristic algorithms achieve energy savings comparable to that obtained using the linear programming methodology under practical channel conditions.     

An energy‐efficient node‐scheduling scheme for wireless sensor networks based on minimum dominating sets

One of the major requirements for new wireless sensor networks is to extend the lifetime of the network. Node‐scheduling techniques have been used extensively for this purpose. Some existing approaches rely mainly on location information through global positioning system (GPS) devices for designing efficient scheduling strategies. However, integration of GPS devices with sensor nodes is expensive and increases the cost of deployment dramatically. In this paper we present a location‐free solution for node scheduling. Our scheme is based on a graph theoretical approach using minimum dominating sets. We propose a heuristic to extract a collection of dominating sets. Each set consists of a group of working nodes which ensures a high level of network coverage. At each round, one set is responsible for covering the sensor field while the nodes in other sets are in sleep mode. We evaluate our solution through simulations and discuss our future research directions. Copyright © 2008 John Wiley & Sons, Ltd.     

Achieving energy‐neutral data transmission by adjusting transmission power for energy‐harvesting wireless sensor networks

Recently, benefiting from rapid development of energy harvesting technologies, the research trend of wireless sensor networks has shifted from the battery‐powered network to the one that can harvest energy from ambient environments. In such networks, a proper use of harvested energy poses plenty of challenges caused by numerous influence factors and complex application environments. Although numerous works have been based on the energy status of sensor nodes, no work refers to the issue of minimizing the overall data transmission cost by adjusting transmission power of nodes in energy‐harvesting wireless sensor networks. In this paper, we consider the optimization problem of deriving the energy‐neutral minimum cost paths between the source nodes and the sink node. By introducing the concept of energy‐neutral operation, we first propose a polynomial‐time optimal algorithm for finding the optimal path from a single source to the sink by adjusting the transmission powers. Based on the work earlier, another polynomial‐time algorithm is further proposed for finding the approximated optimal paths from multiple sources to the sink node. Also, we analyze the network capacity and present a near‐optimal algorithm based on the Ford–Fulkerson algorithm for approaching the maximum flow in the given network. We have validated our algorithms by various numerical results in terms of path capacity, least energy of nodes, energy ratio, and path cost. Simulation results show that the proposed algorithms achieve significant performance enhancements over existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.     

能量采集型无线传感器网络的高能效路由算法

在能量采集型无线传感器网络中,虽然有能量吸收,但是因能量依然非常珍贵,如何优化路由协议,提高能量利用率,延长网络寿命仍然是值得研究的问题.为求解高能效的路由,提出了一种采用遗传算法的高能效路由算法,建立考虑节点的吸收能量、剩余能量、消耗能量和浪费能量的适应函数,用遗传算法寻找全局最优路径.将该适应函数与3种其他适应函数作对比,其他3种适应函数分别为只考虑路径能耗最小的适应函数,考虑路径能耗与路径上节点的吸收能量、剩余能量的适应函数以及考虑路径能耗与网络中所有节点的浪费能量的适应函数.采用遗传算法解出4种路由,通过仿真分析可知,所提出的路由算法能量利用效率最高.     

A myopic mobile sink migration strategy for maximizing lifetime of wireless sensor networks

Network lifetime maximization is challenging particularly for large-scale wireless sensor networks. The sensor nodes near the sink node tend to suffer high energy consumption due to heavy traffic relay operations, becoming vulnerable to energy depletion. The rationale of the sink mobility approach is that as the sink node moves around, such risk of energy depletion at some nodes can be alleviated. In this paper, we first obtain the optimal mobile sink sojourning pattern by solving a linear programming model and then we mathematically analyze why the optimal solution exhibits such sojourning pattern. We use the insights from this analysis to design a simple practical heuristic algorithm for sink mobility, which utilizes only local information. Our heuristic is very different from the existing algorithms which often use the traffic volume as the main decision factor, in that we consider the variance of residual energy of neighboring sensor nodes. The simulation results show that our scheme achieves near-optimal network lifetime even with the relatively low moving speed of the mobile sink.     

MR-MC无线传感器网络最小延迟数据聚集调度研究

单radio单信道无线传感器网络的最小延迟聚集调度是一个NPC问题,已提出许多解决方案。在多radio多信道网络中,节点可以同时接收多个不同节点传输的数据,降低延迟。基于上述特点,考虑树结构约束,时槽、信道和radio分配等约束条件,将多radio多信道无线传感器网络最小延迟聚集调度问题定义为一个优化问题,并分解为建立聚集树和节点调度2个子问题,针对这2个子问题分别提出启发式算法。实验结果表明,提出的算法具有良好的性能。     

Heuristic approach for broadcast scheduling,problem in wireless mesh networks

Disasters can be natural and human-initiated events that interrupt the usual functioning of people on a large scale. Region where disasters have occurred causes hazards to the public of that area and to the rescue teams. Disaster causes the damage to the communication network infrastructure also. Once the communication infrastructure is damaged, it is very difficult to the rescue teams to actively involve in relief operation. To handle these hazards, different wireless technologies can be initiated in the area of disaster. This paper discusses the innovative wireless technology for disaster management. Specifically, issues related to the broadcast scheduling problem in wireless mesh network is deployed efficiently during disaster relief are discussed. A domain specific memetic algorithm is proposed for solving the optimum time division multiple access broadcast scheduling problem in wireless mesh networks. The aim is to increase the total number of transmissions in optimized time slot with high channel utilization in a less computation time. Simulation results showed that our memetic algorithm approach to this problem achieves 100% convergence to solutions within reduced computation time while compared to recent efficient algorithms. The results were compared with several heuristic and non-heuristic algorithms for broadcast scheduling problem.     

Power-Saving Scheduling for Multiple-Target Coverage in Wireless Sensor Networks

We address the multiple-target coverage problem (MTCP) in wireless sensor networks (WSNs). We also propose an energy-efficient sensor-scheduling algorithm for multiple-target coverage (MTC) that considers both the transmitting energy for collected data and overlapped targets. We introduce two algorithms: one optimal, the other heuristic. Simulation results show that the proposed algorithms can contribute to extending the lifetime of network and that the heuristic algorithm is more practical than the optimal algorithm with respect to complexity.     

最小化重传次数的无线网络编码广播重传算法

提出了一种最小化重传次数的无线网络编码广播重传算法。针对无线广播网络,本文首先引入了缓存网络编码（C-IDNC）的概念,在接收端,正确接收但不能解码的网络编码数据包将被缓存起来等待将来的解码机会而不是简单的丢弃该编码包。其次,通过对基于IDNC重传策略的问题描述,分析了不同因素对重传次数的影响,并把这些影响因子量化为可度量的数值。随后,构造了IDNC图 ,用于表征所有可行编码和编码增益,并把最小化重传次数问题转化为最大权重搜寻问题,给出了寻找最优解的编码方法。同时,为降低算法复杂度和计算量,提出一种启发式的最大权重搜寻算法（CI-MWSA）。仿真结果表明,与传统方案相比,提出的策略和算法能有效提高重传效率、减少重传次数。      

Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks

In this paper, we consider the reliable broadcast and multicast lifetime maximization problems in energy‐constrained wireless ad hoc networks, such as wireless sensor networks for environment monitoring and wireless ad hoc networks consisting of laptops or PDAs with limited battery capacities. In packet loss‐free networks, the optimal solution of lifetime maximization problem can be easily obtained by tree‐based algorithms. In unreliable networks, we formulate them as min–max tree problems and prove them NP‐complete by a reduction from a well‐known minimum degree spanning tree problem. A link quality‐aware heuristic algorithm called Maximum Lifetime Reliable Broadcast Tree (MLRBT) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. The time complexity analysis of both algorithms is also provided. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distributions of error probability on lossy wireless links. Copyright © 2012 John Wiley & Sons, Ltd.     

Distributed lifetime optimization in wireless sensor networks using alternating direction method of multipliers

Due to the limited energy of sensor nodes in wireless sensor networks, extending the network lifetime is a major challenge that can be formulated as an optimization problem. In this paper, we propose a distributed iterative algorithm based on alternating direction method of multipliers with the aim of maximizing sensor network lifetime. The features of this algorithm are the use of local information, low overhead of message passing, low computational complexity, fast convergence, and, consequently, reduced energy consumption. In this study, we present the convergence results and the number of iterations required to achieve the stopping criterion. Furthermore, the impact of problem size (number of sensor nodes) on the solution and constraints violation is studied, and, finally, the proposed algorithm is compared with one of the well‐known subgradient‐based algorithms.     

基于ERPMT改进启发式方法的WSN寿命最大化算法

针对传感器节点的电池容量限制导致无线传感网络寿命低的问题,基于容量最大化(CMAX)、线上最大化寿命(OML)两种启发式方法以及高效路由能量管理技术(ERPMT),提出了基于ERPMT改进启发式方法的无线传感网络寿命最大化算法。首先,通过启发式方法初始化每个传感器节点,将节点能量划分为传感器节点起源数据和其它节点数据延迟;然后利用加入的一种优先度量延迟一跳节点的能量消耗;最后,根据路径平均能量为每个路由分配一个优先级,并通过ERPMT实现最终的无线传感网络优化。针对不同分布类型网络寿命的实验验证了本文算法的有效性及可靠性,实验结果表明,相比较为先进的启发式方法CMAX及OML,本文算法明显增大了无线传感网络的覆盖范围,并且大大地延长了网络的寿命。     

Load balancing techniques for lifetime maximizing in wireless sensor networks

Energy consumption has been the focus of many studies on Wireless Sensor Networks (WSN). It is well recognized that energy is a strictly limited resource in WSNs. This limitation constrains the operation of the sensor nodes and somehow compromises the long term network performance as well as network activities. Indeed, the purpose of all application scenarios is to have sensor nodes deployed, unattended, for several months or years.This paper presents the lifetime maximization problem in “many-to-one” and “mostly-off” wireless sensor networks. In such network pattern, all sensor nodes generate and send packets to a single sink via multi-hop transmissions. We noticed, in our previous experimental studies, that since the entire sensor data has to be forwarded to a base station via multi-hop routing, the traffic pattern is highly non-uniform, putting a high burden on the sensor nodes close to the base station.In this paper, we propose some strategies that balance the energy consumption of these nodes and ensure maximum network lifetime by balancing the traffic load as equally as possible. First, we formalize the network lifetime maximization problem then we derive an optimal load balancing solution. Subsequently, we propose a heuristic to approximate the optimal solution and we compare both optimal and heuristic solutions with most common strategies such as shortest-path and equiproportional routing. We conclude that through the results of this work, combining load balancing with transmission power control outperforms the traditional routing schemes in terms of network lifetime maximization.