Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility

The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by further involving sink mobility. As most proposals give their evidence of lifetime improvement through either (small-scale) field tests or numerical simulations on rather arbitrary cases, a theoretical understanding of the reason for this improvement and the tractability of the joint optimization problem is still missing. In this paper, we build a framework for investigating the joint sink mobility and routing problem by constraining the sink to a finite number of locations. We formally prove the NP-hardness of the problem. We also investigate the induced subproblems. In particular, we develop an efficient primal-dual algorithm to solve the subproblem involving a single sink, then we generalize this algorithm to approximate the original problem involving multiple sinks. Finally, we apply the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggest the desirable moving traces of a sink.

A Unified Framework for Joint Sink Mobility and Routing to Increase the Lifetime of Wireless Sensor Networks

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by further involving sink mobility. As most proposals give their evidence of lifetime improvement through either (small-scale) field tests or numerical simulations on rather arbitrary cases, a theoretical understanding of the reason for this improvement and the tractability of the joint optimization problem is still missing. In this paper, we build a unified framework for investigating the joint sink mobility and routing problem. We formally prove the NP-hardness of the problem. We also investigate the induced sub-problems. In particular, we develop an efficient interior point algorithm to solve the sub-problem involving a single sink, then we generalize this algorithm to approximate the original problem. Finally, we apply the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggest the desirable moving traces of a sink.

2008

Network Resource Allocation for Competing Multiple Description Transmissions

Suhas Diggavi

Providing real-time multimedia services over a best-effort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

2008

A distributed minimum-distortion routing algorithm with in-network data processing

Ramin Khalili

In many wired and wireless networks, nodes process input traffic to satisfy a network constraint (e.g., a capacity constraint) and to increase the utility of data in the output flows given these constraints. In this paper we focus on the special case in which data processing is applied to satisfy capacity constraints. This occurs when the sum of the rate of the input traffic at a node exceeds the sum of the capacity of its output links, or in a more general case, when the sum of the input rates is larger than any cut capacity in the network. In this case, nodes process data to decrease the output flow rate. This decrease from input rate to output rate distorts the transmitted data, which we characterize by a distortion metric. We show that the distortion cost of distributively processing input traffic in a network can be written as the sum of the distortion at individual nodes.. We present a distributed algorithm for a data-gathering network with many sources and a data sink that routes traffic and performs in-network data processing to minimize the distortion cost. In this algorithm, each node determines its routing table based on gradient information from neighboring nodes.

2008