A correction is given to a previously published result concerned with the relationship between a suitably defined matrix seminorm for consensus analysis and a coefficient of ergodicity.

An algorithm is presented to determine the number and direction of multiple indistinguishable radio frequency emitters using a single channel circular antenna array. This algorithm combines pseudo-Doppler direction finding with the MUSIC algorithm. The theory is provided along with a simulation. The simulation shows that the algorithm performs very well, with accuracy of better than one degree for typical scenarios, even with low signal to noise ratios.

Graph matching, or the determination of the vertex correspondences between a pair of graphs, is a crucial task in various problems in different science and engineering disciplines. This article aims to propose a distributed optimization approach for graph matching (GM) between two isomorphic graphs over multiagent networks. For this, we first show that for a class of asymmetric graphs, GM of two isomorphic graphs is equivalent to a convex relaxation where the set of permutation matrices is replaced by the set of pseudostochastic matrices. Then, we formulate GM as a distributed convex optimization problem with equality constraints and a set constraint, over a network of multiple agents. For arbitrary labelings of the vertices, each agent only has information about just one vertex and its neighborhood, and can exchange information with its neighbors. A projected primal-dual gradient method is developed to solve the constrained optimization problem, and globally exponential convergence of the agents' states to the optimal permutation is achieved. Finally, we illustrate the effectiveness of the algorithm through simulation examples.

This article discusses cooperative stabilization control of rigid formations via an event-based approach. We first design a centralized event-based formation control system, in which a central event controller determines the next triggering time and broadcasts the event signal to all the agents for control input update. We then build on this approach to propose a distributed event control strategy, in which each agent can use its local event trigger and local information to update the control input at its own event time. For both cases, the triggering condition, event function, and triggering behavior are discussed in detail, and the exponential convergence of the event-based formation system is guaranteed.

In this paper, we develop some new event-triggered algorithms for achieving distributed consensus for a multiagent system that guarantees fully Zeno-free triggerings for all the agents. In the proposed framework, each agent updates its control input only at its own triggering instants by using local measurements (i.e., relative states) with respect to neighboring agents, and such local measurements can be done in a local coordinate frame. For all agents, a positive Lpsignal function is embedded in the event detector functions, which aims to avoid the possible comparison of an event error term to a zero threshold that may happen in a zero-crossing scenario. We further propose a Zeno-free self-triggered algorithm to achieve multiagent consensus, which enables discrete-time measurements and thus avoids continuous measurements between the neighboring agents. We also show that the proposed event-based consensus algorithms guarantee less frequent triggered events in a bounded time interval compared to the conventional algorithm without Lpsignals. Simulations and comparisons are provided to validate the performance and effectiveness of the proposed event-based consensus schemes.

This paper discusses methods for growing tensegrity frameworks akin to what are now known as Henneberg constructions (HCs), which apply to bar-joint frameworks. In particular, this paper presents tensegrity framework versions of the three key HCs of vertex addition, edge splitting, and framework merging (where separate frameworks are combined into a larger framework). This is done for super stable tensegrity frameworks in an ambient 2-D or 3-D space. We start with the operation of adding a new vertex to an original super stable tensegrity framework, named vertex addition. We prove that the new tensegrity framework can be super stable as well if the new vertex is attached to the original framework by an appropriate number of members, which include struts or cables, with suitably assigned stresses. Edge splitting can be secured in R2(R3) by adding a vertex joined to three (four) existing vertices, two of which are connected by a member, and then removing that member. This procedure, with appropriate selection of struts or cables, preserves super-stability. In d-dimensional ambient space, merging two super stable frameworks sharing at least d+1 vertices that are in general positions, we show that the resulting tensegrity framework is still super stable. Based on these results, we further investigate the strategies of merging two super stable tensegrity frameworks in Rd, (d ∈ {2, 3}) that share fewer than d+1 vertices, and show how they may be merged through the insertion of struts or cables as appropriate between the two structures, with a super stable structure resulting from the merge.

This paper proposes and investigates a framework for clique gossip protocols. As complete subnetworks, the existence of cliques is ubiquitous in various social, computer, and engineering networks. By clique gossiping, nodes interact with each other along a sequence of cliques. Clique-gossip protocols are defined as arbitrary linear node interactions where node states are vectors evolving as linear dynamical systems. Such protocols become clique-gossip averaging algorithms when node states are scalars under averaging rules. We generalize the classical notion of line graph to capture the essential node interaction structure induced by both the underlying network and the specific clique sequence. We prove a fundamental eigenvalue invariance principle for periodic clique-gossip protocols, which implies that any permutation of the clique sequence leads to the same spectrum for the overall state transition when the generalized line graph contains no cycle. We also prove that for a network with n nodes, cliques with smaller sizes determined by factors of n can always be constructed leading to finite-time convergent clique-gossip averaging algorithms, provided n is not a prime number. Particularly, such finite-time convergence can be achieved with cliques of equal size m if and only if n is divisible by m and they have exactly the same prime factors. A proven fastest finite-time convergent clique-gossip algorithm is constructed for clique-gossiping using size-m cliques. Additionally, the acceleration effects of clique-gossiping are illustrated via numerical examples.

In this paper, we investigate probabilistic stability of Kalman filtering over fading channels modeled by *-mixing random processes, where channel fading is allowed to generate non-stationary packet dropouts with temporal and/or spatial correlations. Upper/lower almost sure (a.s.) stabilities and absolutely upper/lower a.s. stabilities are defined for characterizing the sample-path behaviors of the Kalman filtering. We prove that both upper and lower a.s. stabilities follow a zero-one law, i.e., these stabilities must happen with a probability either zero or one, and when the filtering system is one-step observable, the absolutely upper and lower a.s. stabilities can also be interpreted using a zero-one law. We establish general stability conditions for (absolute) upper and lower a.s. stabilities. In particular, with one-step observability, we show the equivalence between absolutely a.s. stabilities and a.s. ones, and necessary and sufficient conditions in terms of packet arrival rate are derived; for the so-called non-degenerate systems, we also manage to give a necessary and sufficient condition for upper a.s. stability.

Cooperative geolocation has attracted significant research interests in recent years. A large number of localization algorithms rely on the availability of statistical knowledge of measurement errors, which is often difficult to obtain in practice. Compared with the statistical knowledge of measurement errors, it can often be easier to obtain the measurement error bound. This paper investigates a localization problem assuming unknown measurement error distribution except for a bound on the error. We first formulate this localization problem as an optimization problem to minimize the worst case estimation error, which is shown to be a nonconvex optimization problem. Then, relaxation is applied to transform it into a convex one. Furthermore, we propose a distributed algorithm to solve the problem, which will converge in a few iterations. Simulation results show that the proposed algorithms are more robust to large measurement errors than existing algorithms in the literature. Geometrical analysis providing additional insights is also provided.

We investigate a localization problem using time-difference-of-arrival measurements with unknown and bounded measurement errors. Different from most existing algorithms, we consider the minimization of the worst-case position estimation error to improve the robustness of the algorithm. The localization problem is formulated as a nonconvex optimization problem. We adopt semidefinite relaxation to relax the original problem into a convex optimization problem, which can be solved using existing semidefinite program solvers. Simulation results show that our proposed algorithm has lower worst-case position estimation error than other existing algorithms.

Distributed consensus computation over random graph processes is considered. The random graph process is defined as a sequence of random variables which take values from the set of all possible digraphs over the node set. At each time step, every node updates its state based on a Bernoulli trial, independent in time and among different nodes: either averaging among the neighbor set generated by the random graph, or sticking with its current state. The connectivity-independence and arc-independence are introduced to capture the fundamental influence of the random graphs on the consensus convergence. Necessary and/or sufficient conditions are presented on the success probabilities of the Bernoulli trials for the network to reach a global almost sure consensus, with some sharp threshold established revealing a consensus zero-one law. Convergence rates are established by the lower and upper bounds of the ϵ-computation time. We also generalize the concepts of connectivity/arc independence to their analogues from the *-mixing point of view, so that our results apply to a very wide class of graphical models, including the majority of random graph models in the literature, e.g., Erdos-Rényi, gossiping, and Markovian random graphs. We show that under *-mixing, our convergence analysis continues to hold and the corresponding almost sure consensus conditions are established. Finally, we further investigate almost sure finite-time convergence of random gossiping algorithms, and prove that the Bernoulli trials play a key role in ensuring finite-time convergence. These results add to the understanding of the interplay between random graphs, random computations, and convergence probability for distributed information processing.

Despite intensive research in the area of network connectivity, there is an important category of problems that remain unsolved: how to characterize and measure the quality of connectivity of a wireless network which has a realistic number of nodes, not necessarily large enough to warrant the use of asymptotic analysis, and which has unreliable connections, reflecting the inherent unreliability of wireless communications? The quality of connectivity measures how easily and reliably a packet sent by a node can reach another node. It complements the use of capacity to measure the quality of a network in saturated traffic scenarios and provides an intuitive measure of the quality of (end-to-end) network connections. In this paper, we introduce a probabilistic connectivity matrix as a tool to measure the quality of network connectivity. Some interesting properties of the probabilistic connectivity matrix and their connections to the quality of connectivity are demonstrated. We demonstrate that the largest magnitude eigenvalue of the probabilistic connectivity matrix, which is positive, can serve as a good measure of the quality of network connectivity. We provide a flooding algorithm whereby the nodes repeatedly flood the network with packets, and by measuring just the number of packets a given node receives, the node is able to asymptotically estimate this largest eigenvalue.

Wireless broadcast has been increasingly used to deliver information of common interest to a large number of users. There are two major challenges in wireless broadcast: the unreliable nature of wireless links and the difficulty of acknowledging the correct reception of every broadcast packet by every user when the number of users becomes large. In this paper, by resorting to stochastic geometry analysis, we develop a network coding based broadcast scheme that allows a base station (BS) to broadcast a given number of packets to a large number of users, without user acknowledgment, while being able to provide a performance guarantee on the probability of successful delivery. Further, the BS only has limited statistical information about the environment including the spatial distribution of users (instead of their exact locations and number) and the wireless propagation model. Performance analysis is conducted. On that basis, an upper and a lower bound on the number of packet transmissions required to meet the performance guarantee are obtained. Simulations are conducted to validate the accuracy of the theoretical analysis. The technique and analysis developed in this paper are useful for designing efficient and reliable wireless broadcast strategies.

Wireless communication in a network of mobile devices is a challenging and resource-demanding task, due to the highly dynamic network topology and the wireless channel randomness. This paper investigates information broadcast schemes in 2-D mobile ad hoc networks where nodes are initially randomly distributed and then move following a random direction mobility model. Based on an in-depth analysis of the popular susceptible-infectious-recovered epidemic broadcast scheme, this paper proposes a novel energy and bandwidth-efficient broadcast scheme, named the energy-efficient broadcast scheme, which is able to adapt to fast-changing network topology and channel randomness. Analytical results are provided to characterize the performance of the proposed scheme, including the fraction of nodes that can receive the information and the delay of the information dissemination process. The accuracy of analytical results is verified using simulations driven by both the random direction mobility model and a real-world trace.

This paper investigates the information dissemination process in wireless communication networks formed by vehicles. As vehicles are moving constantly, a vehicular ad-hoc network exhibits a highly-dynamic network topology and a fast-changing radio environment. These distinguishing characteristics result in random and unreliable wireless connections between vehicles. Consequently, vehicles need to work cooperatively to disseminate a piece of information to the destination. This paper analyses cooperative information forwarding schemes where each vehicle determines whether or not to forward a received packet in a decentralized manner, without the costly or even impractical demand for the knowledge of network topology. Considering a generic wireless connection model incorporating wireless channel randomness, analytical results are derived for the probability of successful delivery and the expected number of packet forwardings. Moreover, analysis is conducted on the optimal information forwarding scheme that meets a pre-designated probability of successful delivery objective using the minimum number of packet forwardings.

This paper studies the information propagation process in wireless communication networks formed by vehicles traveling on a highway. Corresponding to different lanes of the highway and different types of vehicles, we consider that vehicles in the network can be categorized into a number of traffic streams, where the vehicles in the same traffic stream have the same speed distribution while the speed distributions of vehicles in different traffic streams are different. We analyze the information propagation process of the aforementioned vehicular network and obtain an analytical formula for the information propagation speed (IPS). Using the formula, one can straightforwardly study the impact of parameters such as radio range, vehicular traffic density, vehicular speed distribution, and the time variation of vehicular speed on the IPS. The accuracy of the analytical results is validated using simulations.

This paper investigates the capacity of a random network in which the nodes have a general spatial distribution. Our model assumes n nodes in a unit square, with a pair of nodes directly connected if and only if their Euclidean distance is smaller than or equal to a threshold, known as the transmission range. Each link has an identical capacity of W bits/s. The transmission range is the same for all nodes and can be any value so long as the resulting network is connected. A capacity upper bound is obtained for the above network, which is valid for both finite n and asymptotically infinite n. We further investigate the capacity upper bound and lower bound for the above network as n → ∞ and show that both bounds can be expressed as a product of four factors, which represents respectively the impact of node distribution, link capacity, number of source destination pairs and the transmission range. The bounds are tight in that the upper bound and lower bound differ by a constant multiplicative factor only. For the special case of networks with nodes distributed uniformly or following a homogeneous Poisson distribution, the bounds are of the same order as known results in the literature.

ABSTRACT Distance estimation is vital for localization and many other applications in wireless sensor networks. In this paper, we develop a method that employs a maximum‐likelihood estimator to estimate distances between a pair of neighboring nodes in a static wireless sensor network using their local connectivity information, namely the numbers of their common and non‐common one‐hop neighbors. We present the distance estimation method under a generic channel model, including the unit disk (communication) model and the more realistic log‐normal (shadowing) model as special cases. Under the log‐normal model, we investigate the impact of the log‐normal model uncertainty; we numerically evaluate the bias and standard deviation associated with our method, which show that for long distances our method outperforms the method based on received signal strength; and we provide a Cramér–Rao lower bound analysis for the problem of estimating distances via connectivity and derive helpful guidelines for implementing our method. Finally, on implementing the proposed method on the basis of measurement data from a realistic environment and applying it in connectivity‐based sensor localization, the advantages of the proposed method are confirmed. Copyright © 2012 John Wiley & Sons, Ltd.

This paper proposes a new merging (stitching) scheme for distributed localization of wireless sensor networks. In splitting-merging localization techniques, the network is first split into small sub-networks and each sub-network self-localizes itself, possibly in its own rather than a global coordinate basis. Then by using a stitching strategy they are merged back to compute the position of the nodes in a global coordinate basis. Unlike the existing techniques in which the stitchable sub-networks must have at least 3 nodes in common for the stitching to succeed, the proposed method can systematically address all possible scenarios (even when the two sub-networks are disjoint) while keeping the computational complexity fairly low. The scheme puts the idea of four-bar linkage mechanism and bilateration together in tackling the problem. Therefore, theoretically the proposed method can localize a broader class of networks which are localizable by any splitting-stitching technique. Simulation comparisons with trilateration and wheel graphs show a considerably higher percentage of the localized nodes in this technique. This technique in conjunction with some existing distributed splitting technique, provides a total distributed localization algorithm.

Broadcast in mobile ad-hoc networks is a challenging and resource demanding task, due to the effects of dynamic network topology and channel randomness. In this paper, we consider 2D wireless ad-hoc networks where nodes are randomly distributed and move following a random direction mobility model. A piece of information is broadcast from an arbitrary node. Based on an in-depth analysis into the popular Susceptible-Infectious-Recovered (SIR) epidemic routing algorithm for mobile ad-hoc networks, an energy and spectrum efficient broadcast scheme is proposed, which is able to adapt to fast-changing network topology and channel randomness. Analytical results are provided to characterize the performance of the proposed scheme, including the fraction of nodes that can receive the information and the delay of information propagation. The accuracy of analytical results is verified using simulations.

Trilateration-based localization techniques have been widely used in sensor networks due to their computational efficiency and distributedness. However in sparse networks or in the boundary area of networks, trilateration-based techniques often fail to localize all localizable nodes. Bilateration-based techniques emerge as a generalization of trilateration techniques to a broader class of networks. Compared with trilaterationbased techniques, the main benefit of bilateration-based schemes is that they can localize a higher percentage of nodes while still maintaining the low computational complexity and distributedness properties. One potential drawback of bilaterationbased schemes is that the number of estimated possible positions (hence the memory required to store these positions) may grow exponentially with the number of nodes in the network. Despite the empirical observations reported in the literature that such exponential growth is a rare event, there is a lack of rigorous analysis quantifying the complexity of bilaterationbased schemes. In this paper, we tackle the challenge by first characterizing a broad subclass of the set of critical sub-networks within which the number of possible estimated positions grows exponentially with the size of these sub-networks. Then using mathematical techniques from percolation theory, we prove that, in random geometric networks, with very high probability the size of these critical sub-networks, which constitute the worst case for bilateration-based localization, is bounded. Therefore the complexity of bilateration-based localization technique does not grow exponentially with the size of the entire network. The significance of this result is to analytically demonstrate that bilateration-based techniques not only localize a higher fraction of nodes than their trilateration counterpart, but also they can be implemented in a very efficient (low computational cost) manner.

This paper studies networks where all nodes are distributed on a unit squareA=Δ[- [1/2], [1/2]]2following a Poisson distribution with known density ρ and a pair of nodes separated by an Euclidean distancexare directly connected with probabilitygrρ(x)=Δg(x/rρ), independent of the event that any other pair of nodes are directly connected. Here,g:[0,∞)→ [0,1] satisfies the conditions of rotational invariance, nonincreasing monotonicity, integral boundedness, andg(x)=o(1/(x2log2x)) ; further,rρ=√{(logρ+b)/(Cρ)} whereC=∫ℜ2g(||x||)dxandbis a constant. Denote the aforementioned network byG(Xρ,grρ,A). We show that as ρ→ ∞, 1) the distribution of the number of isolated nodes inG(Xρ,grρ,A) converges to a Poisson distribution with meane-b; 2) asymptotically almost surely (a.a.s.) there is no component inG(Xρ,grρ,A) of fixed and finite orderk>; 1; c) a.a.s. the number of components with an unbounded order is one. Therefore, as ρ→ ∞, the network a.a.s. contains a unique unbounded component and isolated nodes only; a sufficient and necessary condition forG(Xρ,grρ,A) to be a.a.s. connected is that there is no isolated node in the network, which occurs whenb→ ∞ as ρ→ ∞. These results expand recent results obtained for connectivity of random geometric graphs from the unit disk model and the fewer results from the log-normal model to the more general and more practical random connection model.

In this paper we investigate the critical node density required to ensure that an arbitrary node in a large-scale wireless multi-hop network is connected (via multi-hop path) to infinitely many other nodes with a positive probability. Specifically we consider a wireless multi-hop network where nodes are distributed in ℝ2(d = 2, 3) following a homogeneous Poisson point process. The establishment of a direct connection between any two nodes is independent of connections between other pairs of nodes and its probability satisfies some intuitively reasonable conditions, viz. rotational and translational invariance, nonincreasing monotonicity, and integral boundedness. Under the above random connection model we first obtain analytically the upper and lower bounds for the critical density. Then we compare the new bounds with other existing bounds in the literature under the unit disk model and the log-normal model which are special cases of the random connection model. The comparison shows that our bounds are either close to or tighter than the known ones. To the best of our knowledge, this is the first result for the random connection model in both 2D and 3D networks. The result is of practical use for designing large-scale wireless multihop networks such as wireless sensor networks.

In this paper, we analyze the performance limit of sensor localization from a novel perspective. We consider distance-based single-hop sensor localization with noisy distance measurements by time of arrival (TOA). Differently from the existing studies, the anchors are assumed to be randomly deployed, with the result that the trace of the associated Cramer-Rao Lower Bound (CRLB) matrix becomes a random variable. We adopt this random variable as a scalar metric for the performance limit and then focus on its statistical attributes. By the Central Limit Theorems for U-statistics, we show that as the number of anchors goes to infinity, this scalar metric converges to a random variable which is an affine transformation of a chi-square random variable of degree 2. In addition, we provide the quantitative relationship among the mean, the standard deviation, the number of anchors, parameters of communication channels and the distribution of the anchors. Extensive simulations are carried out to confirm the theoretical results. On the one hand, our study reveals some fundamental features of sensor localization; on the other hand, the conclusions we draw can in turn guide us in the design of wireless sensor networks.

In this paper, our main concern is to study the influence of the number of edges on the convergence rate and the total communication cost in distributed average consensus problems. We begin with the case of regular networks, i.e. networks for which the associated graph (vertices corresponding to sensors and edges being defined by communicating sensor pairs) has the same vertex degree for all vertices. In regular graphs, the number of edges is effectively determined by the common vertex degree. Therefore the problem is converted to one of analyzing the influence of the common vertex degree on the convergence rate and total communication cost. To evaluate the convergence rate we use the ratio of two eigenvalues of the Laplacian matrix of the graph, for which we obtain lower and upper bounds in terms of the common vertex degree. Using the bounds, we can illustrate the intuitively reasonable property that the convergence rate will increase with increase in the common vertex degree. However the increment in the convergence rate drops dramatically as the common vertex degree becomes progressively large. At the same time the total communication cost of the consensus process will become large. Based on these two observations we define a type of `Magic Number' to help analyze the value or otherwise of adding more links to the network. The Monte Carlo simulation results are consistent with the theoretical analysis and demonstrate the existence of the magic number. Further we present the simulation results on irregular graphs in which the degree distribution is subject to a Poisson distribution. From the simulation results we observe that the magic number also exists in the irregular graphs. In general the magic number for irregular graphs is larger than the one for regular graphs.

This paper studies the information propagation process in a 1D mobile ad-hoc network formed by vehicles traveling on a highway. We consider that vehicles can be divided into traffic streams; vehicles in the same traffic stream have the same speed distribution, while the speed distributions of vehicles in different traffic streams are different. Analytical formulas are derived for the fundamental properties of the information propagation process as well as the information propagation speed. Using the formulas, one can straightforwardly study the impact on the information propagation speed of various parameters such as radio range, vehicular traffic density, vehicular speed distribution and the time variation of vehicular speed.

This paper addresses a surveillance problem in which the goal is to achieve a circular motion around a target by a non-holonomic agent. The agent only knows its own position with respect to its initial frame, and the bearing angle of the target in that frame. It is assumed that the position of the target is unknown. An estimator and a controller are proposed to estimate the position of the target and make the agent move on a circular trajectory with a desired radius around it. The performance of the proposed algorithm is verified both through simulations and experiments. Robustness is also established in the face of noise and target motion.

In this paper, we consider 2D wireless multi-hop networks with mobile nodes randomly distributed on a torus, and a small number of base stations (infrastructure nodes) deterministically placed in the same area. Mobile nodes move following a random walk mobility model. A piece of information is broadcast from the base stations at the same time in a multi-hop manner using a Susceptible-Infectious-Recovered (SIR) epidemic routing algorithm. A distinguishing feature of the SIR algorithm, which leverages the mobility of mobile users, is that a relay node carries a piece of information for a predetermined amount of time and forwards it at any available opportunity during that time. We provide analytical results for the percolation probability and for the expected fraction of nodes that receive the information when the information dissemination process stops. Further, we study the time delay of the information dissemination process. The accuracy of the analytical results is verified using simulations.

Connectivity and capacity are two fundamental properties of wireless multihop networks. The scalability of these properties has been a primary concern for which asymptotic analysis is a useful tool. Three related but logically distinct network models are often considered in asymptotic analyses, viz. the dense network model, the extended network model, and the infinite network model, which consider respectively a network deployed in a fixed finite area with a sufficiently large node density, a network deployed in a sufficiently large area with a fixed node density, and a network deployed in with a sufficiently large node density. The infinite network model originated from continuum percolation theory and asymptotic results obtained from the infinite network model have often been applied to the dense and extended networks. In this paper, through two case studies related to network connectivity on the expected number of isolated nodes and on the vanishing of components of finite order respectively, we demonstrate some subtle but important differences between the infinite network model and the dense and extended network models. Therefore, extra scrutiny has to be used in order for the results obtained from the infinite network model to be applicable to the dense and extended network models. Asymptotic results are also obtained on the expected number of isolated nodes, the vanishingly small impact of the boundary effect on the number of isolated nodes, and the vanishing of components of finite order in the dense and extended network models using a generic random connection model.

Consider a wireless multihop network where nodes are randomly distributed in a given area following a homogeneous Poisson process. The hop count statistics, viz. the probabilities related to the number of hops between two nodes, are important for performance analysis of the multihop networks. In this paper, we provide analytical results on the probability that two nodes separated by a known euclidean distance are k hops apart in networks subject to both shadowing and small-scale fading. Some interesting results are derived which have generic significance. For example, it is shown that the locations of nodes three or more hops away provide little information in determining the relationship of a node with other nodes in the network. This observation is useful for the design of distributed routing, localization, and network security algorithms. As an illustration of the application of our results, we derive the effective energy consumption per successfully transmitted packet in end-to-end packet transmissions. We show that there exists an optimum transmission range which minimizes the effective energy consumption. The results provide useful guidelines on the design of a randomly deployed network in a more realistic radio environment.

Many wireless multi-hop networks are deployed with some infrastructure support. Existing results on ad-hoc networks are inadequate to fully understand the properties of those networks. In this paper, we study the properties of 1-D infrastructure-based multi-hop networks. Specifically, we consider networks with two types of nodes, i.e. ordinary nodes and powerful nodes. Ordinary nodes are i.i.d. and Poissonly distributed in a unit interval. Powerful nodes are arbitrarily distributed within the same unit interval. These powerful nodes are inter-connected via some backbone infrastructure. The network is said to be connected if each ordinary node is connected (possibly through a multi-hop path) to at least one of the powerful nodes. We obtain analytical results for the connectivity probability and the average number of clusters in the network. We also prove for the first time that the optimum powerful node distribution that minimizes the average number of clusters, and maximizes the asymptotic connectivity probability, is to deploy these powerful nodes in an equi-distant fashion. These results are important for the design and deployment of 1-D infrastructure-based networks.

In this paper we develop analytical bounds on the critical density for percolation in wireless multi- hop networks, but in contrast to other studies, under a random connection model and with nodes Poissonly distributed in the plane R2. The establishment of a direct connection between any two nodes follows a random connection model satisfying some intuitively reasonable conditions, i.e. rotational and translational invariance, non- increasing monotonicity and integral boundedness. It is well known that under the above network model and connection model there exists a critical density below which almost surely a fixed but arbitrary node is connected (via single or multi-hop path) to finite number of other nodes only, and above which the node is connected to an infinite number of other nodes with a positive probability. In this paper we investigate the bounds on the critical density. The result is compared with the existing results under a specific connection model, i.e. the unit disk communication model, and it is shown that our method generates bounds close to the known ones. The result provides valuable insight into the design of large- scale wireless multi-hop networks.

In this paper, we study information propagation in a 2D mobile ad-hoc network, where mobile nodes are randomly and independently distributed on a torus following a homogeneous Poisson process with a given density. Nodes in the network move following a random direction mobility model. A piece of information is broadcast from a source node to all other nodes in the network, using a Susceptible-Infectious-Recovered (SIR) epidemic routing protocol. A distinguishing feature of the SIR algorithm, which leverages the mobility of mobile users, is that a relay node carries and forwards a piece of information for a specified amount of time. We first propose a metric fundamentally characterizing the information propagation in mobile ad-hoc networks. Then analytical results are derived for the probability that a non-zero fraction of nodes receive the information in the limit of large network size and for the expected fraction of nodes that receive the information. The analytical results are verified using simulations. The research provides useful insights on the design of mobile ad-hoc networks.

We consider wireless multi-hop networks with a finite number of (ordinary) nodes randomly deployed in a given 2D area. A finite number of gateways (infrastructure nodes) are deterministically placed in the same area. We study the connectivity between the ordinary nodes and the gateways. In real applications, it is often desirable to limit the maximum number of hops between the ordinary nodes and the gateways in order to provide reliable services. On the other hand, requiring every ordinary node to be connected to at least one gateway imposes strong requirement on transmission range/power or the number of gateways. Therefore it is beneficial to allow a small fraction of ordinary nodes to be disconnected from the gateways so that the network is only partially connected. Based on the above two considerations, we provide analytical results on the k hop partial connectivity, which is the fraction of ordinary nodes that are connected to at least one gateway in at most k hops. The research provides useful guidelines on the design of wireless multi-hop networks.

Consider a network where all nodes are distributed on a unit square following a Poisson distribution with known density ρ and a pair of nodes separated by an Euclidean distance x are directly connected with probability g(x/rρ), where g : [0,∞) → [0,1] satisfies three conditions: rotational invariance, non-increasing monotonicity and integral boundedness, √(log ρ+b)/Cρ, C = ∫ℜ2g (||x||) dx and b is a constant, independent of the event that another pair of nodes are directly connected. In this paper, we analyze the asymptotic distribution of the number of isolated nodes in the above network using the Chen-Stein technique and the impact of the boundary effect on the number of isolated nodes as ρ → ∞. On that basis we derive a necessary condition for the above network to be asymptotically almost surely connected. These results form an important link in expanding recent results on the connectivity of the random geometric graphs from the commonly used unit disk model to the more generic and more practical random connection model.

For the purposes of this paper, “gossiping” is a distributed process whose purpose is to enable the members of a group of autonomous agents to asymptotically determine, in a decentralized manner, the average of the initial values of their scalar gossip variables. This paper discusses several different deterministic protocols for gossiping which avoid deadlocks and achieve consensus under different assumptions. First considered is$T$-periodic gossiping which is a gossiping protocol which stipulates that each agent must gossip with the same neighbor exactly once every$T$time units. Among the results discussed is the fact that if the underlying graph characterizing neighbor relations is a tree, convergence is exponential at a worst case rate which is the same for all possible$T$-periodic gossip sequences associated with the graph. Many gossiping protocols are request based which means simply that a gossip between two agents will occur whenever one of the two agents accepts a request to gossip placed by the other. Three deterministic request-based protocols are discussed. Each is guaranteed to not deadlock and to always generate sequences of gossip vectors which converge exponentially fast. It is shown that worst case convergence rates can be characterized in terms of the second largest singular values of suitably defined doubly stochastic matrices.

Distance estimation is of great importance for localization and a variety of applications in wireless sensor networks. In this paper, we develop a simple and efficient method for estimating distances between any pairs of neighboring nodes in static wireless sensor networks based on their local connectivity information, namely the numbers of their common one-hop neighbors and non-common one-hop neighbors. The proposed method involves two steps: estimating an intermediate parameter through a Maximum-Likelihood Estimator (MLE) and then mapping this estimate to the associated distance estimate. In the first instance, we present the method by assuming that signal transmission satisfies the ideal unit disk model but then we expand it to the more realistic log-normal shadowing model. Finally, simulation results show that localization algorithms using the distance estimates produced by this method can deliver superior performances in most cases in comparison with the corresponding connectivity-based localization algorithms.

In this paper, we study the information propagation speed in a 1D mobile ad hoc network formed by vehicles Poissonly distributed on a highway and travelling in the same direction but with random Gaussianly-distributed speeds, independent between vehicles. Assume that time is divided into time slots of equal length and that each vehicle changes its speed at the beginning of each time slot, independent of its speed in other time slots. We derive analytical formulas for the IPS in the above network under the unit disk model. Using the formula, we can straightforwardly study the impact on the information propagation speed of various parameters such as vehicle density, speed and radio range. The accuracy of the formula is validated using simulations. The research provides useful guidelines on the design of vehicular ad hoc networks.

Error propagation is a greatly complicated problem arising in multihop sensor localization. In this paper, we focus on how certain key factors in a sensor network affect error propagation for a restricted range-based localization scenario and obtain the significant conclusion that localization errors measured by the Mean Squared Error are propagated at the rate of the cube of the minimal hop count to anchors. A simulation analysis based on actual localization processes and the Cramér-Rao Lower Bound verifies this result.

In previous work we proposed a method to determine the bias in localization algorithms using 2 or 3 sensors, whose location have been already identified, for targets in 2-dimensional space by mixing Taylor series and Jacobian matrices. In this paper we extend the bias-correction method to n-dimensional space with N sensors. To illustrate this approach, we analyze the proposed method in three situations using localization algorithms. Monte Carlo simulation results demonstrate the proposed bias-correction method can correct the bias very well in most situations.

Many real wireless multi-hop networks are deployed with some infrastructure support, where the results on ad-hoc networks cannot be readily extended to understand the properties of those networks. In this paper, we study those networks in 1-D. Specifically, we consider two types of nodes in the networks: ordinary nodes and powerful nodes, where ordinary nodes are i.i.d and Poissonly distributed in a unit interval and powerful nodes are arbitrarily distributed within the same unit interval. These powerful nodes are inter-connected via some backbone infrastructure. The network is said to be connected, i.e. any two nodes can communicate with each other, if each ordinary node is connected to at least one of the powerful nodes. We call this type of connectivity type-II connectivity. Exact and simplified asymptotic formulas for type-II connectivity probability and the average hop count between two arbitrary nodes are obtained. Further we prove that equi- distant powerful nodes deployment delivers the optimum performance which maximizes the type-II connectivity probability. These results are important for the design and deployment of 1-D infrastructure-based networks and provide useful insights into the analysis of higher dimensional networks.

We analytically characterize the energy consumption per successfully transmitted packet in end-to-end packet transmissions in a wireless sensor network where nodes are identically and independently distributed in a square area following a homogeneous Poisson process. It is assumed that a greedy forwarding protocol is used for routing. We obtain analytical results on the average number of hops between any two nodes if the transmission is successful and the average number of hops traversed by packets before being dropped if the transmission is unsuccessful. A transmission is unsuccessful if the packet sent from a source to a destination has to be dropped at an intermediate node because the greedy forwarding routing protocol is unable to find a next-hop node that is closer to the destination. Based on the above analysis, we derive the effective energy consumption per successfully transmitted packet. We show that there exists an optimum transmission range which minimizes the effective energy consumption and such optimum transmission range can be computed based on our analysis.

Graph theory has been used to characterize the solvability of the sensor network localization problem. If sensors correspond to vertices and edges correspond to sensor pairs between which the distance is known, a significant result in the theory of range-based sensor network localization is that if the graph underlying the sensor network is generically globally rigid and there is a suitable set of anchors at known positions, then the network can be localized, i.e., a unique set of sensor positions can be determined that is consistent with the data. In particular, for planar problems, provided the sensor network has three or more noncollinear anchors at known points, all sensors are located at generic points, and the intersensor distances corresponding to the graph edges are precisely known rather than being subject to measurement noise, generic global rigidity of the graph is necessary and sufficient for the network to be localizable (in the absence of any further information). In practice, however, distance measurements will never be exact, and the equations whose solutions deliver sensor positions in the noiseless case in general no longer have a solution. This paper then argues that if the distance measurement errors are not too great and otherwise the associated graph is generically globally rigid and there are three or more noncollinear anchors, the network will be approximately localizable, in the sense that estimates can be found for the sensor positions which are near the correct values; in particular, a bound on the position errors can be found in terms of a bound on the distance errors. The sensor positions in this case can be found by minimizing a cost function which, although nonconvex, does have a global minimum.

Location information for sensors in wireless sensor networks (WSNs) is essential to many tasks. In the presence of noise, locations must be estimated and thus the errors are unavoidable. Moreover, the errors can propagate (i.e. increase) as sensors progressively more distant from anchors are localized. Understanding the rules governing error propagation is quite helpful to deploying WSNs and improving performances of localization systems. In this paper, we investigate error propagation measured by the Cramer-Rao Lower Bound (CRLB) in a type of regular 1-Dimensional WSNs whose Fisher Information Matrices are symmetric band Toeplitz matrices. Approximate analytic formulas for the CRLBs in the regular and almost regular WSNs are derived, and properties of error propagation are also obtained. In addition, we derive a magic number relating to the number of range measurements, which indicates a turning point as to system localization accuracies.

In this paper we introduce a new approach to determine the bias in localization algorithms by mixing Taylor series and Jacobian matrices, which results in an easily calculated analytical expression for the bias. To illustrate this approach, we analyze the proposed method in two situations using localization algorithms based on distance measurements. Monte Carlo simulations verify that the proposed method is consistent with the performance of localization algorithms, which means the bias-correction method can correct the bias in most situations except when there is a collinearity problem. Although the method is analyzed in distance-based localization algorithms, it can be extended to other kinds of localization algorithms.

In this paper, we study the well-known phase transition behavior of connectivity in a wireless multi-hop network, but, in contrast to other studies, in a shadowing environment. We consider that a total of n nodes are randomly, independently and uniformly distributed on a unit square in R2, each node has a uniform transmission power and any two nodes are directly connected if and only if the power received by one node from the other node, as determined by the log-normal shadowing model, is larger than or equal to a given threshold. We extend the results obtained under the unit disk communication model in previous work to the more realistic log-normal shadowing model, and derive an analytical formula for the phase transition width of connectivity for large n. We also demonstrate how our results can be extended to higher dimensional networks and to other channel models.

In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in wireless multi-hop networks in Rd(d = 1, 2). We assume that n nodes are randomly, independently and uniformly distributed in [0, 1]d, and each node has a uniform transmission range of r = r(n) and any two nodes can communicate directly with each other iff their Euclidean distance is at most r. For d = 1, we derive a closed-form analytical formula for calculating the probability of having a giant component of order above pn with any fixed 0.5 < p les 1. The asymptotic behavior of one dimensional network having a giant component is investigated based on the derived result, which is distinctly different from its two dimensional counterpart. For d = 2, we derive an asymptotic analytical upper bound on the minimum transmission range at which the probability of having a giant component of order above qn for any fixed 0 < q < 1 tends to one as n rarr infin. Based on the result, we show that significant energy savings can be achieved if we only require a large percentage of nodes (e.g. 95%) to be connected rather than requiring all nodes to be connected. The results of this paper are of practical significance in the design and analysis of wireless ad hoc networks and sensor networks.

Wireless multihop networks are being increasingly used in military and civilian applications. Advanced applications of wireless multihop networks demand better understanding on their properties. Existing research on wireless multihop networks has largely focused on static networks, where the network topology is time-invariant; and there is comparatively a lack of understanding on the properties of dynamic networks with dynamically changing topology. In this paper, we use and extend a recently proposed graph theoretic model, i.e. evolving graphs, to capture the characteristics of such networks. We extend and develop the concepts of route matrix, connectivity matrix and probabilistic connectivity matrix as convenient tools to characterize and investigate the properties of evolving graphs and the associated dynamic networks. The properties of these matrices are established and their relevance to the properties of dynamic wireless multihop networks are introduced.

Energy saving is an important design consideration in wireless sensor networks. In this paper, we analyze the energy savings that can be achieved in a sensor network where each sensor is capable of reducing its transmission power from a maximum power pm, compared with that in a sensor network where each sensor can only transmit at a constant power level pm. To achieve a fair comparison, we assume sensors in both types of sensor networks are connected to the same set of neighbors, i.e. no connection is lost as a result of a sensor reducing its transmission power. We further assume that sensors are distributed in a given area following a Poisson distribution with known node density and the radio propagation is described by a log-normal model. Ignoring boundary effect, we establish analytically the probability for a sensor to achieve an energy saving of at least h dB. We also obtain the expected percentage of energy savings which can be substantial. The research reported in the paper helps to answer questions such as whether the energy savings achieved by using a sensor with a variable-transmission-power (and the consequent extension of its lifetime) justify the additional cost involved in manufacturing it.

In this paper, we study the giant component, the largest component containing a non-vanishing fraction of nodes, in a wireless multi-hop network where n nodes are randomly and uniformly distributed in [0, 1]d(d = 1, 2) and any two nodes can communicate directly with each other if their Euclidean distance is not larger than the transmission range r. We investigate the probability that the size of the giant component is at least a given threshold p with 0.5 < p les 1. For d = 1, we derive a closed-form analytical formula for this probability. For d = 2, we propose an empirical formula for this probability using simulations. In addition, we compare the transmission range required for having a connected network with the transmission range required for having a certain size giant component for d = 2. The comparison shows that a significant energy saving can be achieved if we only require most nodes (e.g. 95%) to be connected to the giant component rather than require all nodes to be connected. The results of this paper are of practical value in the design and analysis of wireless ad hoc networks and sensor networks.

In this paper, we study the phase transition behavior of k-connectivity (k=1,2,...) in wireless multihop networks where a total of n nodes are randomly and independently distributed following a uniform distribution in the unit cube [0,1]d(d = 1,2,3), and each node has a uniform transmission range r(n). It has been shown that the phase transition of k-connectivity becomes sharper as the total number of nodes n increases. In this paper, we investigate how fast such phase transition happens and derive a generic analytical formula for the phase transition width of k-connectivity for large enough n and for any fixed positive integer k in d-dimensional space by resorting to a Poisson approximation for the node placement. This result also applies to mobile networks where nodes always move randomly and independently. Our simulations show that to achieve a good accuracy, n should be larger than 200 when k = 1 and d = 1; and n should be larger than 600 when k les 3 and d = 2, 3. The results in this paper are important for understanding the phase transition phenomenon; and it also provides valuable insight into the design of wireless multihop networks and the understanding of its characteristics.

Consider a wireless multi-hop network formed by distributing a total of n nodes randomly and uniformly in the unit cube [0, 1]d(d = 1, 2, 3) and connecting any two distinct nodes directly iff (if and only if) their Euclidean distance is not greater than a given threshold r(n). We study the phase transition phenomenon of a k-connected (k isin Nopf) multi-hop network in this paper. We show that the phase transition of k-connectivity becomes sharper as n increases. We derive a generic analytical formula for the phase transition width for large n and for any fixed k isin Nopf in d-dimensional space. The result in this paper is important for understanding phase transition behavior, and it provides valuable insight into the design and implementation of wireless multi-hop networks.

Given a wireless sensor network (WSN) whose sensors are randomly and independently distributed in a bounded area following a homogeneous Poisson process with density rho and each sensor has a uniform transmission radius of r0, we investigate the probability that two random sensors separated by a known distance x are fc-hop neighbors for some positive integer k in this paper. We give a closed-form equation for computing this probability for k = 2; and also give a recursive equation for evaluating this probability for k > 2 by using some approximations. The accuracy of the approximate analytical solution is validated by simulations. Furthermore, we present an empirical method to correct the discrepancies between the analytical results and the simulation results caused by the approximation. The result of this paper can be useful in a number of sensor network problems, e.g., estimating the transmission delay between two sensors and energy consumed in the transmission, and WSN routing problems.

This paper considers localization of a source or a sensor from distance measurements. We argue that linear algorithms proposed for this purpose are susceptible to poor noise performance. Instead given a set of sensors/anchors of known positions and measured distances of the source/sensor to be localized from them, we propose a potentially nonconvex weighted cost function whose global minimum estimates the location of the source/sensor one seeks. The contribution of this paper is to provide nontrivial ellipsoidal and polytopic regions surrounding these sensors/anchors of known positions, such that if the object to be localized is in this region localization occurs by globally convergent gradient descent. This has implication to the deployment of sensors/anchors to achieve a desired level of geographical coverage.

The path loss exponent (PLE) is a parameter indicating the rate at which the received signal strength (RSS) decreases with distance, and its value depends on the specific propagation environment. Path loss exponent estimation plays an important role in distance-based wireless sensor network localization, where distance is estimated from the RSS measurements. Path loss exponent estimation is also useful for other purposes like sensor network dimensioning. Existing techniques on PLE estimation rely on both RSS measurements and distance measurements in the same environment to calibrate the PLE. However distance measurements can be difficult and expensive to obtain in some environments. In this paper we propose a novel technique for online calibration of the path loss exponent in wireless sensor networks without using distance measurements. The major contribution of this paper is to demonstrate that it is possible to estimate the PLE using only power measurements and the geometric constraints associated with planarity in a sensor network. This may have a significant impact on wireless sensor network localization.

Determining node positions is essential for many next-generation network functionalities. Previous localization algorithms lack correctness guarantees or require network density higher than required for unique localizability. In this paper, we describe a class of algorithms for fine-grained localization called Sweeps. Sweeps correctly finitely localizes all nodes in bilateration networks. Sweeps also handles angle measurements and noisy measurements. We demonstrate the practicality of our algorithm through extensive simulations on a large number of networks, upon which it consistently localizes one-thousand-node networks of average degree less than five in less than two minutes on a consumer PC.

In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

Knowing the positions of the nodes in a network is essential to many next generation pervasive and sensor network functionalities. Although many network localization systems have recently been proposed and evaluated, there has been no systematic study of partially localizable networks, i.e., networks in which there exist nodes whose positions cannot be uniquely determined. There is no existing study which correctly identifies precisely which nodes in a network are uniquely localizable and which are not. This absence of a sufficient uniqueness condition permits the computation of erroneous positions that may in turn lead applications to produce flawed results. In this paper, in addition to demonstrating the relevance of networks that may not be fully localizable, we design the first framework for two dimensional network localization with an efficient component to correctly determine which nodes are localizable and which are not. Implementing this system, we conduct comprehensive evaluations of network localizability, providing guidelines for both network design and deployment. Furthermore, we study an integration of traditional geographic routing with geographic routing over virtual coordinates in the partially localizable network setting. We show that this novel cross-layer integration yields good performance, and argue that such optimizations will be likely be necessary to ensure acceptable application performance in partially localizable networks.

We provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

Finite-impulse response (FIR) filters are often preferred to infinite-impulse response (IIR) filters because of their various advantages in respect of stability, phase characteristic, implementation, etc. This article proposes a new method to approximate an IIR filter by an FIR filter, which directly yields an optimal approximation with respect to the H/sup /spl infin// error norm. We show that this design problem can be reduced to a linear matrix inequality. We also make a comparison via a numerical example with an existing method, known as the Nehari shuffle.

It is well known that the thermal noise behavior at the terminals of any LTI RLC circuit can be predicted from knowledge of the driving-point impedance and temperature alone. This paper offers the conjecture that similar results hold if the capacitors and inductors are nonlinear. We refine the conjecture by analyzing the behavior of an RLC bridge circuit with the nonlinear inductor and capacitor carefully matched so the terminal behavior reduces to that of a linear resistor R. We show that the terminal noise current is precisely that predicted by the Nyquist-Johnson model for R if the driving voltage is zero or constant, but not if the driving voltage is time-dependent or the inductor and capacitor are time-varying. This paper makes exact calculations using techniques from stochastic differential equations and using reversibility arguments.

We consider the optimal orthonormal subband coding of zero mean cyclostationary signals, with N-periodic second order statistics. A 2-channel uniform filter bank, with N-periodic analysis and synthesis filters, is used as the subband coder. A dynamic scheme involving N-periodic bit allocation is employed. An average variance condition is used to measure the output distortion. The conditions for maximizing the coding gain parallel those for the case when the signals are wide sense stationary (WSS) and the analysis and synthesis filters and the bit allocation time invariant, in that the blocked subband signals must be decorrelated and the subband power spectral densities must obey an ordering. Some additional conditions on this ordering, over and above those required for the WSS case, are needed.

For pt. I see Proc. 1st IEEE Workshop on Signal Proc. Advances in Wireless Comm., 1997. This paper studies the constant modulus (CM) criterion specifically for the case where the time span of the fractionally-spaced equalizer (FSE) is less than that of the channel. Hence, there necessarily exists an error in the equalized signal. Results for the binary case (Part I) are extended to multi-level signalling. This analysts is connected with the previous work of Fijalkow et al. (see IEEE Trans. on Signal Proc., 1995) on misadjustment of a CM receiver to suggest a finite interval of acceptable FSE length which shows that a longer FSE may not be better than a shorter FSE-in some cases, matching the FSE length to that of the channel may not reduce the MSE to a prescribed threshold, while a shorter FSE may be successful in achieving this threshold.

A number of papers have studied blind channel identification/equalization algorithms relying purely on second-order statistics of the fractionally sampled received signal. A class of cyclic allpass channels is shown to be the only class of IIR channels whose cascade with a core channel results in no change in the second-order-statistics indicators used by several of these algorithms. FIR approximations to the poles of these allpass channels result in robustness concerns for the second-order-statistics algorithms, even when FIR identifiability conditions are well satisfied. This sensitivity suggests that excluding only those channels with common subchannel roots is insufficient when applying these second-order-statistics algorithms.

In this paper, an algorithm presented by Streit (1990) to calculate the integer moments of the output sequence probabilities using the probability measures of the hidden Markov models (HMMs) is reformulated in a matrix algebra framework which allows a better understanding of the algorithm. This algorithm arises in the context of the classification of an unknown stochastic process by a set of HMMs using a test statistic which can be approximated by these integer moments. Using this new formulation, a simple way of calculating the joint moments directly from the parameters of the HMMs in a non-iterative way is presented, and an asymptotic analysis of the algorithm is performed.>

An early use of recursive identification in blind adaptive channel equalization is an algorithm developed by Y. Sato (1975). An important generalization of the Sato algorithm with extensive analysis appears in the work of A. Benveniste et al. (1980). These generalized algorithms have been shown to possess a desirable global convergence property under two idealized conditions. The convergence properties of this class of blind algorithms under practical constraints common to a variety of channel equalization applications that violate these idealized conditions are studied. Results show that, in practice, when the equalizer is finite-dimensional and/or the input is discrete (as in digital communications) the equalizer parameters may converge to parameter settings that fail to achieve the objective of approximating the channel inverse. It is also shown that a center spike initialization is insufficient to guarantee avoiding such ill-convergence. Simulations verify the analytical results.>

The emulation of a nonadaptive, binary, decision-feedback equalizer, operating on a noiseless, finite impulse response channel, by a feedforward multilayer processor is considered. This feedforward perceptron equalizer comprises a triangular array of bandlimiting processing elements. The functional similarity between the two systems is exploited to obtain a tight upper bound on the probability of error as a function of the number of layers, using the theory of finite-state Markov processes.>

Blind equalization up to a constant gain of linear time-invariant channels is studied. Dropping the requirement of gain identification allows equalizer anchoring. This results in the elimination of a degree of freedom that causes ill-convergence of conventional blind equalizers, and affords the possibility of using simple update rules based on the stochastic approximation of output energy. Unlike conventional blind equalizers, truncations of the nonrecursive infinite-dimensional realizations of those equalizers inherit the convergence properties of their infinitely parametrized counterparts. A globally convergent blind recursive equalizer for channels without all-pass sections is obtained based on the exact equalization of the minimum-phase part of the channel and the identification of its nonminimum-phase zeros.>

The emulation of a tuned decision feedback equalizer operating on a noiseless finite impulse response channel by a feedforward multilayer neural network is considered. The similarity between the two structures is exploited to obtain tight bounds on the probability of error for the neural nets as a function of the number of layers, using the theory of finite state Markov processes. A class of channels for which exact representation by a neural net of finite complexity is possible is established.>

The existence of stable undesirable equilibria for the Godard algorithm is demonstrated through a simple autoregressive (AR) channel model. These undesirable equilibria correspond to local but nonglobal minima of the underlying mean cost function, and thus permit the ill-convergence of the Godard algorithms which are stochastic gradient descent in nature. Simulation results confirm predicted misbehavior. For channel input of constant modulus, it is shown that attaining the global minimum of the mean cost necessarily implies correct equalization. A criterion is also presented for allowing a decision at the equalizer as to whether a global or nonglobal minimum has been reached.>

The authors define the DFE (decision feedback equalizer) system of interest and their finite-error-recovery-time problem. They present their basic result, which establishes that whenever the channel satisfies a simple frequency-domain constraint, the error recovery time of an ideal DFE is always finite. They also include four applications of this theorem, including analysis of a real channel. Convergence rates and explicit bounds, given an exponential overbound on the channel impulse response, are presented. Results of greater practical interest, where the authors relax most of the major idealized assumptions, are also given. The authors present the result for M-ary data and relate the error recovery time bound back to the binary case. A formula for the error probability, given a high signal-to-noise-ratio channel, is provided.>

Adaptive decision-directed equalizers can become locked for long periods onto incorrect equilibria. A test involving data available at the equalizer output is proposed for determining whether an equilibrium is correct or not, up to a fixed overall delay. If an independent sequence of random variables taking values +or-1 is the input to a finite impulse response filter, and the output of the filter is passed through a slicer, then the slicer output is uncorrelated if and only if it is a delayed version of the filter input. An analogous result for M-ary rather than binary data is outlined.>

A new procedure for checking the stability of 2-D digital filters is proposed. The key part of the test involves construction of related allpass sections of reduced order, stability of which is shown to be equivalent to the stability of the original function. The results are shown to be equivalent to some known stability testing methods in 2-D, but have the advantage of an additional insight gained from the circuit interpretation. Explicit formulas for checking the stability in terms of the filter coefficients are derived for some special cases, and numerical examples are included to clarify the application of the proposed approach.>

In this correspondence we determine an upper bound on the error recovery time of a decision feedback equalizer (DFE) operating on a high signal to noise ratio channel of exponential impulse response to be used for binary transmission. This bound is related to the channel time constant and we show that exponential impulse response channels form a favourable class of channels with regard to DFE error recovery properties.

The performance of decision feedback equalizers (DFE's) working on a noiseless channel with correct tap weights is studied. We show that the space of channel parameters can accordingly be partitioned into a finite number of sets. The error recovery performance of a DFE is the same for all DFE's within one such set, and is determinable. We also discuss some tight bounds for recovery time statistics, which are particularly important when the number of equalizer taps is not small. We argue that minimum phase or near minimum phase character for the channel does not necessarily guarantee short recovery time.

A decision feedback equalizer (DFE) with correct tap weights operating on a noisy channel is considered. We show how the results concerning a noiseless channel can be extended to yield tight bounds on the stationary error probability performance for the noisy case. The effect of noise on DFE performance is classified according to the noise distribution and the channel parameters.

Statistical inference procedures are considered when less complete prior information is available than usually considered. For the purposes of this paper, the prior information is taken to be the specification of a set of probability measures\cal P. With any one prior probability measure the corresponding Bayes' estimate may be found; the recommended inference procedure when a whole set of prior probabilities\cal Pis available is to find the whole set of estimates corresponding to\cal P--this is called the set of feasible estimates\^{\Theta}. The procedure is shown to have some justification on philosophical grounds. Practical justification is also given in that finding\^{\Theta}is computationally feasible in particular cases--those cases investigated here include median, minimum mean square error (MMSE), and maximum {\em a posteriori} probability (MAP) estimation.

A perturbed error system is developed to describe the parameter and output error behaviors of reduced-order application of adaptive identifier/ filters such as the hyperstable adaptive recursive filter (HARF). Given satisfaction of a sufficient excitation condition, this error system is shown to exhibit a bounded-input, bounded-output (BIBO) property. This implies that despite order insufficiency the output and parameter estimates of HARF (and similar adaptive identifier/filter algorithms) remain bounded.

In a desionmaking situation if prior information is vague, indecision may result. A model for partial prior information is established and from this arises the notion of a set of feasible decisions. The existence of more than one feasible decision represents the existence of indecision. In many practical situations the partial prior information may be given by linear inequalities on the prior probabilities in which case there is a computationally attractive method for determining the set of feasible decisions.

The solution of an integral equation arising in a covariance factorization problem is obtained by a Newton-Raphson iteration that is almost always globally convergent. Interpretations of the iterates are given, and the result is shown to specialize to known algorithms when the covariance is stationary with a rational Fourier transform.

The fixed-lag smoothing of random telegraph type signals is studied. The smoothers are derived by first obtaining fixed-point smoothing equations and then using a time discretization. Simulation results are described that verify the qualitative carry-over of known results for the linear-Gaussian problem: the greater the lag, the greater the improvement; beyond a certain lag, no further improvement is obtained by the increase of lag; and the higher the signal-to-noise ratio (SNR), the greater is the improvement over filtering obtained through the use of smoothing. Smoothing errors of one-half the corresponding filtering error are demonstrated.

Attempts to realize optimal fixed-lag smoothers for continuous-time processes have encountered two major difficulties: the presence of delay lines in the smoother, and the instability of most smoothers. This paper considers suboptimal smoothers which still outperform filters and have performance very close to the optimum. Design procedures are exhibited for smoothers that are both finite-dimensional and asymptotically stable, with the procedures depending on the delay line being approximated by a finite-dimensional dynamical system.

The Karhunen-Loève expansion of a random process is used to derive the impulse response of the optimal realizable linear estimator for the process. The expansion is truncated to yield an approximate state-variable model of the process in terms of the firstNeigenvalues and eigenfunctions. The Kalman-Bucy filter for this model provides an approximate realizable linear estimator which approaches the optimal one asN \rightarrow \infty. A bound on the truncation error is obtained.

This paper considers the solution of a Fredholm equation occurring in detection theory problems. A solution procedure, based on solving differential equations with nonmixed boundary conditions, is described for the case when the kernel of the integral equation is known to be the output covariance of a linear finite-dimensional system excited by white noise. Solutions with discontinuities are considered.

The notion is exploded that to build a Kalman-Bucy filter, one needs to know the whole structure of the signal generating process. It is shown that the filter is constructible knowing precisely those covariances required to construct a Wiener filter, and no more, and that the filter is independent of the particular models of the processes generating these covariances. Performance of the Kalman-Bucy filter does depend on the models, however. Results are also obtained for the smoothing problem.

The determination of the state-space equations of a time-varying finite-dimensional linear system with a prescribed output covariance matrix is considered when the system is excited by Gaussian white-noise inputs. It is shown that a symmetric state covariance matrix provides the key link between the state-space equations of a system and the system output covariance matrix. Furthermore, such a matrix satisfies a linear matrix differential equation if the state-space equations of the system are known, and a matrix Riccati equation if the output covariance matrix of the system is given. Existence results are given for the Riccati equation solution, and discussion of asymptotic solutions of the differential equations is also included.

Two solutions are presented to the problem of finding from one spectral factorization all spectral factorizations of a non-negative para-Hermitian matrix. The first solution results from the theory of equivalent networks while the second is given through a derivation from first principles.