Multicast Capacity of Wireless Ad Hoc Networks

Assume that n wireless nodes are uniformly randomly deployed in a square region with side-length a and all nodes have the uniform transmission range r and uniform interference range R > r. We further assume that each wireless node can transmit (or receive) at W bits/second over a common wireless channel. For each node vi , we randomly and independently pick k-1 points pi,j (1 les j les k-1) from the square, and then multicast data to the nearest node for each pi,j. We derive matching asymptotic upper bounds and lower bounds on multicast capacity of random wireless networks. Under protocol interference model, when a ²/r ²=O(n/log(n)), we show that the total multicast capacity is Theta(radic{n/log n}middot(W/radick)) when k=O(n/log n); the total multicast capacity is Theta(W) when k=Omega(n/log n). We also study the capacity of group-multicast for wireless networks where for each source node, we randomly select k-1 groups of nodes as receivers and the nodes in each group are within a constant hops from the group leader. The same asymptotic upper bounds and lower bounds still hold. We also extend our capacity bounds to d -dimensional networks.     

Low-Energy Fault-Tolerant Bounded-Hop Broadcast in Wireless Networks

This paper studies asymmetric power assignments in wireless ad hoc networks. The temporary, unfixed physical topology of wireless ad hoc networks is determined by the distribution of the wireless nodes as well as the transmission power (range) assignment of each node. We consider the problem of bounded-hop broadcast under k-fault resilience criterion for linear and planar layout of nodes. The topology that results from our power assignment allows a broadcast operation from a wireless node r to any other node in at most h hops and is k -fault resistant. We develop simple approximation algorithms for the two cases and obtain the following approximation ratios: linear case-O(k); planar case-we first prove a factor of O(k ³) , which is later decreased to O(k ²) by a finer analysis. Finally, we show a trivial power assignment with a cost O(h) times the optimum. To the best of our knowledge, these are the first nontrivial results for this problem.     

Unreliable sensor grids: coverage, connectivity and diameter

We consider an unreliable wireless sensor grid network with n nodes placed in a square of unit area. We are interested in the coverage of the region and the connectivity of the network. We first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r²(n)  log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is “active” (not failed). This result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage.

We also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order . Finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). If the node success probability p(n) is small enough, we show that connectivity does not imply coverage.     

基于几何学的无线传感器网络定位算法

提出一种基于几何学的无线传感器网络(WSN)定位算法。把网络区域中的节点分为锚节点和未知节点,假设在定位空间中有n个锚节点,由于受到几何学的限制,实际可行的锚节点序列是有限的,因此利用一种几何方法判断锚节点间的位置关系,从而选取最优的锚节点序列,能够更精确地确定未知节点的位置,并且分析了待定位节点的邻居锚节点数量对定位精度的影响。仿真结果表明,与已有的APS(Ad-Hoc positioning system)定位算法相比,该算法可有效地降低平均定位误差和提高定位覆盖度。     

Product Multicommodity Flow in Wireless Networks

We provide a tight approximate characterization of the n-dimensional product multicommodity flow (PMF) region for a wireless network of n nodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information-theoretic sense and for a combinatorial interference model (e.g., protocol model). These provide an inner approximation to the n ²-dimensional capacity region. Our results hold for general node distributions, traffic models, and channel fading models. We first establish that the random source-destination model assumed in many previous results on capacity scaling laws, is essentially a one-dimensional approximation to the capacity region and a special case of PMF. We then build on the results for a wireline network (graph) that relate PMF to its spectral (or cut) properties. Specifically, for a combinatorial interference model given by a network graph and a conflict graph, we relate the PMF to the spectral properties of the underlying graphs resulting in simple computational upper and lower bounds. These results show that the 1/radicn scaling law obtained by Gupta and Kumar for a geometric random network can be explained in terms of the scaling law of the conductance of a geometric random graph. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs-such a characterization for general wireless networks has not been available before. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.     

A bidirectional vector associative memory architecture with application to neural networks

A bidirectional architecture for associative memory (AM) capable of vector arithmetic operations is proposed. By introducing a pair of masking and tagging mechanisms, the conventional concepts of bit-operations and word-operations in AM have been generalized to row and column operations, respectively. The proposed architecture demonstrates a symmetrical functionality such that associative processing can be performed in both column and row directions. A set of built-in vector arithmetic and logic units (VALU) is designed to perform the basic vector operations, which offers O(max{n, m}) speed-up for vector operations over the conventional AM at an O(n + m) cost for realizing an n × m AM array. As an applicational example, an associative processing implementation for artificial neural networks is presented.     

Comparative node selection‐based localization technique for wireless sensor networks: A bilateration approach

Wireless sensor networks find extensive applications, such as environmental and smart city monitoring, structural health, and target location. To be useful, most sensor data must be localized. We propose a node localization technique based on bilateration comparison (BACL) for dense networks, which considers two reference nodes to determine the unknown position of a third node. The mirror positions resulted from bilateration are resolved by comparing their coordinates with the coordinates of the reference nodes. Additionally, we use network clustering to further refine the location of the nodes. We show that BACL has several advantages over Energy Aware Co‐operative Localization (EACL) and Underwater Recursive Position Estimation (URPE): (1) BACL uses bilateration (needs only two reference nodes) instead of trilateration (that needs three reference nodes), (2) BACL needs reference (anchor) nodes only on the field periphery, and (3) BACL needs substantially less communication and computation. Through simulation, we show that BACL localization accuracy, as root mean square error, improves by 53% that of URPE and by 40% that of EACL. We also explore the BACL localization error when the anchor nodes are placed on one or multiple sides of a rectangular field, as a trade‐off between localization accuracy and network deployment effort. Best accuracy is achieved using anchors on all field sides, but we show that localization refinement using node clustering and anchor nodes only on one side of the field has comparable localization accuracy with anchor nodes on two sides but without clustering.     

Capacity of Multichannel Wireless Networks Under the Protocol Model

This paper studies the capacity of a n node static wireless network with c channels and m radio interfaces per node under the protocol model of interference. In their seminal work, Gupta and Kumar have determined the capacity of a single channel network (c=1, m=1). Their results are also applicable to multichannel networks provided each node has one interface per channel (m=c) . However, in practice, it is often infeasible to equip each node with one interface per channel. Motivated by this observation, we establish the capacity of general multichannel networks (m les c). Equipping each node with fewer interfaces than channels in general reduces network capacity. However, we show that one important exception is a random network with up to O(logn) channels, where there is no capacity degradation even if each node has only one interface. Our initial analysis assumes that the interfaces are capable of switching channels instantaneously, but we later extend our analysis to account for interface switching delays seen in practice. Furthermore, some multichannel protocols proposed so far rarely require interfaces to switch, and therefore, we briefly study the capacity with fixed interfaces as well.     

Concentric Distributed Localization Based on the Tripodal Anchor Structure and Grid Scan for Wireless Sensor Networks

Achieving high accuracy with minimum reference nodes, anchor nodes, and computation and communication costs is a goal for the localization in wireless sensor networks. Targeting at this goal, a localization scheme called concentric distributed localization with the tripodal anchor structure and grid scan (CDL-TAGS) requiring two reference nodes and a few anchor nodes is proposed in this paper. Under the precondition that the system has randomly distributed normal sensor nodes, a tripodal anchor structure is first designed. With this structure, the localization process is started from the centroid node and then stretched outward to the farthest normal nodes. Based on the two best reference nodes, a virtual point is generated to serve as the third reference node. In the CDL-TAGS scheme, a grid scan algorithm is employed to estimate the position of a normal node. Finally, we show that the communication overhead and time and space complexities among sensor nodes for CDL-TAGS can be kept at a low level. In addition, CDL-TAGS can achieve better accuracy with minimum anchor nodes as compared to some closely related localization schemes in the literature through simulation results.     

Hierarchical Cooperation in Ad Hoc Networks: Optimal Clustering and Achievable Throughput

For a wireless network with n nodes distributed in an area A, and with n source-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in (Ozgur, Leveque, and Tse, 2007) is analyzed and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily improve the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending on n . In addition, to apply the hierarchical cooperation scheme to random networks, a clustering algorithm is developed, which divides the whole network into quadrilateral clusters, each with exactly the number of nodes required.     

HiRLoc: high-resolution robust localization for wireless sensor networks

In this paper, we address the problem of robustly estimating the position of randomly deployed nodes of a wireless sensor network (WSN), in the presence of security threats. We propose a range-independent localization algorithm called high-resolution range-independent localization (HiRLoc), that allows sensors to passively determine their location with high resolution, without increasing the number of reference points, or the complexity of the hardware of each reference point. In HiRLoc, sensors determine their location based on the intersection of the areas covered by the beacons transmitted by multiple reference points. By combining the communication range constraints imposed by the physical medium with computationally efficient cryptographic primitives that secure the beacon transmissions, we show that HiRLoc is robust against known attacks on WSN, such as the wormhole attack, the Sybil attack, and compromise of network entities. Finally, our performance evaluation shows that HiRLoc leads to a significant improvement in localization accuracy compared with state-of-the-art range-independent localization schemes, while requiring fewer reference points.     

Scalability and Performance Evaluation of Hierarchical Hybrid Wireless Networks

This paper considers the problem of scaling ad hoc wireless networks now being applied to urban mesh and sensor network scenarios. Previous results have shown that the inherent scaling problems of a multihop ldquoflatrdquo ad hoc wireless network can be improved by a ldquohybrid networkrdquo with an appropriate proportion of radio nodes with wired network connections. In this work, we generalize the system model to a hierarchical hybrid wireless network with three tiers of radio nodes: low-power end-user mobile nodes (MNs) at the lowest tier, higher power radio forwarding nodes (FNs) that support multihop routing at intermediate level, and wired access points (APs) at the highest level. Scalability properties of the proposed three-tier hierarchical hybrid wireless network are analyzed, leading to an identification of the proportion of FNs and APs as well as transmission range required for linear increase in end-user throughput. In particular, it is shown analytically that in a three-tier hierarchical network with nA APs, nF FNs, and nM MNs, the low-tier capacity increases linearly with nF, and the high-tier capacity increases linearly with nA when nA = Omega(radic{nF}) and n _A = O(nF). This analytical result is validated via ns-2 simulations for an example dense network scenario, and the model is used to study scaling behavior and performance as a function of key parameters such as AP and FN node densities for different traffic patterns and bandwidth allocation at each tier of the network.     

Sensor network localization using kernel spectral regression

This paper addresses the localization problem in wireless sensor networks using signal strength. We use a kernel function to measure the similarities between sensor nodes. The kernel matrix can be naturally defined in terms of the signal strength matrix. We show that the relative locations of sensor nodes can be obtained by solving a dimension reduction problem. To capture the structure of the whole network, we use the kernel spectral regression (KSR) method to estimate the relative locations of the sensor nodes. Given sufficient anchor nodes, the relative locations can be aligned to global locations. The key benefits of adopting KSR are that it allows us to define a graph to optimally preserve the topological structure of the sensor network, and a kernel function can capture the nonlinear relationship in the signal space. Simulation results show that we can achieve small average location error with a small number of anchors. We also compare our method with several related methods, and the results show that KSR is more efficient than the others in our simulated sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.     

The Capacity of Wireless Networks: Information-Theoretic and Physical Limits

It is shown that the capacity scaling of wireless networks is subject to a fundamental limitation which is independent of power attenuation and fading models. It is a degrees of freedom limitation which is due to the laws of physics. By distributing uniformly an order of n users wishing to establish pairwise independent communications at fixed wavelength inside a two-dimensional domain of size of the order of n, there are an order of n communication requests originating from the central half of the domain to its outer half. Physics dictates that the number of independent information channels across these two regions is only of the order of radicn, so the per-user information capacity must follow an inverse square-root of n law. This result shows that information-theoretic limits of wireless communication problems can be rigorously obtained without relying on stochastic fading channel models, but studying their physical geometric structure.     

Practical and secure localization and key distribution for wireless sensor networks

In many applications of wireless sensor networks, sensor nodes are manually deployed in hostile environments where an attacker can disrupt the localization service and tamper with legitimate in-network communication. In this article, we introduce Secure Walking GPS, a practical and cost effective secure localization and key distribution solution for real, manual deployments of WSNs. Using the location information provided by the GPS and inertial guidance modules on a special master node, Secure Walking GPS achieves accurate node localization and location-based key distribution at the same time. We evaluate our localization solution in real deployments of MicaZ. Our experiments show that 100% of the deployed nodes localize (i.e., have a location position) and that the average localization errors are within 1–2 m, due mainly to the limitations of the existing commercial GPS devices. Our further analysis and simulation results indicate that the Secure Walking GPS scheme makes a deployed WSN resistant to the Dolev-Yao, the wormhole, and the GPS-denial attacks, the scheme is practical for large-scale deployments with resource-constrained sensor nodes and has good localization and key distribution performance.     

Learning Adaptive Temporal Radio Maps for Signal-Strength-Based Location Estimation

In wireless networks, a client's locations can be estimated using the signals received from various signal transmitters. Static fingerprint-based techniques are commonly used for location estimation, in which a radio map is built by calibrating signal-strength values in the offline phase. These values, compiled into deterministic or probabilistic models, are used for online localization. However, the radio map can be outdated when the signal-strength values change with time due to environmental dynamics, and repeated data calibration is infeasible or expensive. In this paper, we present a novel algorithm, known as LEMT (Location Estimation using Model Trees), to reconstruct a radio map using real-time signal- strength readings received at the reference points. This algorithm can take into account real-time signal-strength values at each time point and make use of the dependency between the estimated locations and reference points. We show that this technique can effectively accommodate the variations of signal strength over different time periods without the need to rebuild the radio maps repeatedly. We demonstrate the effectiveness of our proposed technique on realistic data sets collected from an 802.11b wireless network and a RFID-based network.     

Timing-Based Mobile Sensor Localization in Wireless Sensor and Actor Networks

In this paper, localization problem in wireless sensor and actor networks (WSAN) is addressed. In WSAN, the performance of event detection and tracking highly depends on the exact location information of the events that must be reported along with the event features. Having precise location information of the sensor nodes, actors are able to execute actions more effectively in the region of detected events. In this context, the accurate localization of sensor nodes is essential with respect to the actors. Particularly, the problem becomes much more complicated when the sensor nodes as well as the anchor nodes (actors) are mobile. In order to localize the mobile sensor nodes relative to the actors, a novel Timing-based Mobile Sensor Localization (TMSL) algorithm is introduced. In TMSL, sensor nodes determine their distance from actors by using propagation time and speed of RF signal. In order to determine distance from the actors, actors actively broadcast reference beacons in a pattern of intervals adaptively defined according to the mobility of sensor nodes and the required level of localization accuracy. These reference beacons carry the interval numbers in which they were transmitted. The interval numbers are then used by the sensor nodes to calculate the start time of the beacons locally which is then used to determine the propagation time. TMSL does neither require nor assume any time synchronization among the sensor nodes or with the actors. Performance evaluations clearly show that TMSL is adaptive to velocity of mobile sensor and actor nodes and can be configured according to the required localization accuracy in order to avoid overhead raised due to high velocity.     

普适计算中的定位误差分析

 在二维空间定位服务中,通过对定位过程中产生的误差区域进行分析,提出了参考点优化选择定理,参考点优化选择定理表明在室内定位过程中有针对性选择参考点能使定位误差最小,为室内环境中布置和选择定位参考点提供了相应的理论基础.在此基础上,对传统定位算法进行了改进,提出了定位参考点优化选择算法(RNOS).RNOS算法以参考点与未知节点之间位置关系为基础,通过选择出合适的参考点来计算未知节点的位置,可以提供更准确的定位信息.仿真实验表明本文所提出的参考点优化选择算法能更好地满足对普适终端实时定位的需求,且具有较高的定位精度.     

基于位置信息的无线小区自组织网络拓扑控制研究

针对无线小区自组织网络节点连接性不高的问题,在网络节点所处的平面上引入空间约束机制,通过加入位置信息和增大平面以降低网络节点间干扰的方法来减小网络总干扰。分析了网络源节点的广播成功率,计算了网络节点的空间位置下界,并分别就单数据流和多数据流的情况下网络的有效性加以讨论。实验仿真表明,这种新型的网络拓扑控制方法可以有效提高无线自组织网络的相关性能。     

Localization systems for wireless sensor networks

Monitoring applications define an important class of applications used in wireless sensor networks. In these applications the network perceives the environment and searches for event occurrences (phenomena) by sensing different physical properties, such as temperature, humidity, pressure, ambient light, movement, and presence (for target tracking). In such cases the location information of both phenomena and nodes is usually required for tracking and correlation purposes. In this work we summarize most of the concepts related to localization systems for WSNs as well as how to localize the nodes in these networks (which allows the localization of phenomena). By dividing the localization systems into three distinct components -distance/angle estimation, position computation, and localization algorithm - besides providing a didactic viewpoint, we show that these components can be seen as subareas of the localization problem that need to be analyzed and studied separately.