Selecting Forwarding Neighbors in Wireless Ad Hoc Networks

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(nlogn) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(nlog² n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n ³ logn) time.     

BlueMesh: Degree-Constrained Multi-Hop Scatternet Formation for Bluetooth Networks

In this paper we describe BlueMesh, a new protocol for the establishment of scatternets, i.e., multi-hop wireless networks of Bluetooth devices. BlueMesh defines rules for device discovery, piconet formation and piconet interconnection so to generate connected scatternets with the following desirable properties. BlueMesh forms scatternets without requiring the Bluetooth devices to be all in each other transmission range. BlueMesh scatternet topologies are meshes with multiple paths between any pair of nodes. BlueMesh piconets are made up of no more than 7 slaves. Simulation results in networks with over 200 nodes show that BlueMesh is effective in quickly generating a connected scatternet in which each node, on average, does not assume more than 2.4 roles. Moreover, the route length between any two nodes in the network is comparable to that of the shortest paths between the nodes.     

Bluetooth scatternets: criteria, models and classification

Bluetooth ad hoc networks are constrained by a master/slave configuration, in which one device is the master and controls the communication with the slave devices. The master and up to seven active slave devices can form a small Bluetooth network called a piconet. In order to build larger network topologies, called scatternets, the piconets must be interconnected. Scatternets are formed by allowing certain piconet members to participate in several piconets by periodically switching between them. Due to the fact that there is no scatternet formation procedure in the Bluetooth specification, numerous different approaches have been proposed. We discuss criteria for different types of scatternets and establish general models of scatternet topologies. Then we review the state-of-the-art approaches with respect to Bluetooth scatternet formation and compare and contrast them.     

Comparative Performance Evaluation of Scatternet Formation Protocols for Networks of Bluetooth Devices

This paper describes the results of the first ns2-based comparative performance evaluation among four major solutions presented in the literature for forming multi-hop networks of Bluetooth devices (scatternet formation). The four protocols considered in this paper are BlueTrees [1], BlueStars [2], BlueNet [3] and the protocol presented in [4] which proposes geometric techniques for topology reduction combined with cluster-based scatternet formation. We implemented the operations of the four protocols from device discovery to scatternet formation. By means of a thorough performance evaluation we have identified protocol parameters and Bluetooth technology features that affect the duration of the formation process and the properties of the produced scatternet. We have investigated how possible modifications of the BT technology (e.g., backoff duration, possibility for a BT inquirer to identify itself) make device discovery more efficient for scatternet formation in multi-hop networks. We have then discussed implementation concerns for each of the selected protocols. Finally, we have analyzed the protocols overhead as well as the effect of the different protocols operations on key metrics of the generated scatternets, which includes the time needed for forming a scatternet, the number of its piconets, the number of slaves per piconet, the number of roles assumed by each node and the scatternet route lengths.     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

Energy-Efficient Broadcasting in All-Wireless Networks

In all-wireless networks, minimizing energy consumption is crucial as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of radio transmissions can be exploited to optimize energy consumption. This problem appears to be difficult to solve [30]. We provide a formal proof of NP-completeness for the general case and give an NP-completeness result for the geometric case; in the former, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. For the general case, we show that it cannot be approximated better than O(logN), where N is the total number of nodes. We then describe an approximation algorithm that achieves the O(logN) approximation ratio. We also describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.     

A Bluetooth scatternet-route structure for multihop ad hoc networks

Bluetooth scatternets, integrating polling, and frequency hopping spread-sprectrum in their medium access control protocol, provide a contention-free environment for Bluetooth devices to access the medium and communicate over multihop links. Currently, most available scatternet formation protocols tend to interconnect all Bluetooth devices at the initial network startup stage and maintain all Bluetooth links thereafter. Instead of this "big scatternet" approach, we propose a scatternet-route structure to combine the scatternet formation with on-demand routing, thus eliminating unnecessary link and route maintenances. To the best of our knowledge, this is the first effort to address on-demand scatternet formation with every detail. We introduce an extended ID (EID) connectionless broadcast scheme, which, compared with original Bluetooth broadcast mechanism, achieves very much shortened route discovery delay. We also propose to synchronize the piconets along each scatternet route to remove piconet switch overhead and obtain even better channel utilization. Furthermore, we present a route-based scatternet scheduling scheme to enable fair and efficient packet transmissions over scatternet routes. Network performance analysis and simulations show that scatternet routes can provide multihop wireless channels with high network utilization and extremely stable throughput, being especially useful in the transmission of large batches of packets and real time data in wireless environment.     

A traffic-aware scheduling for bluetooth scatternets

Bluetooth is a low cost, low power, short-range radio technology used for wireless personal area networks (PANS). Bluetooth scatternet is a set of piconets interconnected via bridge devices. Good interpiconet schedulings are necessary for bridge devices to switch among piconets they participate in. This paper proposes an interpiconet scheduling algorithm named "Traffic-Aware Scatternet Scheduling" (TASS), for bridges in Bluetooth scatternets. According to masters' traffic information, TASS can adaptively switch the bridge to high traffic load masters, and increase the usage of the bridge. In addition, TASS can reduce the number of failed "unsniffs" and the overhead of "bridge switch wastes" to further increase overall system performance. Simulation results show that TASS outperforms existing interpiconet scheduling in both network throughput and adaptability for various traffic loads.     

Efficient Scheduling Algorithms for Bluetooth Scatternets

When more than seven devices are connected in a Bluetooth scatternet, bridge devices are used to connect two piconets to the scatternet. To deal with possible data transmissions between different piconets, the bridge device must frequently switch to different masters. Suppose, however, that a bridge is serving a piconet and the master in another piconet is calling it at the same time, the calling master has to wait until the bridge completes the previous service. Such transmission delay may accumulate over a long period and the performance of the whole Bluetooth network will degrade significantly. In this work, two new scheduling protocols, namely the static schedule and the hybrid schedule were implemented in an effort to smooth this kind of transmission delay in Bluetooth networks. In this static schedule the rendezvous points between piconets are coordinated by distributing them by using a graph edge coloring technique. In case of a heavy traffic load, the static schedule is expected to perform well. On the other hand, in case of a light traffic load, the static schedule may cause long and unavoidable routing delays even when there is no transmission between piconets; in this case a naive random round-robin (RR) schedule in each piconet is more appropriate. Thus, in the hybrid schedule, each master initially runs a RR scheme in its piconet. When the traffic load is heavier than a predefined threshold value, it runs the static schedule. Finally, simulations were conducted by using an ns-2 simulator and Bluehoc to demonstrate the efficiency and effectiveness of the proposed scheduling protocols.

A Fair and Traffic Dependent Scheduling Algorithm for Bluetooth Scatternets

The Bluetooth specification defines the notion of interconnected piconets, called scatternets, but does not define the actual mechanisms and algorithms necessary to set up and maintain them. The operation of a scatternet requires some Bluetooth units to be inter-piconet units (gateways), which need to time-division multiplex their presence among their piconets. This requires a scatternet-scheduling algorithm that can schedule the presence of these units in an efficient manner. In this paper, we propose a distributed scatternet-scheduling scheme that is implemented using the HOLD mode of Bluetooth and adapts to non-uniform and changing traffic. Another attribute of the scheme is that it results in fair allocation of bandwidth to each Bluetooth unit. This scheme provides an integrated solution for both intra- and inter-piconet scheduling, i.e., for polling of slaves and scheduling of gateways.     

An Anchor Chain Scheme for IP Mobility Management

This work presents a simple mobility scheme for IP-based networks, termed the anchor chain scheme. The scheme combines pointer forwarding and caching methods. Every mobile host (MH) is associated with a chain of anchors that connects it to its home agent. Each anchor defines the location of the MH at a certain degree of accuracy. The accuracy is increased along the chain until the attachment point of the MH is reached. We develop distributed procedures for updating the anchor chain (binding operation) with MH movements and for delivering messages to a MH (delivery operation). In terms of worst case performance, the total cost of the binding operations is O(Move logMove), where Move is the total geographic distance that the MH has traveled since its activation. The total length of the MH's pointer path is linear with the distance between the MH and its home network, and the delivery cost is near optimal. In addition, the anchor chain of a MH is determined dynamically with no need for preliminary definitions of static anchors or regions. Our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature, including the current home approach. We believe that the proposed scheme is scalable, fairly easy to implement and there fore attractive for supporting MHs.     

BlueStar: Enabling Efficient Integration Between Bluetooth WPANs and IEEE 802.11 WLANs

Bluetooth is a radio technology for Wireless Personal Area Networking (WPAN) operating in the 2.4 GHz ISM frequency band. So far, there has been little research on how Bluetooth-enabled devices can effectively and efficiently have uninterrupted access to wide area networks (WAN) such as the Internet. We introduce a novel architecture (BlueStar) whereby selected Bluetooth devices, called Bluetooth Wireless Gateways (BWGs), are also IEEE 802.11 enabled so that these BWGs could serve as egress/ingress points to/from the IEEE 802.11 wireless network. We propose mitigating interference between Bluetooth and IEEE 802.11, by employing a hybrid approach of adaptive frequency hopping (AFH) and Bluetooth carrier sense (BCS) of the channels. AFH labels channels as bad or good, and Bluetooth devices only access those channels in the good state, whereas BCS is used to avoid collision by sensing the channel prior to any transmission. By combining AFH and BCS, we drastically minimize the effect of the worst-case interference scenario wherein both a Bluetooth and an IEEE 802.11 interface are co-located in a single device. BlueStar enables Bluetooth devices, belonging to either a piconet or a scatternet, to access the WAN through the BWG without the need for any fixed Bluetooth access points, while utilizing widely deployed base of IEEE 802.11 networks. Moreover, we define the protocol stack employed by BlueStar as well as indicate how BWGs efficiently manage their capacity allocation through the different systems. We also mathematically derive an upper bound on the number BWGs needed in a Bluetooth scatternet so that uninterrupted access to all Bluetooth devices could be provided.     

Cleaning and Doping of Silicon in a BF3Plasma during Fabrication of Ohmic Contacts

The formation of reliable ohmic contacts to silicon is considered. Silicon surface cleaning, contact window doping, and molybdenum application by cathode sputtering in the BF₃atmosphere are carried out in a single vacuum cycle. A model of semiconductor–plasma and dielectric–plasma contacts under stationary discharge conditions is discussed. It is shown that the rates of processes with the participation of charged particles on p-Si and n-Si surfaces substantially differ. The resistivity of Mo-n ⁺Si and Mo-p ⁺Si contacts is the least when the molybdenum films are applied by sputtering in the Ar + (10–15) vol% BF₃atmosphere.     

An efficient algorithm for scheduling in bluetooth piconets and scatternets

Bluetooth is a short-range radio technology operating in the unlicensed industrial-scientific-medical (ISM) band at 2.45 GHz. A piconet is basically a collection of slaves controlled by a master. A scatternet, on the other hand, is established by linking several piconets together in an ad hoc fashion to yield a global wireless ad hoc network. This paper proposes a scheduling policy that aims to achieve increased system throughput and reduced packet delays while providing reasonably good fairness among all traffic flows in bluetooth piconets and scatternets. We propose a novel algorithm for scheduling slots to slaves for both piconets and scatternets using multi-layered parameterized policies. Our scheduling scheme works with real data and obtains an optimal feedback policy within prescribed parameterized classes of these by using an efficient two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm. We show the convergence of our algorithm to an optimal multi-layered policy. We also propose novel polling schemes for intra- and inter-piconet scheduling that are seen to perform well. We present an extensive set of simulation results and performance comparisons with existing scheduling algorithms. Our results indicate that our proposed scheduling algorithm performs better overall on a wide range of experiments over the existing algorithms for both piconets (Das et al. in INFOCOM, pp. 591–600, 2001; Lapeyrie and Turletti in INFOCOM conference proceedings, San Francisco, US, 2003; Shreedhar and Varghese in SIGCOMM, pp. 231–242, 1995) and scatternets (Har-Shai et al. in OPNETWORK, 2002; Saha and Matsumot in AICT/ICIW, 2006; Tan and Guttag in The 27th annual IEEE conference on local computer networks(LCN). Tampa, 2002). Our studies also confirm that our proposed scheme achieves a high throughput and low packet delays with reasonable fairness among all the connections.     

Deterministic tests for detecting singleV-coupling faults in RAMs

We consider the problem of detecting singleV-coupling faults (as defined by Nair, Thatte, and Abraham) inn×1 random-access memories (RAMs). First we derive a lower bound of 2 ^V–2 nlog₂ n+(2 ^V +3)n on the length of any test that detects all singleV-coupling faults, for 2V47 andn=2 ^e wheree{8,...,34}. In the derivation we make use of a family of binary codes which we call (n, )-exhaustive codes. We then describe a procedure which, given any (n, V–1)-exhaustive code, constructs a test that detects all singleV-coupling faults, fornV>2. Following this approach, optimal (n,1)- and (n, 2)-exhaustive codes are used to construct S2CTEST and S3CTEST, which are efficient tests of length 10n and 4nlog₂ n+18n that detect all single 2- and 3-coupling faults, respectively. S3CTEST is roughly five times shorter, for current RAM capacities, than Papachristou and Sahgal's test of length 24n[log₂ n]+n. Codes generated according to Tang and Chen are used similarly to construct S4CTEST and S5CTEST, which are tests of approximate length 8.6n(log₂ n)^1.585 and 9.6n(log₂ n)^2.322 that detect all single 4- and 5-coupling faults, respectively. S5CTEST has the interesting property of being able to detect all single physical neighborhood pattern-sensitive faults without requiring the mapping from logical cell addresses to physical cell locations. S5CTEST also detects the scrambled pattern-sensitive fault recently proposed by Franklin and Saluja; moreover, the new test is approximately fourteen times shorter (for 1 and 4 Mbit RAMs) than the test they describe.This work was supported by operating grants from the Central Research Fund of the University of Alberta and the Natural Sciences and Engineering Research Council of Canada under grant OGP0105567.     

Ad hoc networking with Bluetooth: key metrics and distributed protocols for scatternet formation

Bluetooth is a promising technology for personal/local area wireless communications. A Bluetooth scatternet is composed of simple overlapping piconets, each with a low number of devices sharing the same radio channel. A scatternet may have different topological configurations, depending on the number of composing piconets, the role of the devices involved and the configuration of the links. This paper discusses the scatternet formation issue by analyzing topological characteristics of the scatternet formed. A matrix-based representation of the network topology is used to define metrics that are applied to evaluate the key cost parameters and the scatternet performance. Numerical examples are presented and discussed, highlighting the impact of metric selection on scatternet performance. Then, a distributed algorithm for scatternet topology optimization is introduced, that supports the formation of a “locally optimal” scatternet based on a selected metric. Numerical results obtained by adopting this distributed approach to “optimize” the network topology are shown to be close to the global optimum.     

A Distributed Algorithm for Dynamic Channel Allocation

Recent demand for mobile telephone service has been growing rapidly while the electro-magnetic spectrum of frequencies allocated for this purpose remains limited. Any solution to the channel assignment problem is subject to this limitation, as well as the interference constraint between adjacent channels in the spectrum. Channel allocation schemes provide a flexible and efficient access to bandwidth in wireless and mobile communication systems. In this paper, we present an efficient distributed algorithm for dynamic channel allocation based upon mutual exclusion model, where the channels are grouped by the number of cells in a cluster and each group of channels cannot be shared concurrently within the cluster. We discuss the algorithm and prove its correctness. We also show that the algorithm requires at most (worst case) O(N _gN _n logN _n) messages, where N _g is the number of groups and N _n is the number of neighbors. This is compared to Choy's algorithm which requires O(N _g ²N _n), where N _g is the number of groups and N _n is the number of neighboring cells in the system. We report our algorithm's performance with several channel systems using different types of call arrival patterns. Our results indicate that significant low denial rate, low message complexity and low acquisition time can be obtained using our algorithm.     

Performance of Bluetooth Bridges in Scatternets with Limited Service Scheduling

The performance of two Bluetooth piconets linked through a bridge device is analyzed using the tools of queueing theory. We analyze both possible cases, i.e., when the bridge device is the master in one of the piconets and a slave in the other (MS bridge), as well as when the bridge device is the slave in both of the piconets (SS bridge). Analytical results are derived for the probability distribution of access delay (i.e., the time that a packet has to wait before being serviced) and end-to-end delay, for both intra- and inter-piconet bursty traffic. The scatternet with an SS bridge was found to provide lower end-to-end delay for local traffic as well as lower access delay, while the scatternet with an MS bridge offers lower end-to-end delay for non-local traffic. The scatternet with an SS bridge was also found to be less sensitive to increased probability of non-local traffic and low values of time interval between bridge exchanges, than its counterpart with an MS bridge. All analytical results have been confirmed through simulations.     

Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks

The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces. More specifically, we provide low constant approximations for L ₁ and L norms on a d-dimensional space, for any fixed d>0, and for the L ₂ norm on two- and three-dimensional spaces. Our framework provides a family of fully-distributed and decentralized algorithms, which adapt (asymptotically) optimally to the mobility of disks, at the expense of a low degradation on the best known approximation factors of the respective centralized algorithms: Our algorithms take O(1) time to update the piercing set maintained, per movement of a disk. We also present a family of fully-distributed algorithms for the MPS problem which either match or improve the best known approximation bounds of centralized algorithms for the respective norms and space dimensions.Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. More specifically, we formally prove that the LCC algorithm adapts in constant time to the mobility of the network nodes, and minimizes (up to low constant factors) the number of 1-hop clusters maintained. While there is a vast literature on simulation results for the LCC and the lowest-id algorithms, these had not been formally analyzed prior to this work.We also present an O(logn)-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.