Robots that can manipulate objects in unstructured environments and collaborate with humans can benefit immensely by understanding natural language. We propose a pipelined architecture of two stages to perform spatial reasoning on the text input. All the objects in the scene are first localized, and then the instruction for the robot in natural language and the localized co-ordinates are mapped to the start and end co-ordinates corresponding to the locations where the robot must pick up and place the object respectively. We show that representing the localized objects by quantizing their positions to a binary grid is preferable to representing them as a list of 2D co-ordinates. We also show that attention improves generalization and can overcome biases in the dataset. The proposed method is used to pick-and-place playing cards using a robot arm.

The FCC mandate of allowing TV Whitespaces for unlicensed access has the potential for dramatic improvements in wireless access data rates. We argue that an ideal MAC should account for diverse user-location and spectrum dependent channel rates to provide fair data rates and efficient utilization. Furthermore, due to limited tunable bandwidth of a radio and fragmented spectrum, the AP should support multiple radios. We make the following contributions by designing a MAC for wireless LAN access over TV Whitespace. (i) We propose an architecture and beaconing mechanism to enable such a MAC. Our MAC is an evolution of 802.11 MAC. (ii) We propose an algorithm that chooses the Whitespaces for the different radios of the AP and assigns clients to the radios. Our algorithm has provable guarantee and is near-optimal in many scenarios. (iii) Extensive simulation over OMNET platform demonstrates the benefit of our design over a frequency and client-location agnostic Wi-Fi-like MAC. The typical throughput gain is 30-76 percent, whereas, the reduction in collisions is up to 80 percent. (iv) We implemented a proof-of-concept prototype (by modifying madWiFi drivers) that demonstrates feasibility of our design, robustness to temporal variation of available spectrum, and system throughput.

Recent trends suggest that cognitive radio based wireless networks will be frequency agile and the nodes will be equipped with multiple radios capable of tuning across large swaths of spectrum. The MAC scheduling problem in such networks refers to making intelligent decisions on which communication links to activate at which time instant and over which frequency band. The challenge in designing a low-complexity distributed MAC, that achieves low delay, is posed by two additional dimensions of cognitive radio networks: interference graphs and data rates that are frequency-band dependent, and explosion in number of feasible schedules due to large number of available frequency-bands. In this paper, we propose MAXIMAL-GAIN MAC, a distributed MAC scheduler for frequency agile multi-band networks that simultaneously achieves the following: (i) optimal network-delay scaling with respect to the number of communicating pairs, (ii) low computational complexity of O(log2(maximum degree of the interference graphs)) which is independent of the number of frequency bands, number of radios per node, and overall size of the network, and (iii) robustness, i.e., it can be adapted to a scenario where nodes are not synchronized and control packets could be lost. Our proposed MAC also achieves a throughput provably within a constant fraction (under isotropic propagation) of the maximum throughput. Due to a recent impossibility result, optimal delay-scaling could only be achieved with some amount of throughput loss . Extensive simulations using OMNeT++ network simulator shows that, compared to a multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our asynchronous algorithm achieves a 2.5x reduction in delay while achieving at least 85% of the maximum achievable throughput. Our MAC algorithms are derived from a novel local search based technique.

Multi-packet reception (MPR) promises significant throughput gains in wireless local area networks (WLANs) by allowing nodes to transmit even in the presence of ongoing transmissions in the medium. However, the medium access control (MAC) layer must now be redesigned to facilitate - rather than discourage - these overlapping transmissions. We investigate asynchronous MPR MAC protocols, which successfully accomplish this by controlling the node behavior based on the number of ongoing transmissions in the channel. The protocols use the backoff timer mechanism of the distributed coordination function, which makes them practically appealing. We first highlight a unique problem of acknowledgment delays, which arises in asynchronous MPR, and investigate a solution that modifies the medium access rules to reduce these delays and increase system throughput in the single receiver scenario. We develop a general renewal-theoretic fixed-point analysis that leads to expressions for the saturation throughput, packet dropping probability, and average head-of-line packet delay. We also model and analyze the practical scenario in which nodes may incorrectly estimate the number of ongoing transmissions.

Multi-packet reception (MPR), in which a receiver can decode multiple simultaneous transmissions, significantly improves the uplink throughput of wireless local area networks (WLANs). However, the medium access control (MAC) layer must be redesigned to encourage, and not avoid, simultaneous transmissions. Asynchronous MPR MAC protocols, in which nodes independently access the channel so long as the number of ongoing transmissions is less than a threshold, are promising solutions for enabling MPR in IEEE 802.11-based WLANs. In this paper, we highlight the problem of acknowledgment (ACK) delays that arises in asynchronous MPR when multiple nodes transmit in succession without the channel becoming idle. We propose a novel asynchronous MAC protocol that reduces the ACK delays, increases throughput, and retains the distributed nature of the 802.11 distributed coordination function (DCF). An accurate renewal theoretic fixed-point analysis that leads to general analytical expressions for the saturation throughput is also developed.

The cellular industry is evaluating architectures to distribute the signal processing in radio access networks. One of the options is to process the signals of all base stations on a shared pool of compute resources in a central location. In this centralized architecture, the existing base stations will be replaced with just the antennas and a few other active RF components, and the remainder of the digital processing including the physical layer will be carried out in a central location. This model has potential benefits that include a reduction in the cost of operating the network due to fewer site visits, easy upgrades, and lower site lease costs, and an improvement in the network performance with joint signal processing techniques that span multiple base stations. Further there is a potential to exploit variations in the processing load across base stations, to pool the base stations into fewer compute resources, thereby allowing the operator to either reduce energy consumption by turning the remaining processors off or reducing costs by provisioning fewer compute resources. We focus on this aspect in this paper.

Distributed Information SHaring (DISH) is a new cooperative approach to designing multichannel MAC protocols. It aids nodes in their decision making processes by compensating for their missing information via information sharing through neighboring nodes. This approach was recently shown to significantly boost the throughput of multichannel MAC protocols. However, a critical issue for ad hoc communication devices, viz. energy efficiency, has yet to be addressed. In this paper, we address this issue by developing simple solutions that reduce the energy consumption without compromising the throughput performance and meanwhile maximize cost efficiency. We propose two energy-efficient strategies: in-situ energy conscious DISH, which uses existing nodes only, and altruistic DISH, which requires additional nodes called altruists. We compare five protocols with respect to these strategies and identify altruistic DISH to be the right choice in general: it 1) conserves 40-80 percent of energy, 2) maintains the throughput advantage, and 3) more than doubles the cost efficiency compared to protocols without this strategy. On the other hand, our study also shows that in-situ energy conscious DISH is suitable only in certain limited scenarios.

There are two emerging trends in the mobile data world. First, mobile data is exploding at a rapid rate with analysts predicting 25-50X growth by the year 2015. The second trend is that users are demanding greater degree of flexibility in selecting their operators at fine timescales. Across Asia, dual-SIM phones have become popular, while Apple is rumored to be designing a Universal SIM that will allow iPhone users to toggle between different operators. This latter trend points towards an impending disruption in wireless service models which could also be the need of the hour from the spectrum shortage perspective.

In wireless networks, node cooperation has been exploited as a data relaying mechanism for decades. However, the wireless channel allows for much richer interaction among nodes. In particular, Distributed Information SHaring (DISH) represents a new improvement to multichannel MAC protocol design by using a cooperative element at the control plane. In this approach, nodes exchange control information to make up for other nodes' insufficient knowledge about the environment, and thereby aid in their decision making. To date, what is lacking is a theoretical understanding of DISH. In this paper, we view cooperation as a network resource and evaluate the availability of cooperation, p_{co}. We first analyze p_{co} in the context of a multichannel multihop wireless network, and then perform simulations which show that the analysis accurately characterizes p_{co} as a function of underlying network parameters. Next, we investigate the correlation between p_{co} and network metrics such as collision rate, packet delay, and throughput. We find a near-linear relationship between p_{co} and the metrics, which suggests that p_{co} can be used as an appropriate performance indicator itself. Finally, we apply our analysis to solving a channel bandwidth allocation problem, where we derive optimal schemes and provide general guidelines on bandwidth allocation for DISH networks.

Wireless community networks, where users share wireless bandwidth is attracting tremendous interest from academia and industry. Companies such as FON have been successful in attracting large communities of users. However, solutions such as FON either require users to buy specialized FON routers or firmware modifications to existing routers. In this paper we propose a solution which requires no such sophisticated hardware. An alternative is to provide a solution which requires users to download a client software on to their PCs. While the solution appears simple it raises several issues of incentivizing users to share their bandwidth and also issues of preventing users from cheating behaviors which give them an unfair advantage. In this paper, we propose a system and solution which (i) requires only software downloads on PCs, (ii) is robust to tampering of the software, and intermittent monitoring of an access point by the owner, (iii) a credit based mechanism whereby users earn credits for sharing bandwidth and punishment and pricing mechanism whereby users are charged at a higher price whenever they are caught misbehaving. By making simple but plausible assumptions about user behavior, we show via analysis and extensive simulations that the system converges to a Pareto optimal Nash equilibrium. We further validate our system model, by running trace driven simulations on real world data. We believe that the solution provided by Wi-Sh is an attractive and more credible alternative to solutions such as FON.

In November 2008, the FCC ruled that the digital TV whitespaces be used for unlicensed access. This is an exciting development because DTV whitespaces are in the low frequency range (50-698 MHz) compared to typical cellular and ISM bands, thus resulting in much better propagation characteristics and much higher spectral efficiencies. The FCC has also mandated certain guidelines for short range unlicensed access, so as to avoid any interference to DTV receivers. We consider the problem of WiFi like access (popularly referred to as WiFi 2.0) for enterprizes. We assume that the access points and client devices are equipped with cognitive radios, i.e., they can adaptively choose the center frequency, bandwidth and ower of operation. The access points can be equipped with one or more radios. Our goal is to design a complete system, which (i) does not violate the FCC mandate, (ii) dynamically assigns center frequency and bandwidth to each access point based on their demands and (iii) squeezes the maximum efficiency from the available spectrum. This problem is far more general than prior work that investigated dynamic spectrum allocation in cellular and ISM bands, due to the non-homogenous nature of the whitespaces, i.e., different whitespace widths in different parts of the spectrum and the large range of frequency bands with different propagation characteristics. This calls for a more holistic approach to system design that also accounts for frequency dependent propagation characteristics and radio frontend characteristics. In this paper, we first propose design rules for holistic system design. We then describe an architecture derived from our design rules. Finally we propose demand based dynamic spectrum allocation algorithms with provable worst case guarantees. We provide extensive simulation results showing that (i) the performance of our algorithm is within 94% of the optimal in typical settings and (ii) and the DTV whitespaces can provide significantly higher data rates compared to the 2.4GHz ISM band. Our approach is general enough for designing any system with access to a wide range of spectrum.

Abstract In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into some sensor covers such that each cover can monitor all targets and the covers are activated sequentially. In this paper, we propose to provide information coverage instead of the conventional sensing disk coverage for target. The notion of information coverage is based on estimation theory to exploit the collaborative nature of geographically distributed sensors. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor. This change of the problem settings complicates the solutions compared to that by using a disk coverage model. We first define the target information coverage (TIC) problem and prove its NP‐completeness. We then propose a heuristic to approximately solve our problem. Simulation results show that our heuristic is better than an existing algorithm and is close to the upper bound when only the sensing disk coverage model is used. Furthermore, simulation results also show that the network lifetime can be significantly improved by using the notion of information coverage compared with that by using the conventional definition of sensing disk coverage. Copyright © 2008 John Wiley & Sons, Ltd.

Low latency anonymity systems are susceptive to traffic analysis attacks. In this paper, we propose a dependent link padding scheme to protect anonymity systems from traffic analysis attacks while providing a strict delay bound. The covering traffic generated by our scheme uses the minimum sending rate to provide full anonymity for a given set of flows. The relationship between user anonymity and the minimum covering traffic rate is then studied via analysis and simulation. When user flows are Poisson processes with the same sending rate, the minimum covering traffic rate to provide full anonymity to m users is O(log m). For Pareto traffic, we show that the rate of the covering traffic converges to a constant when the number of flows goes to infinity. Finally, we use real Internet trace files to study the behavior of our algorithm when user flows have different rates.

For long, node cooperation has been exploited as a data relaying mechanism. However, the wireless channel allows for much richer interaction between nodes. One such scenario is in a multi-channel environment, where transmitter-receiver pairs may make incorrect decisions (e.g., in selecting channels) but idle neighbors could help by sharing information to prevent undesirable consequences (e.g., data collisions). This represents a Distributed Information SHaring (DISH) mechanism for cooperation and suggests new ways of designing cooperative protocols. However, what is lacking is a theoretical understanding of this new notion of cooperation. In this paper, we view cooperation as a network resource and evaluate the availability of cooperation via a metric, pco, the probability of obtaining cooperation. First, we analytically evaluate pco in the context of multi-channel multi-hop wireless networks. Second, we verify our analysis via simulations and the results show that our analysis accurately characterizes the behavior of pco as a function of underlying network parameters. This step also yields important insights into DISH with respect to network dynamics. Third, we investigate the correlation between pco and network performance in terms of collision rate, packet delay, and throughput. The results indicate a near-linear relationship, which may significantly simplify performance analysis for cooperative networks and suggests that pco be used as an appropriate performance indicator itself. Throughout this work, we utilize, as appropriate, three different DISH contexts - model-based DISH, ideal DISH, and real DISH - to explore pco.

In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method. We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 - 1/m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. "as hard as that of finding a local optimum in any local search problem with efficient computable neighbors". Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria.

In centralized wireless networks, reducing the transmission power normally leads to higher network transport throughput. In this paper, we investigate power control in a different scenario, where the network adopts distributed MAC layer coordination mechanisms. We first consider widely adopted RTS/CTS based MAC protocols. We show that an optimal power control protocol should use higher transmission power than the "just enough" power in order to improve spatial utilization. The optimal protocol has a minimal transmission floor area of Theta(dijdmax), where dmaxis the maximal transmission range and dijis the link length. This surprisingly implies that if a long link is broken into several short links, then the sum of the transmission floors reserved by the short links is still comparable to that reserved by the long link. Thus, using short links does not necessarily lead to higher throughput. Another consequence of this is that, with the optimal RTS/CTS based MAC, rate control can at best provide a factor of 2 improvement in transport throughput. We then extend our results to other distributed MAC protocols which uses physical carrier sensing or busy-tone as the control signal. Our simulation results show that the optimal power controlled scheme outperforms other popular MAC layer power control protocols.

This paper considers the coverage problem for hybrid networks which comprise both static and mobile sensors. The mobile sensors in our network only have limited mobility, i.e., they can move only once over a short distance. In random static sensor networks, sensor density should increase as O(log L + k log log L) to provide k-coverage in a network with a size of L. As an alternative, an all-mobile network can provide k-coverage with a constant density of O(k), independent of network size L. We show that the maximum distance for mobile sensors is O( 1/radic(k) log3/4(kL)). We then propose a hybrid network structure, comprising static sensors and a small fraction of O( 1/radic(k)) of mobile sensors. For this network structure, we prove that k-coverage is also achievable with a constant sensor density of O(k). Furthermore, for this hybrid structure, we prove that the maximum distance which any mobile sensor has to move is bounded as O(log(3/4)L). We then propose a distributed relocation algorithm, where each mobile sensor only requires local information in order to optimally relocate itself. We verify our analysis via extensive numerical evaluations and show an implementation of the mobility algorithm on real mobile sensor platforms.

We propose MAX, a system that facilitates human-centric search of the physical world. Instead of organizing objects a priori, it allows humans to search for and locate them as needed. Designed for the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient searching of any tagged object, MAX provides location information in a form natural to humans, that is, with reference to identifiable landmarks (such as, “on the dining table”) rather than precise coordinates. In the system, all physical objects—from documents to clothing—can be tagged, users then locate objects using an intuitive search interface. To make searching efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), substations (bound to landmarks), and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces. It requires minimal initial configuration, and is robust to reconfiguration of the physical space. We also present a methodology to design energy-optimal and delay-optimal query protocols for a variety of device choices, this optimizes system performance, and affords insight into the appropriate actions for various scenarios. We have implemented a simple prototype of MAX, demonstrating the feasibility of the system for human-centric search over several locations across a wide area. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.

Target tracking and localization are important applications in wireless sensor networks. Although the coverage problem for target detection has been intensively studied, few consider the coverage problem from the perspective of target localization. In this paper, we propose two methods to estimate the lower bound of sensor density to guarantee a bounded localization error over the sensing field. We first convert the coverage problem for localization to a conventional disk coverage problem, where the sensing area is a disk centered at the sensor. Our results show that the disk coverage model requires 4 times more sensors for localization compared to detection applications. We then introduce the idea of sector coverage to tighten the lower bound. The lower bound derived through sector coverage is 2 times less than through disk coverage. A distributed sector coverage algorithm is then proposed in this paper. Compared to disk coverage, sector coverage requires more computations. However, it provides more accurate density estimations than the disk model. Numerical evaluations show that the density bound derived through our sector coverage model is tight.

In this paper we consider the coverage problem for target detection applications in wireless sensor networks. Unlike conventional coverage problems which assume sensing regions are disks around sensors, we define the sensing region according to detection constraints in terms of false alarm probability and missing probability. We show that exploiting cooperation between sensors can extend the overall sensing region while maintain the same constraints on false alarm probability and missing probability. We then propose an energy efficient cooperative detection scheme and study the trade-offs on energy consumption between cooperative and non-cooperative schemes. The cooperative scheme can use half the number of sensors to monitor the whole fleld compared to disk model in networks deployed on grids. We also study the communication overheads incurred by the co-operative scheme, and show that only cooperation between limited number of nearby sensors is profitable in terms of energy consumption. In our simulations on randomly deployed networks, cooperation reduces the number of sensors to cover the area by 30% and nearly doubles the number of disjoint sensor sets where each can fully cover the area. Appropriately trading off energy consumption with coverage extension, our cooperative detection scheme can increase the network lifetime by nearly 70%.

This paper studies the problem of how to maximize the network lifetime while preserving network coverage for an energy constrained wireless sensor network. We consider network coverage from an our recently proposed information coverage model [1] other than the conventional sensing disk model. The lifetime maximization problem is modeled as a nonlinear programming problem and is shown NP-Complete. We then propose a family of greedy algorithms to allocate sensors different roles such that different sensors may consume different amount of energies in different intervals to prolong network lifetime while still guaranteeing application requirements. Simulation results suggest that the algorithm with the best balancing between communication energy consumption and area coverage requirement has the highest network lifetime.

In this paper, we study the coverage problem for hybrid networks which comprise both static and mobile sensors. We consider mobile sensors with limited mobility, i.e., they can move only once over a short distance. Such mobiles are simple and cheap compared to sophisticated mobile robots. In conventional static sensor networks, for a random deployment, the sensor density should increase as O(log L + k log log L) to provide k-coverage in a network with a size of L. As an alternative, an all mobile sensor network can provide k-coverage over the field with a constant density of O(k), independent of network size L. We show that the maximum distance that any mobile sensor will have to move is O(1 over √k log 3 over 4 (kL)). We then propose a hybrid network structure, comprising static sensors and a small fraction of O(1 over √(k)) of mobile sensors. For this network structure, we prove that k-coverage is achievable with a constant sensor density of O(k), independent of network size L. Furthermore, for this hybrid structure, we prove that the maximum distance which any mobile sensor has to move is bounded as O(log3 over 4 L). We then propose a distributed relocation algorithm, where each mobile sensor only requires local information in order to optimally relocate itself and characterize the algorithm's computational complexity and message overhead. Finally, we verify our analysis via extensive numerical evaluations.

Recently, a new notion of cooperation was proposed to solve multi-channel coordination problems. When a transmit-receive pair wishes to initiate communication, neighboring nodes share their knowledge of channel usage. This helps to substantially reduce collisions and increases throughput significantly. However, it comes at the cost of increased energy consumption since idle nodes have to stay awake to overhear and acquire channel usage information. In fact this can be as high as 264% of a power-saving protocol without cooperation. In this paper, we propose a strategy called altruistic cooperation for cooperative multi-channel MAC protocols to conserve energy. The core idea is to introduce specialized nodes called altruists in the network whose only role is to acquire and share channel usage information. All other nodes, termed peers, go in to the sleep mode when idle. This strategy seems naive because it needs additional nodes to be deployed. In fact, it is unclear whether a desirable throughput-energy trade-off can be achieved and whether the cost of additional nodes can offset the performance gain. We perform a close study on this strategy in terms of three aspects: network deployment, cost efficiency, and system performance. Our study indicates that only a few additional nodes need to be deployed and cost efficiency is more than doubled in terms of a new metric called bit-price ratio that we propose. By using the strategy, a cooperative protocol is found to save up to 70% energy while not compromising throughput.

In many delay tolerant applications, information is opportunistically exchanged between mobile devices who encounter each other. In order to effect such information exchange, mobile devices must have knowledge of other devices in their vicinity. We consider scenarios in which there is no infrastructure and devices must probe their environment to discover other devices. This can be an extremely energy consuming process and highlights the need for energy conscious contact probing mechanisms. If devices probe very infrequently, they might miss many of their contacts. On the other hand, frequent contact probing might be energy inefficient. In this paper, we investigate the trade-off between the probability of missing a contact and the contact probing frequency. First, via theoretical analysis, we characterize the trade-off between the probability of a missed contact and the contact probing interval for stationary processes. Next, for time varying contact arrival rates, we provide an optimization framework to compute the optimal contact probing interval as a function of the arrival rate. We characterize real world contact patterns via Bluetooth phone contact logging experiments and show that the contact arrival process is self-similar. We design STAR, a contact probing algorithm which adapts to the contact arrival process. Via trace driven simulations on our experimental data, we show that STAR consumes three times less energy when compared to a constant contact probing interval scheme.

Energy limitations in wireless sensor networks and the need for low latency in many applications require a unified approach in the design of network protocols. In this paper, we propose a distributed wakeup schedule to accomplish a new topology control scheme. The aim is to increase the longevity of the network for a given upper bound on the average end-to-end delay. In the proposed scheme neither localization nor synchronization is required and only local information is used. In addition to its simplicity of implementation, its energy overhead is negligible and it implicitly determines the routing paths. Our simulation results show that this protocol achieve significant improvement in the network lifetime compared to SPAN, an existing topology control mechanism.

Coverage is an important issue in wireless sensor networks. The most commonly used coverage model in the literature defines a point to be covered if its Euclidian distance to at least one sensor is less than a fixed threshold. This is a conservative definition of coverage which implicitly assumes that each sensor makes a decision independent of other sensors in the field. Sensors can cooperate to make an accurate estimation, even if any single sensor is unable to do so. We have previously proposed a new notion of information coverage and investigated its properties. In this paper, we study sensor density requirements for complete information coverage of a field with random sensor deployment. We provide an upper bound on the probability that an arbitrary point in a randomly deployed sensor field is not information covered and find the relationship between the sensor density and the average field vacancy. Simulation results validate our theoretical analysis and show that significant savings in terms of sensor density for complete coverage can be achieved with information coverage.

Medium access control (MAC) protocols have been studied under different contexts for several years now. In all these MAC protocols, nodes make independent decisions on when to transmit a packet and when to back-off from transmission. In this paper, we introduce the notion of node cooperation into MAC protocols. Cooperation adds a new degree of freedom which has not been explored before. Specifically we study the design of cooperative MAC protocols in an environment where each node is equipped with a single transceiver and has multiple channels to choose from. Nodes cooperate by helping each other select a free channel to use. We show that this simple idea of cooperation has several qualitative and quantitative advantages. Our cooperative asynchronous multi-channel MAC protocol (CAM-MAC) is extremely simple to implement and, unlike other multi-channel MAC protocols, is naturally asynchronous. We conduct extensive simulation experiments. We first compare CAM-MAC with IEEE 802.11b and a version of CAM-MAC with the cooperation element removed. We use this to show the value of cooperation. Our results show significant improvement in terms of number of collisions and throughput for CAM-MAC. We also compare our protocol with MMAC and SSCH and show that CAM-MAC significantly outperforms both of them.

Target tracking and localization are important applications in wireless sensor networks. Although the coverage problem for target detection has been intensively studied, few consider the coverage problem from the perspective of target localization. In this paper, we propose two methods to estimate the necessary sensor density which can guarantee a localization error bound over the sensing field. In the first method, we convert the coverage problem for localization to a conventional disk coverage problem, where the sensing area is a disk centered around the sensor. Our results show that the disk coverage model requires 4 times more sensors for tracking compared to detection applications. We then introduce the idea of sector coverage, which can satisfy the same coverage conditions with 2 times less sensors over the disk coverage approach. This shows that conventional disk coverage model is insufficient for tracking applications, since it overestimates the sensor density by two times. Simulation results show that the network density requirements derived through sector coverage are close to the actual need for target tracking applications.

Characterizing mobility or contact patterns in a campus environment is of interest for a variety of reasons. Existing studies of these patterns can be classified into two basic approaches - model based and measurement based. The model based approach involves constructing a mathematical model to generate movement patterns while the measurement based approach measures locations and proximity of wireless devices to infer mobility patterns. In this paper, we take a completely different approach. First we obtain the class schedules and class rosters from a university-wide Intranet learning portal, and use this information to infer contacts made between students. The value of our approach is in the population size involved in the study, where contact patterns among 22341 students are analyzed. This paper presents the characteristics of these contact patterns, and explores how these patterns affect three scenarios. We first look at the characteristics from the DTN perspective, where we study inter-contact time and time distance between pairs of students. Next, we present how these characteristics impact the spread of mobile computer viruses, and show that viruses can spread to virtually the entire student population within a day. Finally, we consider aggregation of information from a large number of mobile, distributed sources, and demonstrate that the contact patterns can be exploited to design efficient aggregation algorithms, in which only a small number of nodes (less than 0.5%) is needed to aggregate a large fraction (over 90%) of the data.

An important application of wireless sensor networks is to perform the monitoring missions, for example, to monitor some targets of interests at all times. Sensors are often equipped with non-rechargeable batteries with limited energy and energy saving is a critical aspect for wireless sensor networks. If a target is monitored simultaneously by serval sensors, some of them can be switched off to save energy without causing mission failure and by which their operational times as well as the network lifetime can be prolonged. In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into sensor covers such that each cover can monitor all targets and the covers are activated successively. In this paper, we propose to use the notion of information coverage which is based on the estimation theory to exploit the collaborative nature of wireless sensor networks, instead of using the conventional definition of coverage. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor.

In this paper, we address the problem of energy efficient packet scheduling in a wireless environment. We consider a wireless transmitter which is limited by its finite battery resource. Our objective is to design a transmission schedule that maximizes battery lifetime subject to some delay constraints. To achieve this, we exploit two previously unconnected ideas: (i) channel coding can be used to conserve energy by transmitting at reduced power levels over longer durations; (ii) electro-chemical mechanisms in batteries allow them to recover energy during idle periods. While the first idea favors extending transmission durations, the second idea requires the transmitter to be idle to allow for recovery. In other words, bursty packet transmissions interspersed with idle periods extend battery life. Therefore, a strategy which is based entirely on either one or the other idea is not optimal. We provide a framework to merge the two ideas. We consider two kinds of delay constraints, one a deadline constraint and the other an average delay constraint and show that energy aware scheduling strategies for both these scenarios can result in significant energy savings.

People often seek information by asking other people even when they have access to vast reservoirs of information such as the Internet and libraries. This is because people are great sources of unique information, especially that which is location-specific, community-specific and time-specific. Social networking is effective because this type of information is often not easily available anywhere else. In this paper, we conceive a wireless virtual social network which mimics the way people seek information via social networking. PeopleNet is a simple, scalable and low-cost architecture for efficient information search in a distributed manner. It uses the infrastructure to propagate queries of a given type to users in specific geographic locations, called bazaars. Within each bazaar, the query is further propagated between neighboring nodes via peer-to-peer connectivity until it finds a matching query. The PeopleNet architecture can overlay easily on existing cellular infrastructure and entails minimal software installation. We identify three metrics for system performance: (i) probability of a match, (ii) time to find a match and (iii) number of matches found by a query. We describe two simple models, called the swap and spread models, for query propagation within a bazaar. We qualitatively argue that the swap model is better with respect to the performance metrics identified and demonstrate this via simulations. Next, we compute analytically the probability of match for the swap model. We show that the probability of match can be significantly improved if, prior to swapping queries, the nodes exchange some limited information about their buffer contents. We propose a simple greedy algorithm which uses this limited information to decide which queries to swap. We show via simulation that this algorithm achieves significantly better performance. Overall our results demonstrate that PeopleNet, with its bazaar concept and peer-to-peer query propagation, can provide a simple and efficient mechanism for seeking information.

In this paper we investigate the benefits of a heterogeneous architecture for wireless sensor networks composed of a few resource rich mobile nodes and a large number of simple static nodes. These mobile nodes can either act as mobile relays or mobile sinks. To investigate the performance of these two options and the trade-offs associated with these two options, we first consider a finite network. We then compute the lifetime for different routing algorithms for three cases (i) when the network is all static (ii) when there is one mobile sink and (iii) when there is one mobile relay. We find that using the mobile node as a sink results in the maximum improvement in lifetime. We contend however that in hostile terrains, it might not always be possible for the sink to be mobile. We then investigate the performance of a large dense network with one mobile relay and show that the improvement in network lifetime over an all static network is upper bounded by a factor of four. Also, the proof implies that the mobile relay needs to stay only within a two hop radius of the sink. We then construct a joint mobility and routing algorithm which comes close to the upper bound. However this algorithm requires all the nodes in the network to be aware of the location of the mobile node. We then proposed an alternative algorithm, which achieves the same performance, but requires only a limited number of nodes in the network to be aware of the location of the mobile. We finally compare the performance of the mobile relay and mobile sink and show that for a densely deployed sensor field of radius R hops, we require O(R) mobile relays to achieve the same performance as the mobile sink.

MAX is a system that facilitates human-centric search of the physical world. It allows humans to search for and locate objects as and when they need it instead of organizing them a priori. It provides location information in a form natural to humans, i.e., with reference to identifiable landmarks (e.g., on the dining table) rather than precise coordinates. MAX was designed with the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient search of any tagged object. In the system, all physical objects, from documents to clothing, can be tagged and people locate objects using an intuitive search interface. To make search efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), sub-stations (bound to landmarks) and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces.MAX requires minimal initial configuration, and is robust to reconfiguration of the physical space. To optimize system performance, we present a methodology to design energy and delay optimal query protocols for a variety of device choices. We have implemented MAX using Crossbow motes and conducted user trials in a 5m by 5m cluttered office. The user feedback was positive, demonstrating the feasibility of MAX for human-centric search. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

In this paper, we address the problem of energy efficiency in wireless ad hoc networks. We consider an ad hoc network comprising a set of sources, communicating with their destinations using multiple routes. Each source is associated with a utility function which increases with the total traffic flowing over the available source-destination routes. The network lifetime is defined as the time until the first node in the network runs out of energy. We formulate the problem as one of maximizing the sum of the source utilities subject to a required constraint on the network lifetime. We present a primal formulation of the problem, which uses penalty functions to take into account the system constraints, and we introduce a new methodology for solving the problem. The proposed approach leads to a flow control algorithm, which provides the optimal source rates and can be easily implemented in a distributed manner. When compared with the minimum transmission energy routing scheme, the proposed algorithm gives significantly higher source rates for the same network lifetime guarantee.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal throughput that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called generous tit-for-tat (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

In this paper, we address the problem of energy-conscious cache placement in wireless ad hoc networks. We consider a network comprising a server with an interface to the wired network, and some nodes requiring access to the information stored at the server. In order to reduce access latency in such a communication environment, an effective strategy is caching the server information at some nodes distributed across the network. Caching, however, can considerably impact the system energy expenditure; for instance, disseminating information incurs additional energy burden. Since wireless devices have limited amounts of available energy, we need to design caching strategies that optimally trade-off between energy consumption and access latency. We pose our problem as an integer linear program. We show that this problem is the same as a special case of the connected facility location problem, which is known to be NP-hard. We devise a polynomial time algorithm which provides a sub-optimal solution. The proposed algorithm applies to any arbitrary network topology and can be implemented in a distributed and asynchronous manner. In the case of a tree topology, our algorithm gives the optimal solution. In the case of an arbitrary topology, it finds a feasible solution with an objective function value within a factor of 6 of the optimal value. This performance is very close to the best approximate solution known today, which is obtained in a centralized manner. We compare the performance of our algorithm against three candidate caching schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes.

Wireless networking has experienced a great deal of popularity, and significant advances have been made in wireless technology. However, energy efficiency of radio communication systems is still a critical issue due to the limited battery capacity of portable devices. In this paper, we deal with the charge recovery effect that takes place in electrochemical cells and show how we can take advantage of this mechanism to increase the energy delivered by a battery. Then, we present energy-aware traffic shaping techniques, as well as scheduling and routing algorithms, which exploit the battery recovery effect.

In this paper, we address the problem of energy efficient packet scheduling in a wireless environment. We consider a wireless transmitter which is limited by its finite battery resource. Our objective is to design a transmission schedule that maximizes battery lifetime subject to some delay constraints. To achieve this, we exploit two previously unconnected ideas: (i) channel coding can be used to conserve energy by transmitting at reduced power levels over longer durations; (ii) electro-chemical mechanisms in batteries allow them to recover energy during idle periods. While the first idea favors extending transmission durations, the second idea requires the transmitter to be idle to allow for recovery. Therefore, a strategy which is based entirely on either one or the other idea is not optimal. We provide a framework to merge these two ideas. We consider two kinds of delay constraints, one a deadline constraint and the other an average delay constraint and show that energy aware scheduling strategies for both these scenarios can result in significant energy savings.

In this paper, we address the problem of energy efficiency in ad hoc wireless networks. We consider a network that is shared by a set of sources, each one communicating with its corresponding destination using multiple routes. Each source is associated with a utility function which increases with the total traffic flowing over the available source-destination routes. The network lifetime is defined as the time until the first node in the network runs out of energy. We formulate the problem as one of maximizing the sum of the sources' utilities subject to the required constraint on network lifetime. We present a primal formulation of the problem, which uses penalty functions to take into account the system constraints, and we introduce a new methodology for solving the problem. The proposed approach leads to a flow control algorithm, which provides the optimal sources' rate and can be easily implemented in a distributed manner. When compared with the minimum transmission energy routing scheme, the proposed algorithm gives significantly higher sources' rates for same network lifetime guarantee.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. However, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete non-cooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e. their actions are strictly determined by self-interest, and that each node is associated with a minimum lifetime constraint. Then, we are able to determine the optimal throughput that each node should receive, and we define this to be the rational Pareto optimal operating point. We propose a distributed and scalable acceptance algorithm, which is used by the nodes to decide whether to accept or reject a relay request. The algorithm results in a Nash equilibrium, and we prove that the system converges to the rational and optimal operating point.

In an effort to conserve energy, mobile hosts wake up periodically to serve incoming traffic. This gives rise to a trade-off between energy consumption and delay. However, the deterministic strategy of current systems might not yield the desired performance. We show that knowledge of the statistical characteristics of incoming traffic can be used to better meet the energy and delay requirements of the mobile node. We consider zero-buffer and buffered models. We propose some strategies to improve the energy efficiency and study the related trade-offs. We also introduce a new metric for energy efficiency and derive explicit expressions for the same. Our results prove that significant gains accrue by employing intelligent wake-up schemes.

In a tiered cellular system the cells are split into two regions: the inner tier and the outer tier. These two regions can be treated as logically separate cells. Due to the smaller radii of the inner tier cells, a frequency plan with greater reuse can be employed for the inner tier cells than for the original (untiered) system, or the outer tier cells. This results in a net increase in the call carrying capacity of the system due to tiering. In this paper, we propose a method for the determination of the frequency plan for a tiered system while maintaining the specified call quality. The call quality is assumed to be specified in the form of a minimum carrier-to-interference ratio that is to be met at each base station, under the worst-case locations of the mobiles. Under these co-channel interference constraints, the cellular system can be modeled as a hypergraph. The frequency planning method involves generating the maximal independent sets (MISs) of this hypergraph and solving a linear program whose constraints are determined by these MISs. Moreover, these frequency plans can be shown to be optimal (have the greatest call carrying capacity) asymptotically, that is, when a very large number of frequencies are available. The method is applicable to systems with either omnidirectional or sectored antennas. However the number of MISs is significantly larger in the sectored case and thus we use only a fraction of them which may make the resulting frequency plans somewhat sub-optimal. The same remark holds for systems with a large number of cells. Nevertheless, in all cases, the frequency plans obey the specified co-channel interference restrictions. The other parameters which affect the performance gain due to tiering are the inner tier area and transmit power. In a specific example, we have evaluated the optimal inner tier area and transmit power and found that their optimization results in significant capacity gains.