IEEE Transactions on Mobile Computing

IEEE Transactions on Mobile Computing - January 2010 (Vol. 9, No. 1)

PrePrint: Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

Existing work on placing additional relay nodes in wireless sensor networks to improve network connectivity typically assumes homogeneous wireless sensor nodes with an identical transmission radius. In contrast, this paper addresses the problem of deploying relay nodes to provide fault-tolerance with higher network connectivity in {\em heterogeneous} wireless sensor networks, where sensor nodes possess different transmission radii. Such problems can be categorized as: (1) {\em full} fault-tolerance, which aims to deploy a minimum number of relay nodes to establish $k$ $(k \geq 1)$ vertex-disjoint paths between every pair of sensor and/or relay nodes; (2) {\em partial} fault-tolerance, which aims to deploy a minimum number of relay nodes to establish $k$ $(k \geq 1)$ vertex-disjoint paths only between every pair of sensor nodes. Due to the different transmission radii of sensors, these problems are further complicated by the existence of two different kinds of communication paths, namely {\em two-way} paths, along which wireless communications exist in both directions; and {\em one-way} paths, along which wireless communications exist in only one direction. This paper comprehensively analyzes the range of problems introduced by the different levels of fault-tolerance coupled with the different types of path, and presents approximation algorithms.

PrePrint: DCAR: Distributed Coding-Aware Routing in Wireless Networks

Recently, there has been a growing interest of using network coding to improve the performance of wireless networks, for example, authors of \cite{xor} proposed the practical wireless network coding system called COPE, which demonstrated the throughput gain achieved by network coding. However, COPE has two fundamental limitations: (a) the coding opportunity is crucially dependent on the established routes; (b) the coding structure in COPE is limited within a two-hop region only. The aim of this paper is to overcome these limitations. In particular, we propose DCAR, the Distributed Coding-Aware Routing mechanism which enables (1) the discovery for available paths between a given source and destination, and (2) the detection for potential network coding opportunities over much wider network region. On interesting result is that DCAR has the capability to discover high throughput paths with coding opportunities while conventional wireless network routing protocols fail to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the "two-hop" coding limitation in COPE. We also propose a novel routing metric called Coding-aware Routing Metric (CRM) which facilitates the performance comparison between "coding-possible" and "coding-impossible" paths. We implement the DCAR system in ns-2 and carry out extensive evaluation.

PrePrint: Energy Efficient Reprogramming of a Swarm of Mobile Sensors

Existing code update protocols for reprogramming nodes in a sensor network are either unsuitable or inefficient when used in a mobile environment. In this paper, we propose ReMo, an energy efficient, multihop reprogramming protocol for mobile sensor networks. Without making any assumptions on the location of nodes, ReMo uses the LQI and RSSI measurements of received packets to estimate link qualities and relative distances with neighbors in order to select the best node for code exchange. The protocol is based on a probabilistic broadcast paradigm with the mobile nodes smoothly modifying their advertisement transmission rates based on the dynamic changes in network density, thereby saving valuable energy. Contrary to previous protocols, ReMo downloads pages regardless of their order, thus, exploiting the mobility of the nodes and facilitating a fast transfer of the code. Our simulation results show significant improvement in reprogramming time and number of message transmissions over other existing protocols under different settings of network mobility. Our implementation results of ReMo on a testbed of SunSPOTs also showcase its better performance than existing reprogramming protocols in terms of transfer time and number of message transmissions.

PrePrint: A Scalable and Energy-Efficient Context Monitoring Framework for Mobile Personal Sensor Networks

The key feature of many emerging pervasive applications is to proactively provide services to mobile individuals. One major challenge in providing users with proactive services lies in continuously monitoring users’ context based on numerous sensors in their PAN/BAN environments. The context monitoring in such environments imposes heavy workloads on mobile devices and sensor nodes with limited computing and battery power. We present SeeMon, a scalable and energy-efficient context monitoring framework for sensor-rich, resource-limited mobile environments. Running on a personal mobile device, SeeMon effectively performs context monitoring involving numerous sensors and applications. On top of SeeMon, multiple applications on the mobile device can proactively understand users’ contexts and react appropriately. This paper proposes a novel context monitoring approach that provides efficient processing and sensor control mechanisms. We implement and test a prototype system on two mobile devices: a UMPC and a wearable device with a diverse set of sensors. Example applications are also developed based on the implemented system. Experimental results show that SeeMon achieves a high level of scalability and energy efficiency.

PrePrint: Schedule Adaptation of Low-Power-Listening Protocols for Wireless Sensor Networks

Many recent advances in MAC protocols for wireless sensor networks have been proposed to reduce idle listening, an energy wasteful state of the radio. Low-Power-Listening (LPL) protocols transmit packets for t_i s (the "inter-listening interval"), thereby allowing nodes to sleep for long periods of time between channel probes. The inter-listening interval as well as the particular type of LPL protocol should be well matched to the network conditions. In this paper, we propose network-aware adaptation of the specific succession of repeated packets over the t_i interval (the "MAC schedule"), which yields significant energy savings. Moreover, some LPL protocols interrupt communication between the sender and the receiver after the data packet has been successfully received. We propose a new and simple adaptation of the "transmit / receive schedule" to synchronize nodes on a slowly changing path so that energy consumption and delay are further reduced, at no cost of overhead in most cases. Our results show that using network-aware adaptation of the MAC schedule provides up to 30% increase in lifetime for different traffic scenarios. Additional adaptation of the transmit / receive schedule to automatically synchronize the nodes can reduce packet delivery delays by up to 50%, providing an additional decrease in energy consumption of 18%

PrePrint: Modeling Power Saving Protocols for Multicast Services in 802.11 Wireless LANs

In recent years, multiple power saving (PS) protocols have been proposed in the 802.11 standards to save energy for mobile devices. Many works have been carried out on testbeds or simulation platforms to evaluate their performances. However, there is a lack of accurate theoretical models to analyze the performance for these protocols. In an effort to fill this gap, we present a Markov chain based model to analytically study these PS protocols, with its focus on multicast services. The proposed model successfully captures the key characteristic of the power saving systems: the data delivery procedure starts periodically at the previously negotiated time, but ends at a rather random time with its distribution depending on the ending time of data delivery in the last delivery period and the the arrival rate of incoming traffic. Under the poisson assumption for incoming traffic and in light to moderate traffic loads, the amount of data delivered between consecutive delivery periods possesses the Markov property, which builds up our Markov chain model. For incoming traffic with long range dependence, a multi-state Markov Modulated Poisson Process (MMPP) is used to approximate the traffic, making the model valid in more general cases.

PrePrint: On Multihop Distances in Wireless Sensor Networks with Random Node Locations

Location and inter-sensor distance estimations are important functions for the operation of wireless sensor networks, especially when protocols can benefit from the distance information prior to network deployment. The maximum multihop distance that can be covered in a given number of hops in a sensor network is one such parameter related with coverage area, delay, and minimal multihop transmission energy consumption estimations. In randomly deployed sensor networks, inter-sensor distances are random variables. Hence, their evaluations require probabilistic methods, and distance models should involve investigation of distance distribution functions. Current literature on analytical modeling of the maximum distance distribution is limited to one-dimensional networks using the Gaussian pdf. However, determination of the maximum multihop distance distribution in two dimensional networks is a quite complex problem. Furthermore, distance distributions in two dimensional networks are not accurately modeled by the Gaussian pdf. Hence, we propose a greedy method of distance maximization and evaluate the distribution of the obtained multihop distance through analytical approximations and simulations.

PrePrint: Energy-Efficient VoIP over Wireless LANs

Emerging dual-mode phones incorporate a Wireless LAN (WLAN) interface along with the traditional cellular interface. The additional benefits of the WLAN interface are, however, likely to be outweighed by its greater rate of energy consumption. This is especially of concern when real-time applications, that result in continuous traffic, are involved. WLAN radios typically conserve energy by staying in sleep mode. With real-time applications like Voice over Internet Protocol (VoIP), this can be challenging since packets delayed above a threshold are lost. Moreover, the continuous nature of traffic makes it difficult for the radio to stay in the lower power sleep mode enough to reduce energy consumption significantly. In this work we propose the GreenCall algorithm to derive sleep/wakeup schedules for the WLAN radio to save energy during VoIP calls while ensuring that application quality is preserved within acceptable levels of users. We evaluate GreenCall on commodity hardware and study its performance over diverse network paths and describe our experiences in the process. We further extensively investigate the effect of different application parameters on possible energy savings through trace-based simulations. We show that, in spite of the interactive, real-time nature of voice, energy consumption during calls can be reduced by close to 80% in most instances.

PrePrint: Distributed Localization Scheme for Mobile Sensor Networks

Localization is an essential and important research issue in wireless sensor networks (WSNs). Most localization schemes focus on static sensor networks. However, mobile sensors are required in some applications such that the sensed area can be enlarged. As such, a localization scheme designed for mobile sensor networks is necessary. In this paper, we propose a localization scheme to improve the localization accuracy of previous work. In this proposed scheme, the normal nodes without location information can estimate their own locations by gathering the positions of location-aware nodes (anchor nodes) and the one-hop normal nodes whose locations are estimated from the anchor nodes. In addition, we propose a scheme that predicts the moving direction of sensor nodes to increase localization accuracy. Simulation results show that the localization error in our proposed scheme is lower than the previous schemes in various mobility models and moving speeds.

PrePrint: Extended Knowledge-Based Reasoning Approach to Spectrum Sensing for Cognitive Radio

In this paper, a novel scheme for Cognitive Radio (CR) spectrum sensing in Medium Access Control (MAC) layer, called Extended Knowledge-Based Reasoning (EKBR), is proposed. The target of EKBR is to improve the fine sensing efficiency by jointly considering a number of network states and environmental statistics, including fast sensing results, short-term statistical information, channel quality, data transmission rate, and channel contention characteristics. This is for a better estimation on the optimal range of spectrum for fine sensing so as to adaptively reduce the overall channel sensing time. Performance analysis is conducted on the proposed EKBR scheme using a multi-dimensional absorbing Markov chain to evaluate various performance metrics of interest, such as average sensing delay (or referred to as sensing overhead in the study), average data transmission rate, and percentage of missed spectrum opportunities. Numerical results show that the proposed EKBR scheme achieves better performance than that by the state-or-the-art techniques while yielding less computation complexity and sensing overhead.

PrePrint: Local Barrier Coverage in Wireless Sensor Networks

Global barrier coverage is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors cannot locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage. Although local barrier coverage does not deterministically guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called Localized Barrier Coverage Protocol (LBCP). We prove that LBCP guarantees local barrier coverage and show that LBCP provides close to optimal enhancement in the network lifetime, while providing global barrier coverage most of the time.

PrePrint: Exploiting and Defending Opportunistic Scheduling in Cellular Data Networks

Third Generation (3G) cellular networks take advantage of time-varying and location-dependent channel conditions of mobile users to provide broadband services. They use opportunistic scheduling to utilize spectrum efficiently under fairness and QoS constraints. Opportunistic scheduling algorithms rely on the collaboration among all mobile users to achieve their design objectives. However, we demonstrate that rogue cellular devices can exploit vulnerabilities in popular opportunistic scheduling algorithms, such as Proprotional Fair (PF) and Temporal Fair (TF), to usurp the majority of time slots in 3G networks. Our simulations show that only five rogue device per 50-user cell can use up to 90% of the time slots, and can cause two-second end-to-end inter-packet transmission delay on VoIP applications for every user in the same cell, rendering VoIP applications useless. To defend against this attack, we propose strengthening the PF and TF schedulers and a robust handoff scheme.

PrePrint: On Fast and Accurate Detection of Unauthorized Wireless Access Points Using Clock Skews

We explore the use of clock skew of a wireless local area network access point (AP) as its fingerprint to detect unauthorized APs quickly and accurately. The main goal behind using clock skews is to overcome one of the major limitations of existing solutions- the inability to effectively detect Medium Access Control (MAC) address spoofing. We calculate the clock skew of an AP from the IEEE 802.11 Time Synchronization Function (TSF) timestamps sent out in the beacon/probe response frames. We use two different methods for this purpose - one based on linear programming and the other based on least square fit. We collect TSF timestamp data from several APs in three different residential settings. Using our measurement data as well as data obtained from a large conference setting, we find that clock skews remain consistent over time for the same AP but vary significantly across APs. Furthermore, we improve the resolution of received timestamp of the frames and show that with this enhancement our methodology can find clock skews very quickly, using 50-100 packets in most of the cases. We also discuss and quantify the impact of various external factors including temperature variation, virtualization, clock source selection and NTP synchronization on clock skews.

PrePrint: Joint Routing, Channel Assignment, and Scheduling for Throughput Maximization in General Interference Models

Throughput optimization in wireless networks with multiple channels and multiple radio interfaces per node is a challenging problem. For general traffic models (given a set of source-destination pairs), optimization of throughput entails design of "efficient" routes between the given source-destination pairs, in conjunction with (i) assignment of channels to interfaces and communication links, and (ii) scheduling of non-interfering links for simultaneous transmission. Prior work has looked at restricted versions of the above problem. In this article, we design approximation algorithms for the joint routing, channel assignment, and link scheduling problem in wireless networks with general interference models. The unique contributions of our work include addressing the above joint problem in the context of physical interference model and single-path routing (wherein, traffic between a source-destination is restricted to a single path). To the best of our knowledge, ours is the first work to address the throughput maximization problem in such general contexts. For each setting, we design approximation algorithms with provable performance guarantees. We demonstrate the effectiveness of our algorithms in general contexts through simulations.

PrePrint: Optimal Patterns for Four-Connectivity And Full Coverage Wireless Sensor Networks

In this paper, we study optimal deployment in terms of sensor number needed to achieve four connectivity and full coverage under different ratios of sensors' communication range (denoted by $r_c$) to their sensing range (denoted by $r_s$). We propose a new pattern called the "Diamond" pattern, which can be viewed as a series of evolving patterns. When $r_c/r_s \ge \sqrt{3}$, the Diamond pattern coincides with the well-known triangle lattice pattern; when $r_c/r_s \leq \sqrt{2}$, it degenerates to a "Square" pattern (i.e., square grid). We prove that the pattern we propose is asymptotically optimal when $r_c/r_s > \sqrt{2}$ to achieve four connectivity and full coverage. We also discover another new deployment pattern called the ``Double-strip'' pattern. This pattern broadens the research on optimal deployment patterns from a new aspect. Our work is the first to propose an asymptotically optimal deployment pattern to achieve four connectivity and full coverage for WSNs. Our work also provides insights on how optimal patterns evolve and how to search for them.

PrePrint: Dealing With Selfishness and Moral Hazard in Non-Cooperative Wireless Networks

For non-cooperative networks in which each node is a selfish agent, certain incentives must be given to intermediate nodes to let them forward the data for others. What makes the scenario worse is that, in a multi-hop non-cooperative network, the endpoints can only observe whether or not the end-to-end transaction was successful or not, but not the individual actions of intermediate nodes. Thus, in the absence of properly designed incentive schemes, rational and selfish intermediate nodes may choose to forward data packets at a very low priority or simply drop the packets, and they could put the blame on the unreliable channel. In this paper, assuming the receiver is a trusted authority, we propose several methods that discourage the hidden actions under hidden information in multi-hop non-cooperative networks with high probability. We design several algorithmic mechanisms for a number of routing scenarios such that each selfish agent will maximize its expected utility (\ie, profit) when it \emph{truthfully} declares its \emph{type} (\ie, cost and its actions) and it truthfully follows its declared actions. Our simulations show that the payments by our mechanisms are only slightly larger than the \emph{actual cost} incurred by all intermediate nodes.

PrePrint: Intelligent Dynamic Radio Tracking in Indoor Wireless Local Area Networks

Indoor positioning is an enabling technology for delivery of location-based services in mobile computing environments. This paper proposes a positioning solution using received signal strength in indoor Wireless Local Area Networks. In this application, an explicit measurement equation and the corresponding noise statistics are unknown because of the complexity of the indoor propagation channel. To address these challenges, we introduce a new state-space Bayesian filter: the Nonparametric Information (NI) filter. This filter effectively tracks motion in situations where the Kalman filter and its variants are inapplicable, while maintaining a computational complexity comparable to that of the Kalman filter. To deal with the noisy nature of the indoor propagation environment, the NI filter is used in the design of an intelligent dynamic WLAN tracking system. The system anticipates future position values and adapts its sensing and estimation parameters accordingly. Our experimental results conducted on measurements from a real office environment indicate that the combination of the intelligent design and the NI filter results in significant improvements over the Kalman and particle filters.

PrePrint: Energy-Optimal Scheduling with Dynamic Channel Acquisition in Wireless Downlinks

We consider a wireless basestation serving users through time-varying channels. It is well-known that opportunistic scheduling with full channel state information (CSI) is throughput-optimal. However, it may not be energy-efficient when the cost of channel acquisition is high and traffic rates are low. Under the low traffic rate regime, it may be sufficient and more energy-efficient to transmit data without CSI, since no channel acquisition power is consumed. In general, we show strategies that probe channels in every slot or never probe channels in any slot are not necessarily optimal, and we must consider mixed strategies. We derive a unified scheduling algorithm that dynamically chooses to transmit data with full or no CSI based on queue backlog and channel statistics. Our methodology is general and can be extended to include timing overhead due to channel acquisition, and to treat systems that allow any subset of channels to be measured. Through Lyapunov analysis, we show our algorithm is throughput-optimal and stabilizes the downlink with optimal power consumption, regardless of the values of channel probing power, transmission power, and data rates. Through simulations, we show our algorithm is energy-efficient by balancing well between earning opportunistic scheduling gains in channel-aware mode and saving channel probing power in channel-blind mode.

PrePrint: Activity-Based Proactive Data Management in Mobile Environments

Most users in a mobile environment are moving and accessing wireless services for the activities they are currently engaged in. We propose the idea of complex activity for characterizing the continuously changing complex behavior patterns of mobile users. For the purpose of data management, a complex activity is modeled as a sequence of location movement, service requests, the co-occurrence of location and service pair, or the interleaving of all above. An activity may be composed of subactivities. Different activities may exhibit dependencies that affect user behaviors. We argue that the complex activity concept provides a more precise, rich, and detail description of user behavioral patterns which are invaluable for data management in mobile environments. Proper exploration of user activities has the potential of providing much higher quality and personalized services to individual user at the right place and on the right time. We therefore propose new methods for complex activity mining, incremental maintenance, online detection and proactive data management based on user activities. In particular, we devise prefetching and pushing techniques with cost sensitive control to facilitate predictive data allocation. Preliminary implementation and simulation results demonstrate that the proposed framework and techniques can significantly increase local availability, conserve execution cost, reduce response time and improve cache utilization.

PrePrint: A Metric for DISH Networks: Analysis, Implications, and Applications

In wireless networks, node cooperation is usually exploited as a data relaying mechanism. However, the wireless channel allows for much richer interaction between nodes. In a multi-channel scenario, transmitter-receiver pairs may make incorrect decisions (e.g., in selecting channels) but idle neighbors could help by sharing information to prevent data collisions. This is a Distributed Information SHaring (DISH) approach to 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 probability of obtaining cooperation, $p_{co}$. First, we analytically evaluate $p_{co}$ in the context of multi-channel multi-hop wireless networks. Second, we verify the analysis via simulations, showing that our analysis accurately characterizes the behavior of $p_{co}$ as a function of underlying network parameters. Third, we investigate the correlation between $p_{co}$ and network performance in terms of collision rate, packet delay, and throughput. We find a near-linear relationship, which suggests that $p_{co}$ 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.

PrePrint: Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks

In a mobile ad hoc network, nodes that are geographically close may need to compete for exclusive access to a shared resource. This paper proposes an abstraction of this problem, called local mutual exclusion; it is an extension to mobile networks of the dining philosophers problem, which has been well-studied in static networks. The desirable feature of an algorithm for this problem is having response time and failure locality independent of the total number of nodes, thus providing a scalable and robust solution. The paper presents two algorithms, exhibiting tradeoffs between simplicity, failure locality and response time. The first algorithm has two variations, one of which has response time that depends very weakly on the number of nodes in the entire system and is polynomial in the maximum number of neighboring nodes; the failure locality, although not optimal, is small and grows very slowly with system size. The second algorithm has optimal failure locality and response time that is quadratic in the number of nodes. A pleasing aspect of the latter algorithm is that when nodes do not move, it has linear response time, improving on previous results for static algorithms with optimal failure locality.

PrePrint: Power Control and Channel Allocation in Cognitive Radio Networks with Primary Users' Cooperation

We consider a point-to-multipoint cognitive radio network that shares a set of channels with a primary network. Within the cognitive radio network, a base station controls and supports a set of fixed-location wireless subscribers. The objective is to maximize the throughput of the cognitive network while not affecting the performance of primary users. Both downlink and uplink transmission scenarios in the cognitive network are considered. For both scenarios, we propose two-phase mixed distributed/centralized control algorithms that require minimal cooperation between cognitive and primary devices. In the first phase, a distributed power updating process is employed at the cognitive and primary nodes to maximize the coverage of the cognitive network while always maintaining the constrained signal to interference plus noise ratio of primary transmissions. In the second phase, centralized channel assignment is carried out within the cognitive network to maximize its throughput. Numerical results are obtained for the behaviors and performance of our proposed algorithms.

PrePrint: MAC for Networks with Multipacket Reception Capability and Spatially Distributed Nodes

The physical layer of future wireless networks will be based on novel radio technologies such as UWB and MIMO. One of the important capabilities of such technologies is the ability to capture a few packets simultaneously. This capability has the potential to improve the performance of the MAC layer. However, we show that in networks with spatially distributed nodes, reusing backoff mechanisms originally designed for narrow-band systems (e.g., CSMA/CA) is inefficient. It is well known that when networks with spatially distributed nodes operate with such MAC protocols, the channel may be captured by nodes that are near the destination, leading to unfairness. We show that when the physical layer enables multipacket reception, the negative implications of reusing the legacy protocols include not only such unfairness but also a significant throughput reduction. We present alternative backoff mechanisms and evaluate their performance via Markovian analysis, approximations, and simulation. We show that our alternative backoff mechanisms can improve both overall throughput and fairness.

PrePrint: Enabling Efficient Peer-to-Peer Resource Sharing in Wireless Mesh Networks

Wireless mesh networks are a promising area for the deployment of new wireless communication and networking technologies. In this paper, we address the problem of enabling effective peer-to-peer resource sharing in this type of networks. Starting from the well-known Chord protocol for resource sharing in wired networks, we propose a specialization (called MeshChord) that accounts for peculiar features of wireless mesh networks: namely, the availability of a wireless infrastructure, and the 1-hop broadcast nature of wireless communication. Through extensive packet-level simulations, we show that MeshChord reduces message overhead of as much as 40% with respect to the basic Chord design, while at the same time improving the information retrieval performance. Furthermore, MeshChord information retrieval performance is resilient to the presence of both CBR and TCP background traffic. Overall, the results of our study suggest that MeshChord can be successfully utilized for implementing file/resource sharing applications in wireless mesh networks.

PrePrint: An Edge Constrained Localized Delaunay Graph for Geographic Routing in Mobile Ad Hoc and Sensor Networks

In this paper, we propose an Edge Constrained Localized Delaunay graph, denoted by ECLDel, as the underlying graph for geographic routing in mobile ad hoc and sensor networks. We prove that the ECLDel is a planar t-spanner of the unit-disk graph. Geographic routing on ECLDel is as efficient as on the previous work of PLDel in terms of path length (hop count). However, the construction of ECLDel graph is far more simple and it converges faster. This is because we significantly reduce the number of messages broadcast by each node from five rounds (each round may contain several messages) to only two messages, and we define two new types of edges, the Intersecting Gabriel (IG) edges and the Unaware Intersection (UI) edges, which are constrained in the ECLDel graph. These edges help significantly reduce the size of messages broadcast by each node which reduces the communication cost, and saves the network bandwidth and node power. Our simulation results show that the average number of messages and the average size of messages broadcast by each node is, respectively, 65% and 42% less in the construction of ECLDel than that in the construction of PLDel.

PrePrint: Distributed Relay-Assignment Protocols for Coverage Expansion in Cooperative Wireless Networks

One important application of cooperative communications is to extend coverage area in wireless networks without increasing infrastructure. However a crucial challenge in implementing cooperation protocols is how to select relay-source pairs. In this paper we address this problem based on the knowledge of the users' spatial distribution which determines the channel statistics. We consider two scenarios at the destination node, when the receiver uses MRC and when no-MRC is used. We characterize the optimal relay location to minimize the outage probability. Then we propose and analyze the performance of two schemes: a distributed nearest neighbor relay-assignment, and an infrastructure based relay-assignment protocol. The outage probability of these two schemes are derived. We also derive universal lower bounds on the performance of relay-assignment protocols to serve as a benchmark for our proposed protocols. Numerical results reveal significant gains when applying the proposed simple distributed algorithms over direct transmission in terms of coverage area, transmit power, and spectral efficiency. At 1% outage probability, more than 200% increase in coverage area can be achieved, 7 dBW savings in the transmitted power, and the system can operate at 2 b/s/Hz higher spectral efficiency.

PrePrint: Exploiting Reactive Collaborative Target Detection in Wireless Sensor Networks

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

PrePrint: Super-Diffusive Behavior of Mobile Nodes and its Impact on Routing Protocol Performance

Mobility is the most important component in mobile ad-hoc networks and delay-tolerant networks. We first investigate numerous GPS mobility traces of human mobile nodes and observe super-diffusive behavior in all GPS traces, which is characterized by a 'faster-than-linear' growth rate of the mean square displacement of a mobile node. We then investigate a large amount of access point based traces, and develop a theoretical framework built upon continuous time random walk formalism, in which one can identify the degree of diffusive behavior of mobile nodes even under possibly heavy-tailed pause time distribution, as in the case of reality. We study existing synthetic models and trace based models in term of the capability of producing various degrees of diffusive behavior, and use a set of Levy walk models due to its simplicity and flexibility. In addition, we show that diffusive properties make a huge impact on contact-based metrics and the performance of routing protocols in various scenarios. Our work in this paper thus suggests that the diffusive behavior of mobile nodes should be correctly captured and taken into account for the design and comparison study of network protocols.

PrePrint: Asymptotic Distortion Performance of Source-Channel Diversity over Multi-hop and Relay Channels

A key challenge in the design of real-time wireless multimedia systems is the presence of fading coupled with strict delay constraints. A very effective answer to this problem is the use of diversity achieving techniques to overcome the fading nature of the wireless channels caused by the mobility of the nodes. This paper focuses on comparing systems that exhibit diversity of three forms: source coding diversity, channel coding diversity, and user-cooperation diversity implemented through multi-hop or relay channels with amplify-and-forward or decode-and-forward protocols. Commonly used in multimedia communications, performance is measured in terms of the distortion exponent. For the case of repetition coding at the relay nodes, we prove that having more relays is not always beneficial. For the general case of having a large number of relays that can help the source using repetition coding, the optimum number of relay nodes that maximizes the distortion exponent is determined in this paper. The derived result shows a tradeoff between the quality (resolution) of the source encoder and the amount of cooperation (number of relay nodes). Also, the performances of the channel coding diversity based scheme and the source coding diversity based scheme are compared.

PrePrint: Handoff Performance in Wireless Mobile Networks with Unreliable Fading Channel

Handoff is an indispensable operation in wireless mobile networks to guarantee continuous, effective and resilient services during a Mobile Station (MS) mobility. Handoff counting, handoff rate and handoff probability are significant metrics to characterize the handoff performance. Handoff counting defines the number of handoff operations during an active call connection. Handoff rate specifies the expected number of handoff operations during an active call. Handoff probability refers to the probability that an MS will perform a handoff procedure to a neighboring cell before call completion. In the literature, the physical fading channel is not considered in developing these metrics. In addition, the tele-traffic parameters are usually simplified into exponentially distributed variables. In this paper, we develop the formulae for these performance metrics over Rayleigh fading. In particular, the results can demonstrate the explicit relationship between the handoff metrics and the Rayleigh channel characteristics, e.g. carrier frequency, maximum Doppler frequency and fade margin. Furthermore, the formulae are developed with the generalized tele-traffic parameters for the aim of general applicability. The numerical results demonstrate that the fading channel has a substantial impact on all these three metrics. The developed techniques and the results are significant for deploying practical wireless networks and also evaluating the system resilience under unreliable physical link.

PrePrint: Optimal Relay Station Placement in Broadband Wireless Access Networks

To satisfy the stringent requirement of capacity enhancement in wireless networks, cooperative relaying is envisioned as one of the most effective solutions. In this paper, we study the capacity enhancement problem by way of Relay Stations (RSs) placement to achieve an efficient and scalable design in broadband wireless access networks. To fully exploit the performance benefits of cooperative relaying, we develop an optimization framework to maximize the capacity as well as meet to the minimal traffic demand by each Subscriber Station (SS). The problem of joint RS placement and bandwidth allocation is formulated into a mixed integer nonlinear program. We reformulate it into an integer linear program which is solvable by CPLEX. To avoid exponential computation time, a heuristic algorithm is proposed to efficiently solve the formulated problem. Numerical analysis is conducted through case studies to demonstrate the performance gain of cooperative relaying and the comparison between the proposed heuristic algorithm against the optimal solutions.

PrePrint: Quantifying Impact of Mobility on Data Availability in Mobile Ad Hoc Networks

In mobile ad hoc networks, there are many applications in which mobile users share information, e.g., collaborative rescue operations at a disaster site and exchange of word-of-mouth information in a shopping mall. For such applications, improving data availability is a significant issue and various studies have been conducted with this aim. However, each of these conventional works assumed a particular mobility model and did not fully investigate the influence of the mobility on the proposed approach. In this paper, we aim to quantify the influences of mobility on data availability from various perspectives. We assume neither specific applications nor specific protocols but we propose and quantify several metrics that affect data availability. We also report results of some experiments that measure the proposed metrics assuming several typical mobility models.

PrePrint: Stochastic Traffic Engineering in Multi-hop Cognitive Wireless Mesh Networks

In this work, the stochastic traffic engineering problem in multi-hop cognitive wireless mesh networks is addressed. The challenges induced by the random behaviors of the primary users are investigated in a stochastic network utility maximization framework. For the convex stochastic traffic engineering problem, we propose a fully distributed algorithmic solution which provably converges to the global optimum with probability one. We next extend our framework to the cognitive wireless mesh networks with non-convex utility functions, where a decentralized algorithmic solution, based on learning automata techniques, is proposed. We show that the decentralized solution converges to the global optimum solution asymptotically.

PrePrint: A Multi-channel Scheduler for High Speed Wireless Backhaul Links with Packet Concatenation

Capacity has been an important issue for many wireless backhaul networks. Both the multi-hop nature and the large per packet channel access overhead can lead to its low channel efficiency. The problem may get even worse when there are many applications transmitting packets with small data payloads, e.g. Voice over Internet Protocol (VoIP). Previously, the use of multiple parallel channels and employing packet concatenation were treated as separate solutions to these problems. However, there is no available work on the integrated design and performance analysis of a complete scheduler architecture combining these two schemes. In this paper, we propose a scheduler that concatenates small packets into large frames and sends them through multiple parallel channels between neighboring nodes. Besides the expected capacity improvements, we also derive delay bounds for this scheduler. Based on the delay bound formula, call admission control (CAC) of a broad range of scheduling algorithms can be obtained. We demonstrate the significant capacity improvement of this novel design with a voice-data traffic mixing example, via both numerical and simulation results.

PrePrint: Multiple RFID Tags Access Algorithm

One of the main problems that affect the data integrity of passive RFID systems is the collision between the tags. A popular anticollision algorithm which dominates the standards in HF and UHF passive RFID systems is Framed Slotted Aloha (FSA) and some variations of FSA. Throughput and average time delay of the RFID system which determines the performance/efficiency of the system are reduced rapidly when the number of tags inside the interrogation zone is increased. Using larger frame sizes is not always the solution. This paper discusses and compares the existing protocols, and proposes a variation of FSA, called Progressing Scanning (PS) algorithm. The PS algorithm divides the tags in the interrogation zone into smaller groups and gives the ability to the reader to communicate each time with one of them. For performance analysis, the PS algorithm was evaluated with the parameters of a typical passive RFID system at 2.5 GHz. The results showed that the PS algorithm can improve the efficiency of the RFID system and provide a reliable solution for cases with a high density of tags in the area (over 800 tags).

PrePrint: Relay Node Deployment Strategies in Heterogeneous Wireless Sensor Networks

In a heterogeneous wireless sensor network (WSN), relay nodes (RNs) are adopted to relay data packets from sensor nodes (SNs) to the base station (BS). The deployment of the RNs can have a significant impact on connectivity and lifetime of a WSN system. This paper studies the effects of random deployment strategies. We first discuss the biased energy consumption rate problem associated with uniform random deployment. This problem leads to insufficient energy utilization and shortened network lifetime. To overcome this problem, we propose two new random deployment strategies, namely, the lifetime-oriented deployment and hybrid deployment. The former solely aims at balancing the energy consumption rates of RNs across the network, thus extending the system lifetime. However, this deployment scheme may not provide sufficient connectivity to SNs when the given number of RNs is relatively small. The latter reconciles the concerns of connectivity and lifetime extension. Both single-hop and multi-hop communication models are considered in this paper. With a combination of theoretical analysis and simulated evaluation, this study explores the trade-off between connectivity and lifetime extension in the problem of RN deployment. It also provides a guideline for efficient deployment of RNs in a large scale heterogeneous WSN.

PrePrint: Cost Analysis of Short Message Retransmissions

Short Message Service (SMS) is the most popular mobile data service today. In Taiwan, a subscriber sends more than 200 short messages per year on average. The huge demand for SMS significantly increases network traffic, and it is essential that mobile operators should provide efficient SMS delivery mechanism. In this paper, we study the short message retransmission policies and derive some facts about these policies. Then we propose an analytic model to investigate the short message retransmission performance. The analytic model is validated against simulation experiments. We also collect SMS statistics from a commercial mobile telecommunications network. Our study indicates that the performance trends for the analytic/simulation models and the measured data are consistent.

PrePrint: Handling Mobility in Wireless Sensor and Actor Networks

In Wireless Sensor and Actor Networks (WSANs), the collaborative operation of sensors enables the distributed sensing of a physical phenomenon, while actors collect and process sensor data and perform appropriate actions. In this paper, coordination and communication problems in WSANs with mobile actors are studied. First, a new location management scheme is proposed to handle the mobility of actors with minimal energy expenditure for the sensors, based on a hybrid strategy that includes location updating and location prediction. Actors broadcast location updates limiting their scope based on Voronoi diagrams, while sensors predict the movement of actors based on Kalman filtering of previously received updates. An optimal energy-aware forwarding rule is then derived for sensor-actor communication, based on geographical routing. Consequently, algorithms are proposed that allow controlling the delay of the data-delivery process based on power control, and deal with network congestion by forcing multiple actors to be recipients for traffic generated in the event area. Finally, a model is proposed to optimally assign tasks to actors and control their motion in a coordinated way to to accomplish the tasks based on the characteristics of the events. Performance evaluation shows the effectiveness of the proposed solution.