IEEE PROJECT ON MOBILE COMPUTING

Cooperative Asynchronous Multi channel MAC:

Design, Analysis, and Implementation

Abstract:Medium access control (MAC) protocols have been studied under

different contexts for decades. In decentralized contexts, transmitter-receiver

pairs make independent decisions, which are often suboptimal due to

insufficient knowledge about the communication environment. In this paper,

we introduce distributed information sharing (DISH), which is a distributed

flavor of control-plane cooperation, as a new approach to wireless protocol

design. The basic idea is to allow nodes to share control information with each

other such that nodes can make more informed decisions in communication.

This notion of control-plane cooperation augments the conventional

understanding of cooperation, which sits at the data plane as a data relaying

mechanism. In a multi channel network, DISH allows neighboring nodes to

notify transmitter-receiver pairs of channel conflicts and deaf terminals to

prevent collisions and retransmissions. Based on this, we design a single-radio

cooperative asynchronous multi channel MAC protocol called CAM-MAC.

For illustration and evaluation purposes; we choose a specific set of

parameters for CAM-MAC. First, our analysis shows that its throughput upper

bound is 91 percent of the system bandwidth and our simulations show that it

actually achieves a throughput of 96 percent of the upper bound. Second, our

analysis shows that CAMMAC can saturate 15 channels at maximum and our

simulations show that it saturates 14.2 channels on average, which indicates

that, although CAMMAC uses a control channel, it does not realistically suffer

from control channel bottleneck. Third, we compare CAM-MAC with its non

cooperative version called UNCOOP, and observe a throughput ratio of 2.81

and 1.70 in single-hop and multi hop networks, respectively. This

demonstrates the value of cooperation. Fourth, we compare CAM-MAC with

three recent multi channel MAC protocols, MMAC, SSCH, and AMCP, and

find that CAM-MAC significantly outperforms all of them. Finally, we

implement CAM-MAC and UNCOOP on commercial off-theshelf hardware

and share lessons learned in the implementation. The experimental results

confirm the viability of CAM-MAC and the idea of DISH.

Modeling Propagation Dynamics of BluetoothWorms

(Extended Version)

Abstract: In the last few years, the growing popularity of mobile devices has

made them attractive to virus and worm writers. One communication channel

often exploited by mobile malware is the Bluetooth interface. In this paper, we

present a detailed analytical model that characterizes the propagation

dynamics of Bluetooth worms. Our model captures not only the behavior of

the Bluetooth protocol but also the impact of mobility patterns on the

Bluetooth worm propagation. Validation experiments against a detailed

discreteevent Bluetooth worm simulator reveal that our model predicts the

propagation dynamics of Bluetooth worms with high accuracy. We further use

our model to efficiently predict the propagation curve of Bluetooth worms in

big cities such as Los Angeles. Our model not only sheds light on the

propagation dynamics of Bluetooth worms but also allows one to predict

spreading curves of Bluetooth worm propagation in large areas without the

high computational cost of discrete-event simulation.

Exploiting In-Zone Broadcasts for Cache Sharing in Mobile

Ad Hoc Networks

Abstract:The problem of cache sharing for supporting data access in mobile

ad hoc networks is studied in this paper. The key to this problem is to discover

a requested data item in an efficient manner. In this paper, we propose two

caching protocols, IXP and DPIP, which distinguish themselves from the

existing ones in that they fully exploit in-zone broadcasts to facilitate cache

sharing operation. In particular, the DPIP protocol offers an implicit index

push property, which is highly useful for enhancing cache hit ratio in the

neighborhood of a data requester node. Moreover, our protocols also exploit

the broadcasts to facilitate the design of a simple but efficient count-based

cache replacement scheme. Performance study shows that the proposed

protocols can significantly improve the performance of data access in a mobile

ad hoc network

Analysis of Cross-Layer Interaction in Multi rate 802.11

WLANS

Abstract:Recent works in empirical 802.11 wireless LAN (WLAN)

performance evaluations have shown that cross-layer interactions in WLANS

can be subtle, sometimes leading to unexpected results. Two such instances

are: 1) significant throughput degradation resulting from automatic rate

fallback (ARF) having difficulty distinguishing collision from channel noise

and 2) scalable TCP-over distributed coordination function (DCF)

performance that is able to mitigate the negative performance effect of ARF

by curbing multiple access contention even when the number of stations is

large. In this paper, we present a framework for analyzing complex cross-layer

Interactions in 802.11 WLANS, with the aim of providing effective tools for

understanding and improving WLAN performance. We focus on crosslayer

interactions between ARF, DCF, and TCP, where ARF adjusts coding at the

physical layer, DCF mediates link layer multiple access control, and TCP

performs end-to-end transport. We advance stationcentric Markov chain

models of ARF, ARF-DCF with and without RTS/CTS, and TCP-over-DCF

that may be viewed as multi protocol extensions of Bianchi’s IEEE 802.11

model. We show that despite significant increase in complexity the analysis

framework leads to tractable and accurate performance predictions. Our results

complement empirical and simulation-based findings, demonstrating the

versatility and efficacy of station-centric Markov chain analysis for capturing

cross-layer WLAN dynamics

Efficient Broadcasting inMobile Ad Hoc Networks

Abstract:This paper presents two efficient broadcasting algorithms based on

1-hop neighbor information. In the first part of the paper, we consider

senderbased broadcasting algorithms, specifically the algorithm proposed by

Liu et al. In their paper, Liu et al. proposed a sender-based broadcasting

algorithm that can achieve local optimality by selecting the minimum number

of forwarding nodes in the lowest computational time complexity Oðn log nÞ,

where n is the number of neighbors. We show that this optimality only holds

for a subclass of sender-based algorithms. We propose an efficient senderbased

broadcasting algorithm based on 1-hop neighbor information that

reduces the time complexity of computing forwarding nodes to OðnÞ. In Liu

et al.’s algorithm, n nodes are selected to forward the message in the worst

case, whereas in our proposed algorithm, the number of forwarding nodes in

the worst case is 11. In the second part of the paper, we propose a simple and

highly efficient receiver-based broadcasting algorithm. When nodes are

uniformly distributed, we prove that the probability of two neighbor nodes

broadcasting the same message exponentially decreases when the distance

between them decreases or when the node density increases. Using simulation,

we confirm these results and show that the number of broadcasts in our

proposed receiverbased broadcasting algorithm can be even less than one of

the best known approximations for the minimum number of required

broadcasts

Message Authentication in Computationally Constrained

Environments

Abstract: RFID and Wireless Sensor Networks exemplify computationally

constrained environments, where the compact nature of the components

cannot support complex computations or high communication overhead. On

the other hand, such components should support security applications such as

message integrity, authentication, and time stamping. The latter are efficiently

implemented by Hash Message Authentication Codes (HMAC). As clearly

stated in the literature, current approved implementations of HMAC require

resources that cannot be supported in constrained components. An approach to

implement a compact HMAC by the use of stream ciphering is presented in

this paper.

A Flexible Privacy-Enhanced Location-Based Services

System Framework and Practice

Abstract:Location-based services (LBSS) are becoming increasingly

important to the success and attractiveness of next-generation wireless

systems.However, a natural tension arises between the need for user privacy

and the flexible use of location information. In this paper, we present a

framework to support privacy-enhanced LBSS. We classify the services

according to several basic criteria, and we propose a hierarchical key

distribution method to support these services. The main idea behind the system

is to hierarchically encrypt location information under different keys, and

distribute the appropriate keys only to group members with the necessary

permission. Four methods are proposed to deliver hierarchical location

information while maintaining privacy. We propose a key tree rebalancing

algorithm to maintain the re keying performance of the group key

management. Furthermore, we present a practical LBS system

implementation. Hierarchical location information coding offers flexible

location information access which enables a rich set of LBSS. Our load tests

show such a system is highly practical with good efficiency and scalability

Contention-Aware Performance Analysis of Mobility-Assisted

Routing

Abstract: A large body of work has theoretically analyzed the performance of

mobility-assisted routing schemes for intermittently connected mobile

networks. However, the vast majority of these prior studies have ignored

wireless contention. Recent papers have shown through simulations that

ignoring contention leads to inaccurate and misleading results, even for sparse

networks. In this paper, we analyze the performance of routing schemes under

contention. First, we introduce a mathematical framework to model

contention. This framework can be used to analyze any routing scheme with

any mobility and channel model. Then, we use this framework to compute the

expected delays for different representative mobilityassisted routing schemes

under random direction, random waypoint, and community-based mobility

models. Finally, we use these delay expressions to optimize the design of

routing schemes while demonstrating that designing and optimizing routing

schemes using analytical expressions that ignore contention can lead to

suboptimal or even erroneous behavior

Energy-Efficient Map Interpolation for Sensor Fields Using

Kriging

Abstract: We propose a spatial-autocorrelation-aware, energy-efficient, and

errorbounded framework for interpolating maps from sensor fields.

Specifically, we propose an iterative reporting framework that utilizes spatial

interpolation models to reduce communication costs and enforce error control.

The framework employs simple and low-overhead in-network coordination

among sensors for selecting reporting sensors so that the coordination

overhead does not eclipse the communication savings. Due to the probabilistic

nature of the first-round reporting, the framework is less sensitive to sensor

failures and guarantees an error bound for all functional sensors for each

epoch. We then propose a graceful integration of temporal data suppression

models with our framework. This allows an adaptive utilization of spatial or

temporal autocorrelation based on whichever is stronger in different regions of

the sensor field. We conducted extensive experiments using data from a realworld

sensor network deployment and a large Asian temperature data set to

show that the proposed framework significantly reduces messaging costs and

is more resilient to sensor failures. We also implemented our proposed

algorithms on a sensor network of MICAZ motes. The results show that our

algorithms save significant energy and the out-of-bound errors due to packet

loss are below 5 percent

Random Cast: An Energy-Efficient Communication Scheme

for Mobile Ad Hoc Networks

Abstract:In mobile ad hoc networks (MANETs), every node overhears every

data transmission occurring in its vicinity and thus, consumes energy

unnecessarily. However, since some MANET routing protocols such as

Dynamic Source Routing (DSR) collect route information via overhearing,

they would suffer if they are used in combination with 802.11 PSM. Allowing

no overhearing may critically deteriorate the performance of the underlying

routing protocol, while unconditional overhearing may offset the advantage of

using PSM. This paper proposes a new communication mechanism, called

Random Cast, via which a sender can specify the desired level of overhearing,

making a prudent balance between energy and routing performance. In

addition, it reduces redundant rebroadcasts for a broadcast packet, and thus,

saves more energy. Extensive simulation using ns-2 shows that RandomCast is

highly energy-efficient compared to conventional 802.11 as well as 802.11

PSM-based schemes, in terms of total energy consumption, energy good put,

and energy balance

Routing in Delay-Tolerant Networks Comprising

Heterogeneous Node Populations

Abstract: Communication networks are traditionally assumed to be connected.

However, emerging wireless applications such as vehicular networks, pocketswitched

networks, etc., coupled with volatile links, node mobility, and power

outages, will require the network to operate despite frequent disconnections.

To this end, opportunistic routing techniques have been proposed, where a

node may store-and-carry a message for some time, until a new forwarding

opportunity arises. Although a number of such algorithms exist, most focus on

relatively homogeneous settings of nodes. However, in many envisioned

applications, participating nodes might include handhelds, vehicles, sensors,

etc. These various “classes” have diverse characteristics and mobility patterns,

and will contribute quite differently to the routing process. In this paper, we

address the problem of routing in intermittently connected wireless networks

comprising multiple classes of nodes. We show that proposed solutions, which

perform well in homogeneous scenarios, are not as competent in this setting.

To this end, we propose a class of routing schemes that can identify the nodes

of “highest utility” for routing, improving the delay and delivery ratio by four

to five times. Additionally, we propose an analytical framework based on fluid

models that can be used to analyze the performance of various opportunistic

routing strategies, in heterogeneous settings.

Information Content-Based Sensor Selection and Transmission

Power Adjustment for Collaborative Target Tracking

Abstract: For target tracking applications, wireless sensor nodes provide

accurate information since they can be deployed and operated near the

phenomenon. These sensing devices have the opportunity of collaboration

among themselves to improve the target localization and tracking accuracies.

An energy-efficient collaborative target tracking paradigm is developed for

wireless sensor networks (WSNS). A mutual-information-based sensor

selection (MISS) algorithm is adopted for participation in the fusion process.

MISS allows the sensor nodes with the highest mutual information about the

target state to transmit data so that the energy consumption is reduced while

the desired target position estimation accuracy is met. In addition, a novel

approach to energy savings in WSNS is devised in the information-controlled

transmission power (ICTP) adjustment, where nodes with more information

use higher transmission powers than those that are less informative to share

their target state information with the neighboring nodes. Simulations

demonstrate the performance gains offered by MISS and ICTP in terms of

power consumption and target localization accuracy.

An Access Delay Model for IEEE 802.11e EDCA

Abstract: We analyze the MAC access delay of the IEEE 802.11e enhanced

distributed channel access (EDCA) mechanism under saturation. We develop a

detailed analytical model to evaluate the influence of all EDCA differentiation

parameters, namely AIFS, CW min, CW max, and TXOP limit, as well as the

back off multiplier _. Explicit expressions for the mean, standard deviation,

and generating function of the access delay distribution are derived. By

applying numerical inversion on the generating function, we are able to

efficiently compute values of the distribution. Comparison with simulation

confirms the accuracy of our analytical model over a wide range of operating

conditions. We derive simple asymptotic and approximations for the mean and

standard deviation of the access delay, which reveal the salient model

parameters for performance under different differentiation mechanisms. We

also use the model to numerically study the differentiation performance and

find that _ differentiation, though rejected during the standardization process,

is an effective differentiation mechanism that has some advantages over the

other mechanisms

Performance of VIP over Multiple Co-Located IEEE 802.11

Wireless LANS

Abstract:IEEE 802.11 WLAN has high data rates (e.g., 11 Mbps for 802.11b

and 54 Mbps for 802.11g), while voice streams of VoIP typically have lowdatarate

requirements (e.g., 29.2 Kbps). One may, therefore, expect WLAN to be

able to support a large number of VoIP sessions (e.g., 200 and 900 sessions in

802.11b and 802.11g, respectively). Prior work by one of the authors, however,

indicated that 802.11 are extremely inefficient for VOIP transport. Only 12 and 60

VOIP sessions can be supported in an 802.11b and an 802.11g WLAN,

respectively. This paper shows that the bad news does not stop there. When there

are multiple WLANs in the vicinity of each other—a common situation these

days—the already low VoIP capacity can be further eroded in a significant

manner. For example, in a 5 _ 5, 25-cell multi-WLAN network, the VoIP

capacities for 802.11b and 802.11g are only 1.63 and 10.34 sessions per AP,

respectively. This paper investigates several solutions to improve the VoIP

capacity. Based on a conflict graph model, we propose a clique-analytical call

admission scheme, which increases the VoIP capacity by 52 percent from 1.63 to

2.48 sessions per AP in 802.11b. For 11g, the call admission scheme can also

increase the capacity by 37 percent from 10.34 to 14.14 sessions per AP. If all the

three orthogonal frequency channels available in 11b and 11g are used to reduce

interferences among adjacent WLANS, clique analytical call admission scheme

can boost the capacity to 7.39 VoIP sessions per AP in 11b and 44.91 sessions per

AP in 11g. Last but not least, this paper expounds for the first time the use of

coarse-grained time-division multiple accesses (CoTDMA) in conjunction with

the basic 802.11 CSMA to eliminate the performance-degrading exposed-node

and hidden-node problems in 802.11. A two-layer coloring problem (which is

distinct from the classical graph coloring problem) is formulated to assign coarse

time slots and frequency channels to VoIP sessions, taking into account the

intricacies of the carrier-sensing operation of 802.11. We find that CoTDMA can

further increase the VoIP capacity in the multi-WLAN scenario by an additional

35 percent, so that 10 and 58 sessions per AP can be supported in 802.11b and

802.11g, respectively.

Wardrop Routing in Wireless Networks

Abstract: Routing protocols for multi hop wireless networks have

traditionally used shortest path routing to obtain paths to destinations and do

not consider traffic load or delay as an explicit factor in the choice of routes.

We focus on static mesh networks and formally establish that if the number of

sources is not too large, then it is possible to construct a perfect flowavoiding

routing, which can boost the throughput provided to each user over that of the

shortest path routing by a factor of four when carrier sensing can be disabled

or a factor of 3.2 otherwise. So motivated, we address the issue of designing a

multi path, load adaptive routing protocol that is generally applicable even

when there are more sources. We develop a protocol that adaptively equalizes

the mean delay along all utilized routes from a source to destination and does

not utilize any routes that have greater mean delay. This is the property

satisfied by a system in Wardrop equilibrium. We also address the

architectural challenges confronted in the software implementation of a multi

path, delay-feedback-based, robabilistic routing algorithm. Our routing

protocol is 1) completely distributed, 2) automatically load balances flows, 3)

uses multiple paths whenever beneficial, 4) guarantees loop-free paths at every

time instant even while the algorithm is suntil converging, and 5) amenable to

clean implementation. An ns-2 simulation study indicates that the protocol is

able to automatically route flows to “avoid” each other, consistently

outperforming shortest path protocols in a variety of scenarios. The protocol

has been implemented in user space with a small amount of forwarding

mechanism in a modified Linux 2.4.20 kernel. Finally, we discuss a proofofconcept

measurement study of the implementation on a six node test bed.