On combining network coding with duty-cycling in flood-based wireless sensor networks

Network coding and duty-cycling are two major techniques for saving energy in wireless sensor networks. To the best of our knowledge, the idea to combine these two techniques for even more aggressive energy savings, has not been explored. This is not unusual, since these two techniques achieve energy efficiency through conflicting means, e.g., network coding saves energy by exploiting overhearing (i.e., nodes are awake), whereas duty-cycling saves energy by reducing idle listening (i.e., nodes sleep). In this article, we thoroughly investigate if network coding and duty cycling can be used together for more aggressive energy savings in flood-based wireless sensor networks.Our main idea is to exploit the redundancy sometimes present in flooding applications that use network coding, and put a node to sleep (i.e., duty cycle) when a redundant transmission takes place (i.e., the node has already received and successfully decoded a sequence of network-coded packets). We propose a scheme, called DutyCode, in which a multiple access control (MAC) protocol implements packet streaming and allows the network coding-aware application to decide when a node can sleep. We also present an algorithm for deciding the optimal coding scheme for a node to further reduce energy consumption by minimizing redundant packet transmissions. Finally, we propose an adaptive switching technique between DutyCode and an existing duty-cycling MAC protocol. We investigate our proposed solutions analytically and implement them on mote hardware. Our performance evaluation results, obtained from a 42-node indoor testbed, show that our scheme saves 30–46% more energy than network coding-based solutions.     

Maximum lifetime routing in wireless sensor networks

A routing problem in static wireless ad hoc networks is considered as it arises in a rapidly deployed, sensor based, monitoring system known as the wireless sensor network. Information obtained by the monitoring nodes needs to be routed to a set of designated gateway nodes. In these networks, every node is capable of sensing, data processing, and communication, and operates on its limited amount of battery energy consumed mostly in transmission and reception at its radio transceiver. If we assume that the transmitter power level can be adjusted to use the minimum energy required to reach the intended next hop receiver then the energy consumption rate per unit information transmission depends on the choice of the next hop node, i.e., the routing decision. We formulate the routing problem as a linear programming problem, where the objective is to maximize the network lifetime, which is equivalent to the time until the network partition due to battery outage. Two different models are considered for the information-generation processes. One assumes constant rates and the other assumes an arbitrary process. A shortest cost path routing algorithm is proposed which uses link costs that reflect both the communication energy consumption rates and the residual energy levels at the two end nodes. The algorithm is amenable to distributed implementation. Simulation results with both information-generation process models show that the proposed algorithm can achieve network lifetime that is very close to the optimal network lifetime obtained by solving the linear programming problem.     

Communication-efficient implementation of join in sensor networks

A sensor network is a multi-hop wireless network of sensor nodes cooperatively solving a sensing task. Each sensor node generates data items that are readings obtained from one or more sensors on the node. This makes a sensor network similar to a distributed database system. While this view is somewhat traditional, efficient execution of database (SQL) queries in sensor network remains a challenge, due to the unique characteristics of such networks such as limited memory and battery energy on individual nodes, multi-hop communication, unreliable infrastructure, and dynamic topology. Since the nodes are battery powered, the sensor network relies on energy-efficiency (and hence, communication efficiency) for a longer lifetime of the network.In this article, we have addressed the problem of communication-efficient implementation of the SQL “join” operator in sensor networks. In particular, we design an optimal algorithm for implementation of a join operation in dense sensor networks that provably incurs minimum communication cost under some reasonable assumptions. Based on the optimal algorithm, we design a suboptimal heuristic that empirically delivers a near-optimal join implementation strategy and runs much faster than the optimal algorithm. Through extensive simulations on randomly generated sensor networks, we show that our techniques achieve significant energy savings compared to other simple approaches.     

A comparative study of distributed frequency assignment algorithms for wireless sensor networks

Wireless sensor networks are composed of energy constrained nodes embedding limited transmission, processing and sensing capabilities. The main research efforts in this area sought to prolong the network lifetime by reducing energy consumption of network operations. Data gathering mechanisms such as clustering have been shown to achieve significant energy savings. However, such benefits can be obtained only if neighboring clusters operate on different frequencies (channels). As the salient characteristics of wireless sensor networks favor a distributed approach, we analyze the performance of several distributed frequency assignment algorithms with a focus on energy consumption. In this context, we find that a heuristic may achieve better results than backtracking-based algorithms.     

Software agent-based directed diffusion in wireless sensor network

In an environment where node density is massive, placement is heterogeneous and redundant sensory traffic is produced; limited network resources such as bandwidth and energy are hastily consumed by individual sensor nodes. Equipped with only a limited battery power supply, this minimizes the lifetime of these sensor nodes. At the network layer, many researchers have tackled this issue by proposing several energy efficient routing schemes. All these schemes tend to save energy by elevating redundant data traffic via in-network processing and choosing empirically good and shortest routing paths for transfer of sensory data to a central location (sink) for further, application-specific processing. Seldom has an attempt been made to reduce network traffic by moving the application-specific code to the source nodes. We unmitigated our efforts to augment the node lifetime within a sensor network by introducing mobile agents. These mobile agents can be used to greatly reduce communication costs, especially over low bandwidth links, by moving the processing function to the data rather than bringing the data to a central processor. Toward this end, we propose an agent-based directed diffusion approach to increase sensor node efficiency and we present the experimental results.     

FLIP: A Flexible Interconnection Protocol for Heterogeneous Internetworking

This paper describes the Flexible Interconnection Protocol, or FLIP, whose main goal is to allow interconnection of heterogeneous devices with varying power, processing, and communication capabilities, ranging from simple sensors to more powerful computing devices such as laptops and desktops. The vision is that FLIP will be used to interconnect such devices forming clouds in the farthest branches/leaves of the Internet, while still providing connectivity with the existing IP-based Internet infrastructure. Through its flexible, customizable headers FLIP integrates just the functions required by a given application and that can be handled by the underlying device. Simple devices like sensors will benefit from incurring close to optimal overhead saving not only bandwidth, but, more importantly, energy. More sophisticated devices in the cloud can be responsible for implementing more complex functions like reliable/ordered data delivery, communication with other device clouds and with the IP infrastructure.FLIP is designed to provide a basic substrate on which to build network- and transport-level functionality. In heterogeneous environments, FLIP allows devices with varying capabilities to coexist and interoperate under the same network infrastructure. We present the basic design of FLIP and describe its implementation under Linux. We also report on FLIP's performance when providing IPv4 and IPv6 as well as transport-layer functionality a la TCP and UDP. We show FLIP's energy efficiency in different sensor network scenarios. For example, we use FLIP to implement the directed diffusion communication paradigm and obtain an improvement of 50% in energy savings over an existing directed diffusion implementation. Finally, we showcase FLIP's flexibility by demonstrating its ability to incorporate new protocol functions seamlessly. In particular, we add data aggregation functionality onto FLIP and show that it significantly increases the system's energy efficiency.     

Spatial Model for Energy Burden Balancing and Data Fusion in Sensor Networks Detecting Bursty Events

In this paper, we propose a stochastic geometric model to study the energy burdens seen in a large scale hierarchical sensor network. The network makes use of aggregation nodes, for compression, filtering, and/or data fusion of locally sensed data. Aggregation nodes (AGNs) then relay the traffic to mobile sinks. While aggregation may substantially reduce the overall traffic on the network, it may have the deleterious effect of concentrating loads on paths between AGNs and the sinks-such inhomogeneities in the energy burden may in turn lead to nodes with depleted energy reserves. To remedy this problem, we consider how one might achieve a more balanced energy burden across the network by spreading traffic, i.e., using a multiplicity of paths between AGNs and sinks. The proposed model reveals, how various aspects of the task at hand impact the characteristics of energy burdens on the network and in turn the lifetime for the system. We show that the scale of aggregation and degree of spreading can be optimized. Additionally, if the sensing activity involves large amounts of data flowing to sinks, then inhomogeneities in the energy burdens seen by nodes around the sinks will be hard to overcome, and indeed the network appears to scale poorly. By contrast, if the sensed data is bursty in space and time, then one can reap substantial benefits from aggregation and balancing.     

Cooperative Routing in Static Wireless Networks

We study the problem of transmission-side diversity and routing in a static wireless network. It is assumed that each node in the network is equipped with a single omnidirectional antenna and that multiple nodes are allowed to coordinate their transmissions in order to obtain energy savings. We derive analytical results for achievable energy savings for both line and grid network topologies. It is shown that the energy savings of and are achievable in line and grid networks with a large number of nodes, respectively. We then develop a dynamic-programming-based algorithm for finding the optimal route in an arbitrary network, as well as suboptimal algorithms with polynomial complexity. We show through simulations that these algorithms can achieve average energy savings of about in random networks, as compared to the noncooperative schemes.     

Improving Energy Efficiency of Centrally Controlled Wireless Data Networks

Wireless network access protocols can assist nodes to conserve energy by identifying when they can enter low energy states. The goal is to put all nodes not involved in a transmission into the doze state. However, in doing so, one must tradeoff the energy and other costs associated with the overhead of coordinating dozing with the energy savings of putting nodes to sleep. In this paper, we define three alternative directory protocols that may be used by a central node to coordinate the transmission of data and the dozing of nodes. We attempt to optimize their performance by using scheduling and protocol parameter tuning. In addition, we consider the impact of errors and error recovery methods on energy consumption. Although one can argue that carefully scheduling transmissions will improve performance, ultimately, appropriately tuning protocols reduces scheduling's significance. In most cases, scheduling transmissions between the same nodes contiguously and ordering such transmissions shortest processing time first results in good performance. The most critical feature that contributes to an access protocol's effectiveness is its ability to minimize the time it takes to inform nodes that they may doze. However, the ability of our protocols to conserve energy is highly dependent on (1) network size, (2) traffic type (e.g., down/uplink, and peer-to-peer) and (3) channel bit error rate. In particular, we show that when protocols are faced with packet errors, more elaborate schemes to coordinate the dozing of nodes can pay-off. We conclude by recommending an energy conserving implementation of the IEEE 802.11 Point Coordination Function.     

A new wireless network medium access protocol based on cooperation

In this paper, we propose a new media access protocol for wireless networks, that due to its ability to resolve collisions can achieve high throughput. We view the wireless network as a spatially distributed antenna with antenna elements linked via the wireless channel. When there is a collision, the collided packets are saved in a buffer. In the slots following the collision, a set of nodes designated as nonregenerative relays retransmit the signal that they received during the collision slot. By processing the originally collided packets and the signals forwarded by the relays, the destination node can recover the original packets. The proposed scheme maintains the benefits of ALOHA systems, i.e., needs no scheduling overhead and is suitable for bursty sources, such as multimedia sources. It also offers the benefits of multi-antenna systems, i.e., spatial diversity while employing a single transmit/receive antenna at each node. Spatial diversity enables it to be robust to the wireless channel. The proposed approach achieves higher throughput and energy savings than existing techniques that allow for multiple packet reception.     

Modulation aware cluster size optimisation in wireless sensor networks

Wireless sensor networks (WSNs) play a great role because of their numerous advantages to the mankind. The main challenge with WSNs is the energy efficiency. In this paper, we have focused on the energy minimisation with the help of cluster size optimisation along with consideration of modulation effect when the nodes are not able to communicate using baseband communication technique. Cluster size optimisations is important technique to improve the performance of WSNs. It provides improvement in energy efficiency, network scalability, network lifetime and latency. We have proposed analytical expression for cluster size optimisation using traditional sensing model of nodes for square sensing field with consideration of modulation effects. Energy minimisation can be achieved by changing the modulation schemes such as BPSK, 16-QAM, QPSK, 64-QAM, etc., so we are considering the effect of different modulation techniques in the cluster formation. The nodes in the sensing fields are random and uniformly deployed. It is also observed that placement of base station at centre of scenario enables very less number of modulation schemes to work in energy efficient manner but when base station placed at the corner of the sensing field, it enable large number of modulation schemes to work in energy efficient manner.     

The encoding complexity of network coding

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group includes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h/sup 3/k/sup 2/. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h/sup 3/k/sup 2/. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require /spl Omega/(h/sup 2/k) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B+1)h/sup 3/k/sup 2/, where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an /spl Nscr/P-hard problem.     

Routing techniques in wireless sensor networks: a survey

Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state-of-the-art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location-based routing. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent-based depending on the protocol operation. We study the design trade-offs between energy and communication overhead savings in every routing paradigm. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.     

Using mobile robots to harvest data from sensor fields - [wireless communications in networked robotics]

We explore synergies among mobile robots and wireless sensor networks in environmental monitoring through a system in which robotic data mules collect measurements gathered by sensing nodes. A proof-of-concept implementation demonstrates that this approach significantly increases the lifetime of the system by conserving energy that the sensing nodes otherwise would use for communication.     

CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks

One of the most important issues for wireless sensor networks is to get a long network lifetime without affecting either communication connectivity or sensing coverage. Many sensors that are deployed randomly in a dense sensor network in a redundant way waste a lot of energy. One effective way to save energy is to let only a subset of sensors work at any given time. In this paper, we mainly consider such a problem. Selecting the minimum number of connected sensor nodes that can provide k-coverage (k ≥ 1), i.e., selecting a subset S of working sensors, such that almost every point in the sensing region can be covered by at least k sensors and the sensors in S can form a connected communication subgraph. We propose a connected k-coverage working sets construction algorithm (CWSC) based on Euclidean distance to k-cover the sensing region while minimizing the number of working sensors. CWSC can produce different coverage degrees according to different applications, which can enhance the flexibility of the sensor network. Simulation results show that the proposed algorithm, which can conserve energy and prolong the lifetime of the sensor network, is better than the previous algorithms.     

A probabilistic algorithm for efficient and robust data propagation in wireless sensor networks

We study the problem of data propagation in sensor networks, comprised of a large number of very small and low-cost nodes, capable of sensing, communicating and computing. The distributed co-operation of such nodes may lead to the accomplishment of large sensing tasks, having useful applications in practice. We present a new protocol for data propagation towards a control center (“sink”) that avoids flooding by probabilistically favoring certain (“close to optimal”) data transmissions. Motivated by certain applications (see [I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Journal of Computer Networks 38 (2002) 393–422], [C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, in: 6th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2000), 2000, pp. 56–67]) and also as a starting point for a rigorous analysis, we study here lattice-shaped sensor networks. We however show that this lattice shape emerges even in randomly deployed sensor networks of sufficient sensor density. Our work is inspired and builds upon the directed diffusion paradigm of [C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, in: 6th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2000), 2000, pp. 56–67].This protocol is very simple to implement in sensor devices, uses only local information and operates under total absence of co-ordination between sensors. We consider a network model of randomly deployed sensors of sufficient density. As shown by a geometry analysis, the protocol is correct, since it always propagates data to the sink, under ideal network conditions (no failures). Using stochastic processes, we show that the protocol is very energy efficient. Also, when part of the network is inoperative, the protocol manages to propagate data very close to the sink, thus in this sense it is robust. We finally present and discuss large-scale simulation findings validating the analytical results.     

传感器网络中基于时空相关性的压缩感知算法

传感器网络节点的能量有限,为节省传感器节点的能耗,提出了利用节点内及节点间的时空相关性的压缩感知模型及算法,减少了通信的数据量,进一步节省了能耗,延长了网络的生命周期。算法在分簇协议和多跳路由优化的基础上,在簇头节点运用较为简单的压缩感知压缩测量方法,降低了计算复杂度。通过对实测数据的误差分析及能耗仿真,验证了该模型及算法的有效性和实用性。     

Exploiting Reactive Mobility for Collaborative Target Detection in Wireless Sensor Networks

Recent years have witnessed the deployments of wireless sensor networks in a class of mission-critical applications such as object detection and tracking. These applications often impose stringent Quality-of-Service requirements including high detection probability, low false alarm rate, and bounded detection delay. Although a dense all-static network may initially meet these Quality-of-Service requirements, it does not adapt to unpredictable dynamics in network conditions (e.g., coverage holes caused by death of nodes) or physical environments (e.g., changed spatial distribution of events). This paper exploits reactive mobility to improve the target detection performance of wireless sensor networks. In our approach, mobile sensors collaborate with static sensors and move reactively to achieve the required detection performance. Specifically, mobile sensors initially remain stationary and are directed to move toward a possible target only when a detection consensus is reached by a group of sensors. The accuracy of final detection result is then improved as the measurements of mobile sensors have higher Signal-to-Noise Ratios after the movement. We develop a sensor movement scheduling algorithm that achieves near-optimal system detection performance under a given detection delay bound. The effectiveness of our approach is validated by extensive simulations using the real data traces collected by 23 sensor nodes.     

A Mobility-Prediction-Based Relay Deployment Framework for Conserving Power in MANETs

There has been a growing interest in designing mobile systems consisting of special relay nodes whose mobility can be controlled by the underlying network. In this paper, we consider the design of a heterogeneous mobile ad hoc network (MANET) consisting of two kinds of mobile nodes-traditional nodes with limited energy and a few controllable mobile relay nodes with relatively abundant energy resources. We propose a novel relay deployment framework that utilizes mobility prediction and works in tandem with the underlying MANET routing protocol to optimally define the movement of the relay nodes. We present two instances of the relay deployment problem, together with the solutions, to achieve different goals. Instance 1, termed Min-Total, aims to minimize the total energy consumed across all the traditional nodes during data transmission, while instance 2, termed Min-Max, aims to minimize the maximum energy consumed by a traditional node during data transmission. Our solutions also enable the prioritization of individual nodes in the network based on residual energy profiles and contextual significance. We perform an extensive simulation study to understand the trade-offs involved in deploying an increasing fraction of such relay nodes in the network. We also investigate the performance of the proposed framework under different mobility prediction schemes. Results indicate that even when the relay nodes constitute a small fraction of the total nodes in the network, the proposed framework results in significant energy savings. Further, we observed that while both the schemes have their potential advantages, the differences between the two optimization schemes are clearly highlighted in a sparse network.     

Energy-aware wireless systems with adaptive power-fidelity tradeoffs

Wireless networked embedded systems, such as multimedia terminals, sensor nodes, etc., present a rich domain for making energy/performance/quality tradeoffs based on application needs, network conditions, etc. Energy awareness in these systems is the ability to perform tradeoffs between available battery energy and application quality requirements. In this paper, we show how operating system directed dynamic voltage scaling and dynamic power management can provide for such a capability. We propose a real-time scheduling algorithm that uses runtime feedback about application behavior to provide adaptive power-fidelity tradeoffs. We demonstrate our approach in the context of a static priority-based preemptive task scheduler. Simulation results show that the proposed algorithm results in significant energy savings compared to state-of-the-art dynamic voltage scaling schemes with minimal loss in system fidelity. We have implemented our scheduling algorithm into the eCos real-time operating system running on an Intel XScale-based variable voltage platform. Experimental results obtained using this platform confirm the effectiveness of our technique