We consider the behavior of mobile users that, upon depletion of their device's energy due to communication, can detour from their regular path, in order to reach a location where the device can be recharged. We develop abstractions of this recharging behavior and analytically derive a charging-aware mobility model. The device is viewed as a mobile node. Based on the Palm inversion formula, we derive the (integral-form) stationary probability density function of the node's location, subject to attraction exerted by one charger in a bounded convex area. The analytical and numerical results demonstrate the distortion effect the charger has on the spatial node distribution. We observe, and explain, a counter-intuitive effect whereby the node density exhibits peaks that are asymmetric, coupled with a relative decrease of the density around the charger area. In addition, we provide a method to approximate the probability density function when multiple chargers are deployed. We examine the accuracy of this approximation and comment on its limitations.

Today's mobile battery-powered communication devices require that users access chargers via wired and, recently, wireless recharging facilities. For a device departing from a location with a given energy “budget”, a plausible strategy is to seek a charger location once the energy is exhausted. We present a model of mobile nodes that captures the paths followed by the nodes with depleted energy seeking, possibly via a detour, to reach a charger. The derived location-dependent mobile node density distribution is used to express the location-dependent congestion of a wireless network whose capacity is used by the mobile nodes. The boundaries, and the relative placement of the charger, create intriguing discontinuities in the probability density function of the nodes across space. We find that chargers are not always “hotspots” in terms of node density, and that the energy budget of the nodes at the beginning of their trip impacts that density and determines the hotspot. Moreover, upon energy depletion, to detour from one's path or not, results in a distinctly different relative impact of the charger placement on the ability of nodes to sustain communication, depending, again on the energy budget the nodes have upon departure from a waypoint.

Received Signal Strength Indication (RSSI) is a notoriously noisy metric, yet attractive for localization purposes. We study the effect of reducing the RSSI value to a single bit, essentially turning the RSSI measurement into a proximity indicator. We consider systems where a device, that needs to be localized, transmits and the transmission is received by a number of receivers placed at fixed and known locations. We consider two modes of 1-bit quantization: one (global) where the quantization is defined uniformly across all signal receivers, and one (local) where the RSSI is quantized separately for each receiver. We compare the effects of 1-bit quantization across three profiling k-NN-based localization algorithms, comparing them with each other in addition to comparing against results when no quantization is performed. We furthermore consider the case of global 2-bit quantization. Our study is based on profiling data collected before and after modifications were performed to the profiled environment, allowing us to also study the impact of those changes. Our results show comparable performance between no quantization and local 1-bit quantization, and similar results for global 2-bit quantization.

Recently remarkable progress has been made on the development of wireless charging technologies. Their augmentation to Intermittently Connected Mobile ad hoc Networks (ICMNs) can boost the network performance with the benefit of elongated nodal lifespans. This benefit, however, is also accompanied by new potential challenges for protocol designers, as the mobile nodes can assume unconventionally dynamic, heterogeneous, and interdependent movement patterns due to dis/charging processes. The interplay between mobility, energy, and communication can skew the efficacy of existing routing protocols. In this paper, we devise a series of grid-based mobility models to mimic the possible charging-aware moving behaviors of wirelessly chargeable ICMNs that are assisted by renewable charging resources. Properties of the mobility models are investigated through simulation with classic routing protocols for ICMNs (i.e. epidemic routing and randomized flooding). Results show that the charging-aware mobility can enable the nodes to maintain high energy and good packet delivery ratios, depending on the aggressiveness of transmission and distribution of chargers.

Received Signal Strength Indication (RSSI) measurements are known to be noisy and to exhibit high degree of variability, yet massive sets of RSSI data are streamed and collected with the purpose of using them for localization. In this paper we determine that the full resolution of RSSI measurements is unnecessary and propose, based on an evaluation of indoor localization experiments, a technique of modest computational effort, using Genetic Algorithms, to determine how to best quantize RSSI measurements. Our approach treats the localization algorithm as a “black box” and, hence, its applicability is broad. However, for the purpose of exposition and to generate absolute performance metrics, a particular profiling-based localization algorithm is used. Results from experiments involving real collected RSSI values indicate that it is possible to reduce the RSSI data volume by approximately 72% with no noticeable reduction in localization accuracy.

Motivated by the computational, bandwidth and energy restrictions of wireless sensor network nodes and their need to, collectively, determine the presence of exogenous interference that could impair their communication, we consider schemes that could support the task of interference classification as a first step towards interference mitigation strategies. In particular, we examine the effectiveness of the Discrete Wavelet Transform (DWT) to communicate to other nodes the state of the channel, as sampled by a node, in a compressed, denoised form. We examine the suitability of different wavelet filters and thresholding methods in order to: (a) preserve key features of the interference, (b) denoise the noisy interference samples, and (c) reduce the amount of information that needs to be communicated to describe the interference.

Wireless Sensor Networks (WSNs) have a wide range of applications including smart home and environmental monitoring systems. Sensors in such systems gather and propagate critical information to sinks (data collectors). Reliability is a crucial issue in these networks but the wireless medium is subject to interference and noise that can disrupt transmissions. Thus we design a reliable routing topology construction framework for WSNs and evaluate the proposed reliable topologies' performance. We observe that there are tradeoffs of reliability, energy consumption and path properties that applications can take advantage of.

We consider multi-hop wireless networks composed of nodes with transceivers capable of multi-packet transmission and reception (MPT/MPR). Legacy MAC protocols based on CSMA/CA are overly restrictive in the interest of avoiding collisions, and are unable to exploit the MPR capability of receivers. We demonstrate how a combination of mechanisms, based on well-known techniques, such as Additive Increase Multiplicative Decrease (AIMD), and the back--pressure (BP) principle, can be used to effectively control medium access in multi-hop MPT/MPR networks. The AIMD component is used to regulate the size of "bundles" of simultaneously transmitted packets, while back--pressure provides the basis for prioritizing, locally, which flows' packets should be transmitted in a bundle. We study the performance of the proposed protocol, AB-MAC, under three different models of node coordination in static wireless multi-hop MPT/MPR networks. We find that, under various scenarios and for the same capacity resources, AB-MAC's throughput performance surpasses that of IEEE 802.11b.

Due to recent progress in signal processing techniques, the traditional collision channel model is inadequate for communication networks where the transceivers are endowed with the ability to transmit or receive multiple packets simultaneously (the MPT/MPR capability). This paper studies the schedule construction in MPT/MPR systems with the objective to understand how the flows traversing the network can leverage the MPT/MPR capabilities in multi-hop wireless networks. Towards our goal, we present a heuristic algorithm MDSatur to produce a schedule and propose the wireless water-filling (WF) algorithm which extends the traditional water-filling algorithm to multi-hop wireless scenarios to compute max-min allocations when the MPT and MPR capabilities are equal. By combining MDSatur and WF, we also design the LEX scheme to approximate the lexicographically optimal allocation of the system when the network has nonidentical MPT and MPR capabilities.

In this paper we consider a wireless sensor network (WSN) deployed to monitor a set of targets with known positions. Each target has an associated desired level of coverage by its neighbouring sensor nodes. The network deployment process introduces node placement uncertainty described by known probability distributions. Consequently, deficiency in achieving the desired coverage levels occurs with certain probabilities. To estimate such probabilities, we formalize a target coverage deficiency (TCD) problem. We show that the TCD problem is #P-hard even when restricted to grid WSNs. We then consider networks where node transmission ranges guarantee that the network after deployment has the same connectivity as the planned network. For such networks, we devise a dynamic programming algorithm that can solve a discrete version of the problem exactly and can produce lower bounds on the solution of any arbitrary given instance of the problem. We present simulation results that investigate the accuracy of the algorithm, and illustrate its usefulness in evaluating performance of any given node deployment scheme.

RP-CDMA is a wireless multiple access protocol that utilizes multiple spreading codes and a multiple packet receiver to enhance link reliability and performance. We apply RP-CDMA to a multihop wireless ad hoc network and propose two significant extensions aimed at improving throughput and reliability. Our simulations confirm that RP-CDMA can substantially improve link reliability and network performance, but that a link level acknowledgement protocol is required to ensure packet delivery across the network. We investigate a simple acknowledgement policy and conclude that it enables simultaneous high throughput and packet delivery while maintaining low latency.

We consider wireless sensor networks (WSNs) deployed in the plane for area surveillance against intrusion attacks. Sensor nodes often employ low-cost sensing and wireless communication modules that are prone to random failure especially when operated in harsh environments. To quantify the network's ability to monitor the area, we formalize the breach path detection reliability (BPDREL) problem that takes as input a specified set of entry-exit pairs of network sides, and calls for computing the likelihood that the network can detect intrusion paths between any of the specified pairs of sides. We devise an exact algorithm for solving the problem on networks that can be embedded in grid networks utilizing diagonal links. Using the devised algorithm, we analyze the least and most detectable classes of intrusion paths, as well as the impact of varying various network parameters on the overall network reliability.

This paper considers wireless sensor networks (WSNs) deployed to provide surveillance against intruders that wish to cross a given area. Due to limited resources, low manufacturing cost, and operation in harsh environments, nodes in such networks are subject to random failure in the field. Hence, there is a need to develop suitable reliability assessment mechanisms to quantify a WSN's ability to perform successfully. Here, we consider one such measure, called the breach path detection reliability (BPDREL), that applies to networks where any intruder crossing a line segment between some adjacent operating pairs of sensor nodes can be detected, and the network perimeter is made of a polygon of such line segments. Each breach path across the network is associated with a pair of entry-exit sides on the perimeter. Our measure takes into account intrusion events associated with any user-specified set of such entry-exit sides. Computing the exact BPDREL can be shown to be #P-hard. We extend existing results on the BPDREL by developing an approach for deriving lower bounds on the problem for arbitrary WSNs where the sink node is located on the network's perimeter. The resulting algorithm is used to analyze the impact of varying various network parameters on the overall network reliability.

This paper deals with a resource sharing problem in wireless sensor networks (WSNs). The problem calls for identifying k data collection trees that can be managed by independent users to run applications requiring area coverage. The formalized problem, called k-balanced area coverage slices (k-BACS), calls for identifying an ensemble of k trees that share the sink node only (and no other node) in a given WSN. To avoid nodal congestion, each tree is required to satisfy constraints on the maximum degree of its nodes. The objective is to maximize the minimum total area covered by any tree in the ensemble. Existing results in the literature show that the k-BACS problem is NP-complete even if k =2. Thus, effective heuristic algorithms are needed. In this paper, we present and compare the performance of two efficient algorithms for solving the problem. Our results show that the devised algorithms produce well-balanced trees. In addition, the combined use of the computed partitions and the PEAS energy conservation protocol can produce competitive lifetime for networks where a prescribed level of area coverage is required for successful operation.

Resource competition is inevitable in shared-resource systems, as the number of users increases or their resource demands change. In wireless networks, this problem is aggravated due to the existence of co-channel interference. Without appropriate control, harmful competition causes unbalanced user consumption of resources (e.g. starvation), and resource waste due to conflicts and idleness. In this paper we propose a novel framework to effectively manage resources (e.g. shared wireless channels). Compared with the state-of-art global optimization algorithm, our method is superior in terms of eliminating control overhead caused by message passing, achieving competitive performance, and reducing computational complexity. This framework combines the advantages of global and local optimization methods and drives the system toward a global optimum by intelligently exploiting local information.

In this paper we consider wireless sensor networks (WSNs) whose nodes can fail independently of each other during normal operation. For successful operation, a network is required to provide sensing coverage of an aggregate area that exceeds a given application-specific coverage requirement. We formulate an area coverage reliability problem that quantifies the likelihood that the network can be in an operating state where the coverage condition is satisfied. Existing results show that the problem is #P-hard even when the WSN is restricted to a rectangular grid with a single corner-located sink. Thus, an exact solution is unlikely to exist for many WSN topologies. We present a framework for computing reliability lower bounds by decomposing an arbitrary WSN into subnetworks that share only the sink node and computing coverage probabilities for each subnetwork. We show that the framework yields an efficiently computable lower bound when the subnetworks are chosen to be trees and cycles. Our design utilizes a 3-state node reliability model that has been shown to improve over the conventional 2-state (operate/fail) model. The obtained results investigate some design issues of the framework, the quality of the obtained lower bounds, and discuss an application of the obtained lower bounds in improving the design of WSNs.

In this paper we formalize a problem called weighted balanced two-slice problem (WB2S) that calls for partitioning (slicing) a wireless sensor network (WSN) so as to support concurrent running of two independent applications. Our model associates a weight with each node to reflect the node's relative importance to the applications. As well, the model imposes a degree constraint on each node to control its traffic load when it operates in a multi-level tree. The problem calls for computing two disjoint trees (sharing a common sink) whose minimum total weight is maximized among all possible feasible pairs of trees. We show that the WB2S problem is NP-complete, present a dynamic program to handle the problem, analyze the algorithm, and show its potential impact by simulation.

Allocating wireless network resources fairly to users, and using these limited resources efficiently is crucial for improving system performance and satisfying user requirements. Our proposal is to achieve higher network throughput via lower transmit power, and to reduce throughput differences between flows caused by uncontrolled resource competition. A hierarchical joint control framework has been designed to achieve this goal. The performance of this framework has been evaluated via ns2 simulation. Our experimental results demonstrate that our control framework significantly improves performance and results in lower packet loss rates, higher network throughput, shorter end-to-end delay and enhanced fairness.

Symmetric distributed source coding has made great progress in the past several years. However, few attempts have been tried to use the symmetric distributed source coding schemes in real data compression scenarios. In this paper, with the inspiration of previous symmetric distributed source coding schemes, we first put forward a novel syndrome-based symmetric distributed coding scheme which can achieve the whole Slepian-Wolf rate region. Then we propose a general architecture for symmetric distributed multiview video schemes. Our experiments show very encouraging results. In the high-rate case, our scheme can achieve great rate saving from separate H.264 coding scheme at the same video quality.

Inefficient resource management may cause problems of reliability of service in shared medium wireless networks. Resources include bandwidth, processor cycles and buffers. Excessive competition for these resources can cause severe packet collision rates, compound network congestion, or even result in starvation of some nodes. In such a situation, data transmission is subject to very long delays and significant packet losses. Although transport layer protocols can help improve end-to-end performance, these approaches are slow in responding to network changes and incur additional overhead. This paper aims to reduce transmission delay and increase packet delivery ratio. A hybrid resource allocation problem is formulated by the Primal algorithm and a controller is derived to decrease congestion globally and to reduce collisions locally. Our simulation results show that this hybrid controller can achieve packet loss rates close to 1% and significantly shorten end-to-end delay even in a high interference environment with heavy system load. In addition, we also compare the performance of the hybrid controller with the impact of multipath routing. The accuracy of our simulation is improved by adding a probabilistic preamble detection model and SINR collision model based on frame error rate.

Underwater sensor networks have received significant attention from the research community in recent years. Since radio signals face excessive absorption in the underwater environment, acoustic communication has been the dominant physical layer medium in the literature. Although acoustic communication has long range and omni-directional characteristics like terrestrial radio, it suffers from excessive propagation delay in water and very low bandwidth. In this paper, we consider the design of an optical underwater sensor network based on low cost LEDs and photodiodes. Such an optical communication system has shorter range compared to acoustic systems but is cheaper and can support significantly higher bandwidth. Optical communication requires line of sight which makes optical links vulnerable to occasional failures due to underwater organisms and moving particles. We consider a grid based deployment of underwater sensor nodes and the selection of a topology based on point-to-point optical links that is robust to occasional link failures. We develop patterns for networks with at most 3 interfaces per node constraints. We evaluate the robustness of our proposed deployment patterns by simulating three resilient routing protocols on these patterns and demonstrate that our patterns support a high degree of robustness even though they use only a fraction of all potential links in the grid graph.

In the past decade, machine learning techniques have made great progress. Inspired by the recent advancement on semi-supervised learning techniques, we propose a novel learning-based multiview video compression framework. Our scheme can efficiently compress the multiview video represented by multiview-video-plus-depth (MVD) format.We model the multiview video compression problem as a semi-supervised learning problem and design sophisticated mechanisms to achieve high compression efficiency. Our approach is significantly different from the traditional hybrid coding scheme such as H.264-based multiview video coding methods. The preliminary results show promising compression performance.

In shared-medium wireless networks, nodes contend for medium access in space, time and channel bandwidth. Uncontrolled competition for limited network resources causes severe packet collisions and compounds network congestion. Consequently, data transmission is subject to very long delay, significant packet loss and poor throughput. This work focuses on improving data transmission in wireless ad hoc networks through optimal control of spatial, temporal and bandwidth contention. Our simulation study demonstrates that this optimal control scheme outperforms RTS/CTS and achieves significant improvement of CSMA/CA performance under various effects.

Distributed source coding is a promising enabling technology for sensor network applications. Symmetric distributed source coding can achieve the entire Slepian-Wolf rate region and offer sensor network applications a wide range of options to compress and transmit data. In this paper, we design a new symmetric distributed coding scheme that realize the benefits of both simplified code construction and bit incorrespondence handling. In particular, we propose a general scheme to deal with the bit incorrespondence problem, which is not specifically addressed by previous approaches. With the ability to deal with the bit incorrespondence in the code structure, it is more likely for our approach to be used in real sensor network environments.

We propose a dynamic scheduler for multichannel 802.15.3 WPANs which exploits both channel reuse and interference control. A maximal-weighted-matching based scheduling scheme is designed to arrange simultaneous transmissions in each single channel and a multichannel assignment scheme is proposed to obtain the ultimate schedule in each superframe. For successful signal decoding, accumulated interference among simultaneous transmissions is taken into account to ensure that signal reception occurs with sufficient SINR. To improve the efficiency of channel reuse, the scheduler fragments each transmission request to multiple requests with the equal duration. An analysis is given of the optimal way to implement such process according to online traffic load and overhead. Simulations are used to evaluate the performance and to compare against existing schemes.

QoS routing has been shown to be NP-hard. A recent study of its hardness shows that the "worst-case" may not occur in practice (Kuipers mieghem, 2003). This suggests that there may exist fast exact algorithms for the multi-constraint shortest path (MCSP) problem, an instance of QoS routing. Search techniques such as A* and IDA* may solve hard problems exactly in polynomial time. In Li et al. (2005), we deploy the idea of iterative deepening search to design IDA*_MCSP, and show its efficiency by extensive empirical study. In this paper, we show that for infeasible cases, where there is no feasible solution, IDA*_MCSP may not be as efficient as A*Prune. This motivates us to design an algorithm that is efficient in both feasible and infeasible cases. We design an exact MCSP algorithm A*_MCSP, which introduces the state notion and dominance relationship between states. Furthermore, we design an exact MCSP algorithm FringeMCSP. It can be regarded as an integration of IDA*_MCSP and A*_MCSP. Extensive empirical study shows that FringeMCSP has good performance in both feasible and infeasible cases; while IDA*_MCSP still shows its superiority among the proposed MCSP algorithms in feasible cases.

We propose an energy-efficient multi-hop scheduling scheme for single-channel 802.15.3 networks which produces interference-avoiding schedules that are throughput and energy efficient. The scheduler replaces high-interference peer-to-peer transmission with low-interference multi-hop transmissions by interference-aware multi-hop routing, which reduces both interference and energy consumption of transmission. To maximize channel reuse, a multi-hop maximal-weighted-matching grouping scheme is applied to arrange concurrent transmissions. For successful signal decoding, the accumulated interference among concurrent transmissions is taken into account to ensure that signal reception occurs with sufficient SINR.

We consider the interplay between data aggregation and workload balancing in a Wireless Sensor Network (WSN). In particular, we formulate the problem of deciding where to forward traffic, in order to benefit the most from potential aggregation, while also splitting the resulting traffic (once aggregated) on the way to the Sink for the sake of load balancing. Load balancing across multiple paths results in a corresponding balanced energy consumption and therefore prolongs the lifetime of WSNs. The optimization formulation leads to an IP/LP model where the objective is that of maximizing the lifetime of the WSN. Heuristics are proposed for assigning an efficient data aggregation node for each sensor source. Simulation results show that our schemes significantly improve performance both in terms of longer system lifetime and less total data received (indicating more aggressive aggregation) at the Sink.

We propose a scheduling scheme for single-channel 802.15.3 networks which produces interference-avoiding schedules for both isochronous and asynchronous traffic. The scheduler explores spatial channel reuse by means of maximal weighted matching and request grouping. For fairness, a binary exponential weight adjustment algorithm is applied to dynamically adjust the priority of requests. To enhance scheduling efficiency, requests are split and channel time is allocated accordingly. An efficient schedule update mechanism is also introduced to handle on-the-fly traffic request modifications.

Abstract — Energy efficiency is an important issue in multihop wireless networks with energy concerns. Usually it is achieved with accurate knowledge of the traffic pattern and/or the current network information such as the remaining energy level. We investigate the problem of designing a routing scheme to minimize the maximum energy utilization of a multihop wireless network with weak assumption of the traffic pattern and without ongoing collection of network information. We develop polynomial size LP models to design such a routing scheme. We discuss generalizations of the LP models to various radio transmission models. In an interference-limited scenario, we show how to guarantee schedulability of the oblivious routing. We present an extension to consider lossy links. We also discuss implementation issues. The LP models achieve performance close to what an oracle can achieve in the performance study. The results for multihop wireless networks with a single sink are especially good. We make a first stride in designing a traffic-oblivious energy-aware routing framework in multihop wireless networks. I.

We consider the problem of extending the lifetime of wireless sensor networks (WSNs) where sensors report their data to a base station via multi-hop transmission. In-network data aggregation is introduced to reduce the traffic. The lifetime is optimized using a LP (linear programming) framework built on a multicommodity network flow model to which we introduce the concept of flow loss multiplier to express the impact of data aggregation over correlated data. To balance energy consumption across the network, data aggregation is performed only at the first hop (FH) transmission. Heuristics are proposed to obtain significant FH aggregation, accordingly prolonging system lifetime. Simulation results show that FH aggregation possesses characteristics that make it suitable under certain data collection applications/scenarios

QoS routing has been shown to be NP-hard. A recent study of its hardness suggests that the "worst-case" may not occur in practice, and thus there may exist a fast exact algorithm. We deploy the idea of iterative deepening search and look ahead to design an exact algorithm for finding the shortest path subject to multiple constraints (the MCSP problem). The accuracy of look-ahead information determines the efficiency of a search algorithm. The higher the accuracy of the look-ahead information, the more efficient the search process. An empirical study on a wide range of topologies shows the high accuracy of look-ahead information in the studied cases. Experimental results also show that our algorithm, IDA*/spl I.bar/MCSP, is fast and, in general, significantly outperforms A*Prune, an algorithm designed for the MCSP problem. The characteristics of iterative deepening search and the high accuracy of look-ahead information make IDA*/spl I.bar/MCSP a fast exact algorithm for the MCSP problem.

We consider the problem of transmission scheduling in wireless networks. A good transmission scheduling scheme should not only be conflict-free, in the sense of resolving collisions and the hidden terminal problem, but should also provide fairness and transmission efficiency to each node. We propose a class of scheduling schemes that rely on the logical ordering of the schedule update operations. The ordering is imposed by the precedence relationship of vertices in a directed acyclic graph (DAG). Two examples of establishing the logical DAG are given: (a) one relies on a distributed spanning tree construction; (b) one is based on location information. A separate mechanism ensures that nodes do not behave in a greedy fashion and monopolize the schedule slots. We prove the correctness of DAG-based schemes and provide simulation results that demonstrate their fairness and efficiency attributes.

Applegate and Cohen (2003) computational complexity design demand oblivious routing schemes that achieve low oblivious ratio with no or approximate knowledge of traffic demands. We investigate the quality of oblivious routing with respect to path dispersion, which is concerned with the number of paths; and path variation, which is concerned with how far the paths are from the shortest paths and the variation of path lengths. The results show the dispersion and the variation are high in general. We propose a penalty method to improve the quality of oblivious routing. The penalty method strikes a good balance between the conflicting objectives of minimizing the oblivious ratio and optimizing the quality of oblivious routing. Moreover, we apply the simple penalty method to the problem of minimizing the maximum link utilization given a traffic matrix. With the penalty method, we can achieve almost the same maximum link utilization, and improve the quality of routing to almost perfect, i.e. one or two paths that are very close to the shortest paths between each pair of nodes.

Multihop wireless networks have unique features such as lossy links and interference. Both interference and lossy links affect the maximum achievable throughput of a network. Some wireless networks have energy constraints. Lossy links also affect energy efficiency due to retransmissions and broadcasting. We investigate the impact of lossy links on maximum achievable throughput and minimax energy utilization. These can be modeled as linear programming optimization problems. We give optimal solutions for both flow-based and destination-based routing. Experiments show that lossy links do have significant impact on the maximum achievable throughput. There are cases where a network can only achieve half of the throughput of the corresponding lossless network. The results show less significant impact of loss on energy efficiency. In some cases, the loss may be advantageous for energy efficiency, since the energy consumption may be reduced due to the loss of broadcasting messages. Experiments also show the significant impact of overhearing on energy efficiency.

Multiview video compression is important to the image based 3D video applications. In this paper, we proposes a novel neighbor-based multiview video compression scheme. It is essentially a MPEG2-like block-based scheme. In particular, a method to decide the stream encoding order is presented. The resulting stream encoding order can better decorrelate spatial redundancies among multiple video streams than the center approach. Experimental results confirm the superiority of the proposed neighbor approach over the center approach and MPEG2 for multiview video compression.

Video transcoding can convert a compressed video from one format to another format. In this paper, we propose a novel multiview video transcoder, which is used for bit-rate scaling of multiple compressed synchronized video streams. Different from the traditional joint transcoder for independent multiple program transcoding, the multiview video transcoder has one unique task to decorrelate spatial redundancies among video streams. A fast disparity estimation algorithm with the GOP-based disparity search window is put forward and evaluated. The proposed multiview video transcoder can be used to design a cost-effective video acquisition and transmission system for emerging 3D video applications.

Power-aware routing is crucial for battery-finite mobile nodes in MANETs. Energy consumption optimization consists of not only energy saving, but also energy-balanced usage of nodes. In this paper, we present a new position-based routing protocol with a power-aware weighted forwarding function, named PAWF. With this forwarding function, the energy consumption and energy residual values of mobile nodes are asymmetrically combined with forwarding achievement and used to make decisions of hop by hop routing. PAWF routing requires only the local information of strict neighbors and the destination. With the power-awareness, the over-usage of mobile nodes is avoided and the lifetime of the network is increased due to energy consumption balance. Based on simulation results, PAWF is also shown to be able to provide global energy-sufficient near-optimal paths by making locally optimal choices, which offers the possibility to implement further QoS routing in MANETS.

It is essential and nontrivial to disseminate QoS information in an efficient manner and to guarantee the information accuracy. We present an efficient scheme for QoS information update among edge routers in a diffserv region. In our scheme, a multicast tree is constructed among the edge routers in a diffserv region to transmit the updates. This scheme is efficient in consuming network resources since the cost for QoS information update of using a tree is much less than using a flooding approach, and routers unrelated to decision-making are relieved from disseminating and storing QoS information. In addition, it is easy to implement our scheme in the Internet, since only edge routers need to deploy it. We investigate quantitatively the cost of our scheme for QoS information update against a flooding approach and study empirically the efficiency of several proposed QoS information update policies.

We estimate that approximately 40% of current Internet traffic is due to Web crawlers retrieving pages for indexing. We address this problem by introducing an efficient indexing system based on active networks. Our approach employs strategically placed active routers that constantly monitor passing Internet traffic, analyze it, and then transmit the index data to a dedicated back-end repository. Our simulations have shown that active indexing is up to 30% more efficient than the current crawler-based techniques.

An error recovery scheme is essential for large-scale reliable multicast. We design, implement, and evaluate an improved active error recovery scheme for reliable multicast (AERM). The AERM uses soft-state storage to facilitate fast error recovery. It has the following features: a simple NAK suppression and aggregation mechanism, an efficient hierarchical RTT measurement mechanism, an effective local recovery and scoped retransmission mechanism, and a periodical ACK mechanism. We implement the AERM and study its characteristics in NS2. We also compare performance with ARM and AER/NCA, both of which are representative active reliable multicast protocols. The results indicate that AERM can achieve considerable performance improvement with limited support from routers. Our work also confirms that active networks can benefit some applications and become a promising network computing platform in the future.

A mobile ad hoc network (MANET) is a collection of wireless mobile computers forming a temporary network with no existing wired infrastructure. Due to the dynamic nature of network topology and the resource constraints, routing in MANETs is a challenging task. Distributing the routing tasks fairly has eminent advantages, such as reducing the possibility of power depletion and queuing delay in the hosts with heavy duties. However, most current routing protocols for MANETs do not take load balancing into account. In this paper, we propose a load-sensitive on-demand routing approach, which utilizes the network load information as the main route selection criterion. We perform a simulation study on the proposed routing protocol. Compared with the dynamic source routing (DSR), our protocol shows better performance in terms of packet delivery ratio and average end-to-end delay. Further, with low mobility, these benefits are gained without an increase in the control overhead.

Wireless Mobile Ad hoc NETworks (MANET) provide end-users with a flexible and cheap way to access and exchange information. While most research in MANETs is oriented to the general application environments, little work is done to utilize the specific characteristics of particular application scenarios, in which end-users' behavior is quite predictable or controllable. To deploy a MANET for a particular realistic system, the end-users' behavior, or profiles, can be used to simplify the implementation and enhance the network performance. We present a scheme to simplify routing strategy in MANET with the help of end-users' mobility profiles. We also study how the routing strategy improves the network performance in a realistic city transportation system.

A Mobile Ad hoc NETwork (MANET) is a collection of wireless mobile computers forming a temporary network without any existing wire line infrastructure. Due to the dynamic nature of the network topology, the established routes in a MANET may be disconnected because of node mobility. It is difficult to support real-time traffic if the routes are broken and re-constructed frequently. In this paper, we propose a LOcation Trace Aided Routing (LOTAR) protocol, which utilizes the mobile nodes' location information to assist in routing and reduce the disruption of a flow. The performance of LOTAR is studied and compared to other routing approaches in MANET.

A protocol for the reliable multicast of data to mobile hosts is described. A logical ring is maintained between all the base stations that handle the multicast traffic of the same multicast group. A token passing protocol enforces a consistent view between all base stations with respect to the frames that are considered delivered to all mobiles. The interaction of the reliable multicasting and the handoff events of the mobiles is controlled by a special handoff protocol. A description of the management protocol is also given. We use simulation results to illustrate the feasibility of the approach and reveal the performance interplay between the base station buffer size and the token rotation frequency.

A logical virtual path (VP) based network provides an effective way to facilitate the dynamic resource management in ATM networks. The physical topology of an ATM network should be designed to provide flexibility to the logical VP reconfiguration in order to adapt to changing traffic conditions. Three different physical design algorithms are considered. Two parameters in the design control the spare capacity and the alternative path allocation providing the flexibility to the VPs. The algorithms are evaluated under both static and dynamic capacity allocation schemes using simulation.

Through the Internet and service providers such as cable companies it will be possible to receive a wide range of services such as Internet access, video distribution and television in the home. However, a bottleneck in these systems is the bandwidth available to the home and over the cable tv network. In this paper, the use of advance reservation for non-interactive services is proposed to alleviate the problem of limited bandwidth and allow for more services to a wider range of customers. Simulation is used to study the performance of video distribution with advance reservation compared to on-demand service. It is shown that by merging requests, advance reservation significantly increases the amount of traffic the system can handle while still maintaining low delays. It is also shown that the demand system is more susceptible to load increases than the reservation traffic.

The SCENT (Student Computing ENvironmenT) project is concerned with building an intelligent tutoring system to help student programmers debug their LISP programs. The major thrust of current SCENT investigations is into the design of the SCENT advisor which is meant to provide debugging assistance to novice students. Six conceptual levels constitute the advisor. At the lowest level is the “raw data,” consisting of the student's (possibly buggy) program. This can be interpreted by a “program behaviour” level which can produce traces, cross‐reference charts, etc. from the student's program. These traces, etc. can be analyzed by “observers” for interesting patterns. At the next level are “strategy judges” and “diagnosticians” which determine which strategy the student has used in his/her program and bugs in this strategy. A “task expert” provides task‐specific input into the process of analyzing the student's solution, and a “student‐knowledge component” provides student‐specific input into this process. Information from the six levels interacts in a variety of ways and control is similarly hierarchical. This necessitates a blackboard‐style scheme to coordinate information dissemination and control flow. This paper discusses the objectives of SCENT and focusses on organizing the process of debugging student programs. A complete example is given to illustrate how entities at the six levels interact and to indicate the kinds of information sharing that occur in the SCENT advisor. The paper concludes with an evaluation of the strengths and weaknesses of this approach to automated debugging, and suggestions about directions for further exploration.