In wireless sensor networks, periodic data collection appears in many applications. During data collection, messages from sensor nodes are periodically collected and sent back to a set of base stations for processing. In this article, we present and analyze a near-lifetime-optimal and scalable solution for data collection in stationary wireless sensor networks and an energy-efficient packet exchange mechanism. In our solution, instead of using a fixed network topology, we construct a set of communication topologies and apply each topology to different data collection cycles. We not only use the flexibility in distributing the traffic load across different routes in the network (spatial load balancing), but also balance the energy consumption in the time domain (temporal load balancing). We show that this method achieves an average energy consumption rate very close to the optimal value found by network flow optimization techniques. To increase the scalability, we further extend our solution such that it can be applied to networks with multiple base stations where each base station only stores part of the network configuration, cooperating with each other to find a global solution in a distributed manner. The proposed methods are analyzed and evaluated by simulations.

Immediate notification of urgent but rare events and delivery of time sensitive actuation commands appear in many practical wireless sensor and actuator network applications. Multi-parent wake-up scheduling was presented as a technique which can provide bi-directional end-to-end latency guarantees while optimizing the node battery lifetime. This method takes a cross-layer approach where multiple routes for transfer of messages and wake-up schedules for nodes are crafted in synergy to reduce overall message latencies. In this paper, we generalize the multi-parent method to support a multi-cluster model for the network where we assume that the network has multiple central points called cluster-head (CH) that are in charge of scheduling the nodes in the network. A key step in multi-parent method is to divide the nodes in network into disjoint groups such that each node has at least one link to a node in each group. We formulate this step as a graph coloring problem which is shown to be NP-complete. We propose an algorithm where all the cluster-heads cooperate to find a heuristic solution for the graph coloring optimization problem in a distributed manner. We show that each cluster-head requires less memory and computational power compared to the case where one cluster-head finds the global solution, therefore the solution is very scalable.

We consider the problem of supervision or periodic data collection for stationary wireless sensor networks and present a practical, energy-efficient, and reliable solution. Energy-efficiency is achieved by combining three design methods: (a) adopting network flow optimization techniques, the optimal scheme for balancing the communication load among all the nodes in the network is calculated. This gives the lower bound for the energy required for data collection process, (b) instead of using a fixed network topology (communication tree), a set of optimized trees is constructed and the communication tree varies over different data collection cycles. We show that this method achieves an average energy consumption rate very close to the optimal value, (c) the packet exchange procedure is designed based on collision-free schedules, to minimize the number of packets and the transmission and reception times for each node. Reliability of the process is guaranteed by including many retransmission opportunities in the schedules. The performance is evaluated through simulations.

Collection of rare but delay-critical messages from a group of sensor nodes is a key process in many wireless sensor network applications. This is particularly important for security related applications like intrusion detection and fire alarm systems. An event sensed by multiple sensor nodes in the network can trigger many messages to be sent simultaneously. We present Alert, a MAC protocol for collecting event-triggered urgent messages from a group of sensor nodes with minimum latency and without requiring any cooperation or pre-scheduling among the senders or between senders and receiver during protocol execution. Alert is designed to handle multiple simultaneous messages efficiently and reliably minimizing the overall delay to collect all messages along with the delay to get the first message. Moreover, the ability to handle a large number of simultaneous messages does not come at the cost of excessive delays when only a few messages need to be handled. We analyze Alert and evaluate its feasibility and performance with an implementation on commodity hardware. We further compare Alert with existing approaches through simulations and show the performance improvement possible through Alert.

Communication among wireless sensor nodes that employ cheap low-power transceivers is often very sensitive to the variations of the wireless channel. Sensor network routing protocols thus strive to continually adapt to temporal variations in wireless links in order to avoid wasteful transmissions over low-quality links. Such adaptive routing protocols must rely on a scheme that can not only accurately estimate the quality of wireless links in terms of a quantitative measure, such as the packet success rate (PSR), but also quickly adapt to temporal dynamics of the links. Traditionally, the PSR is estimated from the fraction of successful transmissions over a window of test- packets. However, we demonstrate that counting based methods do not react to changes in the wireless channel fast enough and that the only way to address this problem is to estimate the PSR based on the receiver's characteristics and on the signal to noise ratio (SNR) at the receiver. We thus propose a scheme that uses a pre-calibrated SNR-PSR relationship and instantaneous SNR estimates to calculate the PSR of the link. In our scheme, each receiver continuously tracks the SNR using a Kalman Filter to minimize the estimation error and uses a locally available SNR- PSR curve to estimate the PSR. Through extensive experiments we demonstrate that our scheme adapts to variations in the channel faster than counting-based PSR estimators and that it also provides better PSR estimates than these counting-based approaches.

A large number of ractical sensing and actuating applications require immediate notification of rare but urgent events and also fast delivery of time sensitive actuation commands. In this a er,we consider the design of efficient wakeup scheduling schemes for energy constrained sensor nodes that adhere to the bidirectional end-to-end delay constraints posed by such applications. We evaluate several existing scheduling schemes and propose novel scheduling methods that outperform existing ones.We also resent a new family of wakeu methods,called multi-parent schemes, which take a cross-layer a roach where multiple routes for transfer of messages and wakeup schedules for various nodes are crafted in synergy to increase longevity while reducing message delivery latencies. We analyze the power-delay and lifetime-latency tradeoffs for several wakeup methods and show that our proposed techniques significantly improve the performance and allow for much longer network lifetime while satisfying the latency constraints.

In recent years, several high-throughput low-delay scheduling algorithms have been designed for input-queued (IQ) switches. It has been shown however that scheduling policies such as maximum weight matching, that perform optimally for an isolated switch, fail to provide stability in a network of IQ switches (M. Andrews and L. Zhang, 2001). Although there exist algorithms that ensure stability in networks of switches (M. Andrews and L. Zhang, 2001) (M. Ajmone Marsan et al., 2003), they are either not fully local or require knowledge/estimation of rates, and are thus not desirable. Here we propose a local and online switch-scheduling algorithm and prove that it achieves stability in a network of single-server switches when arriving traffic is admissible and obeys the strong law of large numbers. We then propose its counterpart for networks of crossbar switches and conjecture that this too is stable. Additionally, we prove that our algorithms provide a max-min fair rate allocation for isolated switches even when arriving traffic is inadmissible. We believe that fairness is key to ensuring stability in networks.

In this paper, we introduce a new and advanced algorithm, namely, multiple-shift algorithm for code acquisition in optical code-division multiple access (CDMA) systems using unipolar optical orthogonal codes (OOCs) as signature sequences. We analyze the performance of the newly proposed algorithm and obtain a bound on its performance and show its advantage in reducing the mean time of synchronization when compared with other synchronization methods. The algorithm can be used with many different receiver structures, like active or passive correlator with or without hardlimiter(s). However, in this paper, we only consider the simple active correlator structure for further discussions and analysis.

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets-also knowns as cells-for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan et al. They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan et al. are strongly dependent on the arrival distribution. Next, we propose a new class of "waiting" algorithms. We show that the "waiting"-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.

Multi-path routing has been studied thoroughly in the context of wired networks. Ii has been shown that using multiple paths to route messages between any source-destination pair of nodes (instead of using a single path) balances the load more evenly throughout the network. The common belief is that the same is true for ad hoc networks, i.e., multi-path routing balances the load significantly better than single-path routing. We show that this is not necessarily the case. We introduce a new model for evaluating the load balance under multi-path routing, when the paths chosen are the first K shortest paths (for a pre-specified K). Using this model, we show that unless we use a very large number of paths (which is very costly and therefore infeasible) the load distribution is almost the same as single shortest path routing. This is in contrary to the previous existing results which assume that multi-path routing distributes the load uniformly.

For energy-constrained stationary wireless networks of sensors, selection of links with high quality rate helps to ensure reliable long-term operation. During the implementation of a protocol targeting industrial applications of such systems, it was found that it is advantageous to acquire accurate information about the availability and quality of the RF communication links prior to the network topology formation. "Link assessment" as part of the initialization process, accomplishes this task by assessing a sufficient number of packets exchanged between neighboring nodes. This paper introduces and analyzes two different approaches to link assessment: The first approach is a random nondeterministic scheme that allows for a probabilistic guarantee of collision-free packet exchange. An alternative method is described which employs 'constant-weight codes' and provides a deterministic guarantee of success. In particular, a special class of constant-weight codes, known as optical orthogonal codes, are considered. Since, these codes are cyclically permutable, they make the link assessment process simpler, and therefore they are preferred over other codes. We evaluate the performance of these methods based on their energy consumption, time duration, and implementation complexity.

In wireless sensor networks, a good cost metric encapsulating wireless link quality is essential to an energy-efficient routing topology. For many wireless network scenarios, rapid variation in the channel precludes an efficient mechanism for knowing instantaneous link quality at the time of transmission, thus making it difficult to estimate the instantaneous value of the cost metric. This paper explores what a good cost metric may be and how it can be measured in an energy-efficient way. We present an experimental study of wireless link quality variation over a period of several days in a sensor network placed in two different indoor office environments. The nodes are equipped with low power transceivers operating in the 900 MHz band. Results are documented for several different link configurations, i.e., relative placement of the transmitter and receiver. Based on detailed observations of link quality variation, we form quantitative measures of link quality, and propose a cost metric. We find that reasonably few channel measurements are sufficient to obtain a good estimate of the cost metric, hence even during the initialization phase one can obtain sufficient information about links in order to design an efficient topology. The estimate can be improved further as more measurements are taken during the normal operation of the network.

Input Queued (IQ) switches have been very well studied in the recent past. The main problem in the IQ switches concerns scheduling. The main focus of the research has been the fixed length packet-known as cells-case. The scheduling decision becomes relatively easier for cells compared to the variable length packet case as scheduling needs to be done at a regular interval of fixed cell time. In real traffic dividing the variable packets into cells at the input side of the switch and then reassembling these cells into packets on the output side achieve it. The disadvantages of this cell-based approach are the following: (a) bandwidth is lost as division of a packet may generate incomplete cells, and (b) additional overhead of segmentation and reassembling cells into packets. This motivates the packet scheduling: scheduling is done in units of arriving packet sizes and in nonpreemptive fashion. In M.A. Marsan et al. (2001) the problem of packet scheduling was first considered. They show that under any admissible Bernoulli i.i.d. arrival traffic a simple modification of maximum weight matching (MWM) algorithm is stable, similar to cell-based MWM. In this paper, we study the stability properties of packet based scheduling algorithm for general admissible arrival traffic pattern. We first show that the result of Marsan et al. extends to general regenerative traffic model instead of just admissible traffic, that is, packet based MWM is stable. Next we show that there exists an admissible traffic pattern under which any work-conserving (that is maximal type) scheduling algorithm will be unstable. This suggests that the packet based MWM will be unstable too. To overcome this difficulty we propose a new class of "waiting" algorithms. We show that "waiting"-MWM algorithm is stable for any admissible traffic using fluid limit technique.

We consider a network of n sender/receiver pairs placed randomly in a region of unit area. Network capacity or maximum throughput is defined as the highest rate that can be achieved by each sender/receiver pair over a long period of time. It is known that without using relays (i.e., via only direct communication), the maximum throughput is less than O(1), that is, strictly decays as n increases. The network capacity without relaying for static or mobile networks is not known. However, a known lower bound on this capacity if O[(log (n))/n]. Our goal is to find a higher achievable rate. We show, by demonstrating a simple coding and scheduling scheme that uses mobility, that O[(log (n))/(n/sup 1/-/spl beta/)] is achievable, where /spl beta/ > 0 is a constant that depends on the power attenuation factor in the wireless medium. For example, when power decays as d/sup -4/ with distance d, O[(log (n))/(n/sup .25/)] is achievable. We assume channels to be AWGN interference channels throughput this work.

We analyze, for the first time, the performance of a serial-search algorithm for optical code-division multiple access (CDMA) systems using optical orthogonal codes (OOC). For our analysis, we use advance photon-counting methods and we consider the effect of shot noise and dark current and multi-access interference (MAI). We introduce a new method for modeling the effect of MAI, then we use two approaches to consider this effect on the performance of the synchronization system. For the first approach, we consider the average effect of interference in our analysis, while for the second approach two specific forms of interference are taken into account where one form represents a heavily localized interference pattern and the other shows a uniformly distributed one. The effects of different parameters of the system including system threshold, number of active users in the network, and mean number of photons in each optical pulse on the performance of the synchronization system are evaluated and discussed.

We analyze, for the first time, the performance of a simple serial-search algorithm for optical code-division multiple access (CDMA) systems using optical orthogonal codes (OOC). For our analysis, we use advanced photon-counting methods and we consider the effect of shot noise and dark current and multi-access interference. We use two approaches for considering the effect of multi-access interference on the performance of the synchronization system. One approach is the general method of considering the average effect of interference. In the other approach, we introduce a new concept for modeling interference; then, with the help of this model, we obtain results that can be regarded as upper and lower bounds on the performance of the synchronization system.