Graph neural network (GNN) models have been widely used for learning graph-structured data. Due to the permutation-invariant requirement of graph learning tasks, a basic element in graph neural networks is the invariant and equivariant linear layers. Previous work (Maron et al., 2019b) provided a maximal collection of invariant and equivariant linear layers and a simple deep neural network model, called k-IGN, for graph data defined on k-tuples of nodes. It is shown that the expressive power of k-IGN is at least as good as the k-Weisfeiler-Leman (WL) algorithm in graph isomorphism tests. However, the dimension of the invariant layer and equivariant layer is the k-th and 2k-th bell numbers, respectively. Such high complexity makes it computationally infeasible for k-IGNs with k >= 3. In this paper, we show that a much smaller dimension for the linear layers is sufficient to achieve the same expressive power. We provide two sets of orthogonal bases for the linear layers, each with only 3(2^k-1)-k basis elements. Based on these linear layers, we develop neural network models GNN-a and GNN-b and show that for the graph data defined on k-tuples of data, GNN-a and GNN-b achieve the expressive power of the k-WL algorithm and the (k+1)-WL algorithm in graph isomorphism tests, respectively. In molecular prediction tasks on benchmark datasets, we demonstrate that low-order neural network models consisting of the proposed linear layers achieve better performance than other neural network models. In particular, order-2 GNN-b and order-3 GNN-a both have 3-WL expressive power, but use a much smaller basis and hence much less computation time than known neural network models.

Blockchain technology has gained growing popularity in recent years. While the technology works well for most applications, the vulnerability of the blockchain-based system is not well understood. The core part of a blockchain-based system is the consensus algorithm. It can be regarded as a protocol used by all network users to make decisions on the growth of the chain. Malicious users can exploit the vulnerabilities of the consensus algorithm to launch block withholding attacks to earn more profit by increasing their winning possibilities, which are significant threats to the security of blockchain-based applications. In this paper, we describe some scenarios of block withholding attacks and suggest effective mitigation methods accordingly. We propose two hybrid consensus algorithms against the block withholding attacks and evaluate the effectiveness of these algorithms, both analytically and through simulation. Simulation results from the SimBlock simulator verified the effectiveness of the proposed algorithms.

In this paper, we consider the power line outage identification problem as a graph signal classification problem, where the signal at each vertex is given as a time series. We propose graph convolutional networks (GCNs) for the task of classifying signals supported on graphs. An important element of the GCN design is filter design. We consider filtering signals in either the vertex (spatial) domain, or the frequency (spectral) domain. Two basic architectures are proposed. In the spatial GCN architecture, the GCN uses a graph shift operator as the basic building block to incorporate the underlying graph structure into the convolution layer. The spatial filter directly utilizes the graph connectivity information. It defines the filter to be a polynomial in the graph shift operator to obtain the convolved features that aggregate neighborhood information of each node. In the spectral GCN architecture, a frequency filter is used instead. A graph Fourier transform operator first transforms the raw graph signal from the vertex domain to the frequency domain, and then a filter is defined using the graph's spectral parameters. The spectral GCN then uses the output from the graph Fourier transform to compute the convolved features. There are additional challenges to classify the time-evolving graph signal as the signal value at each vertex changes over time. The GCNs are designed to recognize different spatiotemporal patterns from high-dimensional data defined on a graph. The application of the proposed methods to power line outage identification shows that these GCN architectures can successfully classify abnormal signal patterns and identify the outage location.

This paper considers the problem of sparse signal recovery where there is a structure in the signal. Efficient recovery schemes can be designed to leverage the signal structure. Following the model-based compressive sensing framework, we have developed an efficient algorithm for both head and tail approximations for the model-projection problem. The problem is modeled as a constrained graph optimization problem, which is an NP-hard optimization problem. Solving the NP-hard optimization program is then transformed to solving a linear program and finding a randomized algorithm to find an integral solution. The integral solution is optimal-in-expectation. The algorithm is proved to have the same geometric convergence as previous work. The algorithm has been tested on various compressing matrices. The proposed algorithm demonstrated improved recoverability and used fewer number of iterations to recover the signal.

This paper presents a solution to the real-time detection of MAC layer misbehaviors in IEEE 802.11 networks. Among the wide range of misbehaviors, we focus on the sender side selfish behavior that creates a channel- capturing effect by using favorable parameters, and the receiver side selfish behavior that does not respond with CTS and ACK upon receiving RTS and data packets, which clears the channel for itself and causes its sender to waste resources. These misbehaviors are subtle to detect, and yet can undermine the performance of the well-behaved nodes significantly. This paper shows a powerful real-time detection method that can catch these misbehaviors as soon as they have started. The detection method requires collecting delay, throughput, and packet interval data to generate time series and applying a sequential change point detection algorithm on the data streams as soon as new data points come in. All attacks are simulated in ns-3 and the simulation results verified the effectiveness of the detection method.

Due to the open nature of wireless communication medium, wireless networks are susceptible to jamming attacks. Jammers interfere with the legitimate nodes by sending strong jamming signals. Legitimate nodes can successfully transmit only between the gaps of the jamming signals. It is therefore very important to detect a jamming attack as soon as it happens in order to effectively take counter measurements. There are various types of jamming attacks, however, the {\it signature} of all jamming attacks is the performance degradation of legitimate nodes. Based on this observation, we develop a detection method using time series analysis approach. We model the network measurements taken over time as time series, and employ a sequential change point detection algorithm to detect the change of state in the time series, which is an indicator of change in the network state. Timely and accurate detection is the first step before further identification and localization of the source of interference. In this paper, we address the detection part and leave the localization of the jammer to future work. The jamming attacks are simulated in ns-3 simulator, and the detection result is satisfactory in terms of false alarm rate and detection delay.

This paper addresses detecting in-band wormholes in wireless ad hoc networks. The detection scheme requires collecting the end-to-end delay of packets at the receiver and then applying a sequential change point detection algorithm to detect abrupt changes in the delay time series. A new change point detection algorithm, named SW-CLT, is proposed. The algorithm is based on the Central Limit Theorem (CLT) and does not involve using a preset detecting threshold. The algorithm is compared with the non-parametric cumulative sum (NP-CUSUM) because the non-parametric version is believed to be more robust to highly dynamic data than the parametric version. SW-CLT has the ability to adjust its detection threshold with the variance of the data, and therefore is more robust than NP-CUSUM, which uses a preset threshold. Simulation results from ns3 verified the advantage of SW-CLT over NP-CUSUM in all simulated scenarios.

This paper considers the problem of sensor node localization, where a total of n anchor nodes are used to determine the locations of other nodes based on the received signal strengths. Challenges arise when anchor nodes are sparse and locations of them are not at grid positions. A range-based machine learning algorithm is developed to tackle the challenges. Instead of using samples to calibrate the parameters of a chosen signal model, we use machine learning to estimate the signal propagation function and its parameters at the same time. It overcomes the model dependency issue of existing range-based algorithms, and avoids the insufficient support issue of support vector machine methods. Simulation results show that the proposed algorithm has good adaptability to different signal characteristics, network deployment, and device variability. It significantly outperforms existing methods, especially when the anchor nodes are sparsely and irregularly deployed.

Network coding improves transmission efficiency by combining packets at relay nodes and thus reduces the number of packets sent to the network. It is a network layer solution to improve network throughput and transmission efficiency. However, a coded packet must be decodable by the destination, otherwise it is a waste of resource to combine them together and to deliver the coded packet. This paper addresses how to find the coding solution that guarantees decodability at the destination. We first quantify the coding gain as the number of transmissions reduced, and then provide a method for runtime check whether a coding pair can be separated at the destination. The optimal coding solution is selected as the one that provides the maximum coding gain among all the decodable pairs. The algorithms can be applied to both unicast and multicast traffic. Simulation results show the number of transmissions can be reduced significantly, especially for multicast traffic where there are rich opportunities to apply network coding.

We consider the problem of identifying the source of failure in a network after receiving alarms or having observed symptoms. To locate the root cause accurately and timely in a large communication system is challenging because a single fault can often result in a large number of alarms, and multiple faults can occur concurrently. In this paper, we present a new fault localization method using a machine-learning approach. We propose to use logistic regression to study the correlation among network events based on end-to-end measurements. Then based on the regression model, we develop fault hypothesis that best explains the observed symptoms. Unlike previous work, the machine-learning algorithm requires neither the knowledge of dependencies among network events, nor the probabilities of faults, nor the conditional probabilities of fault propagation as input. The “low requirement” feature makes it suitable for large complex networks where accurate dependencies and prior probabilities are difficult to obtain. We then evaluate the performance of the learning algorithm with respect to the accuracy of fault hypothesis and the concentration property. Experimental results and theoretical analysis both show satisfactory performance.

When the grid topology is changed due to incidents and the state estimator is not updated with the topological change, it is considered a topology error. In this paper, we develop a new method for detecting topology errors in power grids. The proposed method considers the measurement data as a nonstationary Gaussian process, explores the dependence structure of the underlying process. It detects errors by testing the hypothesis of whether the mean vector of a nonstationary Gaussian process is zero and does not rely on the convergence of the standard weighted least-squares (WLS) state estimation algorithm. It is very effective in detecting topology errors, in which multiple conforming errors may occur and the traditional state estimation algorithms may fail to converge. Simulation results show that it can accurately identify the abnormal measurements caused by the topology error.

We address the issue of wireless ad hoc network connectivity by using a tail model that is derived from the signal to interference and noise ratio (SINR). The SINR model more accurately describes link connectivity than the traditionally used disk model in the real-world. We first assess the network connectivity by measuring the conductance of the network and find the bottleneck location of the network, and then deploy a relay node to improve the connectivity at the bottleneck. A partition algorithm is proposed to address the first problem, and an optimization problem is proposed to address the relay node deployment problem. The relay node deployment problem is solved by using approximate convex optimization models, and the approximation performance is analyzed. Simulation results show that the partition algorithm based on the SINR model identifies the network bottleneck more accurately than the previous methods based on the binary model. It also verifies that the relay node can significantly relieve the bottleneck and make the network more tightly knit.

Network coding is a network layer technique to improve transmission efficiency. Coding packets is especially beneficial in a wireless environment where the demand for radio spectrum is high. However, to fully realize the benefits of network coding two challenging issues that must be addressed are: (1) Guaranteeing separation of coded packets at the destination, and (2) Mitigating the extra coding/decoding delay. If the destination has all the needed packets to decode a coded packet, then separation failure can be averted. If the scheduling algorithm considers the arrival time of coding pairs, then the extra delay can be mitigated. In this paper, we develop a network coding method to address these two issues, i.e., decodability and delay, for multi-source multi-destination unicast and multicast sessions. We use linear programming to find the most efficient coding design solution with guaranteed decodability. To reduce network relay, we develop a scheduling algorithm to minimize the extra coding/decoding delay and store-and-forward delay. Our coding design method and scheduling algorithm are validated through experiments. Simulation results show improved transmission efficiency and reduced network delay.

We consider the network connectivity problem in a wireless ad hoc network. Network connectivity is measured by the conductance of the network, also called the Cheeger constant of the graph. A partition algorithm based on this measure is developed that divides the network at the bottleneck area. After the network is bisected, a relay node may be deployed between the two parts to increase the conductance of the network. The relay node deployment problem is formulated as an integer linear program to maximize the number of connections between the nodes on the two sides of the cut, and then a convex optimization algorithm is used to find the precise location of the relay node, which is within the convex hull defined by the radio transmission ranges of all the nodes that can connect to the relay node. The relay node significantly relieves the bottleneck, and the graph connectivity measured by other metrics such as the widely used Fiedler value are also increased.

We consider the maximum throughput scheduling problem in a millimeter-wave wireless personal area network in which users can use adaptive modulation and coding schemes to change their data rates. The scheduling problem is to map transmissions to time slots so that the total throughput is maximized. Due to the ultra-wide bandwidth of the mm Wave band, bad scheduling tends to waste significant channel resource. It is worth the effort to consider a more sophisticated scheduling scheme than the simple serial TDMA scheme. The challenge is that the achieved data rate of one flow is limited by the interference from other transmissions in the same slot, which is unknown until the scheduling decision is known. We propose two scheduling algorithms for variable data rate transmissions. The first algorithm is a greedy algorithm, which always chooses the best option at the moment; the second one uses sorting to decide the order that flows are included in a slot. Both algorithms are interference-aware. The algorithms can be applied to transmissions with omnidirectional antennas as well as directional antennas. The simulation results show that the proposed algorithms achieve higher throughput than previous work for adaptive-rate scheduling.

This paper addresses how to leverage the spatial multiplexing function of MIMO links to improve wireless network throughput. Wireless interference modeling of a half-duplex MIMO node is presented, based on which, routing, spatial multiplexing and scheduling are jointly considered in one optimization model. A linear program-based algorithm is proposed for the joint optimization, and numerical simulation results show that the joint optimization of routing with spatial-temporal multiplexing is superior to the separate design approaches, including separating routing from the other two designs, and separating scheduling from the other two designs.

Detection of sophisticated stealthy network scans requires analyzing large amounts of network data collected over long periods of time. The sheer volume of the data prohibits efficient detection from a pure algorithmic approach. However timely detection of such sophisticated scanning attacks is critical since the attacker employing these approaches is usually well-resourced and potentially can bring high impact to the network than a naive attacker can. To detect such sophisticated scans we propose the integration of algorithmic detection and visualization for human detection to simultaneously optimize computational complexity and human analyst time. The proposed approach provides real world detection capabilities without excessive computation overhead. We characterize the features of scanning attacks in a graph theory context, propose efficient graph algorithms to extract these features in real time, employ visualization techniques to show the relevant multidimensional characteristics, and provide test scenarios to show that the proposed work is more efficient and effective than previous approaches.

End-to-end delay is an important QoS metric in multihop wireless networks such as sensor networks and mesh networks. End-to-end delay is defined as the total time it takes for a single packet to reach the destination. It is a result of many factors including the length of the route and the interference level along the path. In this paper we address how to minimize end-to-end delay jointly through optimizing routing and link layer scheduling. We present two cross-layer schemes, a loosely coupled cross-layer scheme and a tightly coupled cross-layer scheme. In the loosely coupled cross-layer scheme, routing is computed first and then the information of routing is used for link layer scheduling; in the tightly coupled scheme, routing and link scheduling are solved in one optimization model. The two cross-layer schemes involve interference modeling in multihop wireless networks with omnidirectional antenna. A sufficient condition on conflict-free transmission is established, which can be transformed to polynomial-sized linear constraints, and a linear program based on the sufficient condition is developed. Through simulation, we show that the proposed routing and scheduling schemes can outperform their counterparts in each layer, and the integrated cross-layer schemes are superior to the combination of the existing routing and scheduling schemes.

In multicast applications, the end-to-end delay from the source to a group member is determined by the multicast tree topology and the waiting time at each relay node. This paper addresses when the multicast tree is given how to schedule wireless nodes for transmission so that network delay is minimized. We first model the conflict relation among wireless transmissions in a conflict graph, and then we compute a transmission schedule based on an Integer Linear Programming (ILP) model. Since solving ILP problem is NP-hard, a heuristic is designed to solve the ILP problem. The resulting schedule is conflict-free, which is guaranteed by the feasibility of the ILP model. Simulation results show significant reduction of delay when compared with a First Come First Serve (FCFS) scheduling policy.

End-to-end delay is an important QoS metric in sensor networks as well as any application that involves transferring of small-sized files. In this paper, we address how to minimize the end-to-end delay in a multihop wireless network. End-to-end delay is defined as the total time it takes for a single packet to reach the destination. It is a result of many factors including the length of the routing path and the interference level along the path. In this paper we present a transmission scheduling scheme that minimizes the end-to-end delay along a given route. The link scheduling scheme is based on integer linear programming and involves interference modeling. Using this schedule, there are no conflicting transmissions at any time. Through simulation, we show that the proposed link scheduling scheme can significantly reduce end-to- end latency regardless of the routing algorithm used.

In multihop wireless networks, end-to-end throughput is often hard to predict and is even harder to optimize due to the effect of interference. To date there is no precise result other than asymptotic bounds for this question: if there is no routing information given, what is the maximum throughput of a network using uncoordinated transmission such as IEEE 802.11 MAC? This paper attempts to address this question for a given network with specific traffic demand. In this paper we use a cross-layer design scheme to optimize network performance. The paper includes a basic linear programming model, from which the routing paths and link data rates are derived, and then an extended model to consider links with different loss rates. Using ns2 simulation, we show that our joint routing and rate control scheme indeed can predict the maximum throughput and improve network throughput.

In this project, we developed an adaptive multihop clustering algorithm MaxLife for sensor networks. MaxLife significantly improves sensor network lifetime by balancing energy dissipation and minimizing energy consumption at the same time. The algorithm is compared to Random and MinEnergy algorithms and shows great performance gain. Random is extended from its original design of single hop clustering in (Wendi Rabiner Heinzelman et al., 2000) to multihop clustering, which elects cluster heads with absolute fairness. However, the idea of rotating the role of cluster heads does not work well in a multihop environment, because relay nodes can also drain out energy quickly. MinEnergy chooses cluster heads to minimize total energy consumption, which leads to large energy disparity and hurts long-term performance. MaxLife on the other hand, uses global optimization techniques and directly maximizes network lifetime. Simulation results verified that MaxLife achieves the best tradeoff between fairness and energy efficiency, and the clustering topology computed from it has significantly longer lifetime than those from the other two algorithms.

Many applications of wireless sensor networks (WSNs) require location information of the randomly deployed nodes. A common solution to the localization problem is to deploy a few special beacon nodes having location awareness, which help the ordinary nodes to localize. In this approach, non-beacon nodes estimate their locations using noisy distance measurements from three or more non-collinear beacons they can receive signals from. In this paper, the ranging-based localization task is formulated as a multidimensional optimization problem, and addressed using bio-inspired algorithms, exploiting their quick convergence to quality solutions. An investigation on distributed iterative localization is presented in this paper. Here, the nodes that get localized in an iteration act as references for remaining nodes to localize. The problem has been addressed using particle swarm optimization (PSO) and bacterial foraging algorithm (BFA). A comparison of the performances of PSO and BFA in terms of the number of nodes localized, localization accuracy and computation time is presented.

In sensor networks, both energy and bandwidth are scarce resources. In the past, many energy efficient routing algorithms have been devised in order to maximize network lifetime, in which wireless link bandwidth has been optimistically assumed to be sufficient. This article shows that ignoring the bandwidth constraint can lead to infeasible routing solutions. As energy constraint affects how data should be routed, link bandwidth also affects not only the routing topology but also the allowed data rate on each link. In this paper, we discuss the sufficient condition on link bandwidth that makes a routing solution feasible, then provide mathematical optimization models to tackle both energy and bandwidth constraints.We first present a basic mathematical model to address using uniform transmission power for routing without data aggregation, then extend it to handle nonuniform transmission power, and then routing with data aggregation. We propose two efficient heuristics to compute the routing topology and link data rate. Simulation results show that these heuristics provide more feasible routing solutions than previous work, and provide significant improvement on throughput and lifetime.

In sensor networks, both energy and bandwidth are scarce resources. In the past, the energy efficient routing problem has been vastly studied in order to maximize network lifetime, but link bandwidth has been optimistically assumed to be abundant. As energy constraint affects how data should be routed, link bandwidth also affects not just the routing topology but also the allowed data rate on each link, which in turn affects lifetime. Previous works that focus on energy efficient operations in sensor networks with the sole objective of maximizing network lifetime only consider the energy constraint and ignore the bandwidth constraint. This article shows how infeasible these solutions could be if bandwidth does become a constraint, then provides a new mathematical model to tackle both energy and bandwidth constraints. Two efficient heuristics are proposed based on this model; Simulation results show these heuristics provide more feasible routing solutions than previous works, and provide significant improvement on throughput.

This work presents a transmission scheduling scheme in sensor networks. Each node is assigned a list of time slots to use for unicast and broadcast communication. The algorithm employs edge coloring on a directed graph for transmission scheduling. It is different from previous works that use vertex coloring of a graph for node scheduling, or those that use edge coloring of undirected graphs for link scheduling. The proposed algorithm uses the least number of time slots compared to its counterparts and it avoids both the hidden terminal problem and the exposed terminal problem in both unicast and broadcast communication.

Recent research in sensor networks highlights the low-power mode operation of sensor networks. In wireless sensor networks, network lifetime can be extended by organizing sensors into mutually exclusive subsets and alternatively activating each subset. Coverage breach occurs when a subset fails to cover all the targets. In bandwidth-constrained sensor networks, coverage breach is more likely to happen because when active sensors periodically send data to the base station, contention for channel access must be considered. Channel bandwidth imposes a limit on the cardinality of each subset. To make efficient use of both energy and bandwidth with minimum coverage breach requires optimal arrangement of sensor nodes. This article addresses three coverage breach problems related to the low-power operation of wireless sensor networks where channel bandwidth is limited. The three coverage breach problems are formulated using integer linear programming models. A greedy approximation algorithm and a heuristic based on the LP-relaxation method are proposed. Effects of changing different network resources on sensor network coverage are studied through simulations. One consistent result is that when the number of sensors increases, network lifetime can be improved without loss of network coverage only if there is no bandwidth constraint; with bandwidth constraints, network lifetime may be improved further at the cost of coverage breach.

A new multiple access control scheme for wireless ad hoc networks and WLANs is proposed. This scheme uses explicit denial of channel requests and a busy tone to improve channel throughput. Performance analysis shows significant improvement when the network is under heavy traffic load.

DNA computation is to use DNA molecules for information storing and processing. Challenges currently faced by DNA computation are (1) lack of theoretical computational models for applications, and (2) high error rate for implementation. This paper attempts to address these problems from genetic coding and mathematical modeling aspects. The proposed genetic coding approach provides a promising alternative to reduce high error rate. The mathematical formulation lays down groundwork for studying theoretical aspects of DNA computation

Abstract This paper addresses the problem of broadcasting and multicasting in large scale multihopad hocwireless networks. We focus on the energy‐efficient broadcast routing in stationary networks and consider the case where wireless nodes can dynamically control their transmission power for each broadcast session. Minimum spanning tree (MST) has the property that the longest edge in the tree is the shortest among all the spanning trees. We introduce a new algorithm called minimum longest edge (MLE) that constructs a broadcast tree based on MST, and for networks where nodes have different energy reserves, we introduce minimum weight incremental arborescence (MWIA) algorithm to compute the broadcast tree. Multicast tree can be obtained by pruning broadcast tree. These algorithms provide a scheme to balance the energy consumption among all nodes. The simulation results show that MLE and MWIA improved the energy balance and network lifetime for a wide range of networks, and the improvement is more significant when the network size grows. Copyright © 2006 John Wiley & Sons, Ltd.

This paper addresses the coverage breach problem in wireless sensor networks with limited bandwidths. In wireless sensor networks, sensor nodes are powered by batteries. To make efficient use of battery energy is critical to sensor network lifetimes. When targets are redundantly covered by multiple sensors, especially in stochastically deployed sensor networks, it is possible to save battery energy by organizing sensors into mutually exclusive subsets and alternatively activating only one subset at any time. Active nodes are responsible for sensing, computing and communicating. While the coverage of each subset is an important metric for sensor organization, the size of each subset also plays an important role in sensor network performance because when active sensors periodically send data to base stations, contention for channel access must be considered. The number of available channels imposes a limit on the cardinality of each subset. Coverage breach happens when a subset of sensors cannot completely cover all the targets. To make efficient use of both energy and bandwidth with a minimum coverage breach is the goal of sensor network design. This paper presents the minimum breach problem using a mathematical model, studies the computational complexity of the problem, and provides two approximate heuristics. Effects of increasing the number of channels and increasing the number of sensors on sensor network coverage are studied through numerical simulations. Overall, the simulation results reveal that when the number of sensors increases, network lifetimes can be improved without loss of network coverage if there is no bandwidth constraint; with bandwidth constraints, network lifetimes may be improved further at the cost of coverage breach.

Cryptographic protocols have been widely used to protect communications over insecure network environments. Existing cryptographic protocols usually contain flaws. To analyze these protocols and find potential flaws in them, the secure properties of them need be studied in depth. This paper attempts to provide a new framework to analyze and prove the secure properties in these protocols. A number of predicates and action functions are used to model the network communication environment. Domain rules are given to describe the transitions of principals' knowledge and belief states. An example of public key authentication protocols has been studied and analysed.

Position-based reactive routing is a scalable solution for routing in mobile ad hoc networks. The route discovery algorithm in position-based routing can be efficiently implemented only if the source knows the current address of the destination. In this paper, a quorum-based location management scheme is proposed. Location servers are selected using the minimum dominating set (MDS) approach, and are further organized into quorums for location update and location query. When a mobile node moves, it updates its location servers in the update quorum; when a node requests the location information of another node, it will send a query message to the location servers in the query quorum. We propose to use the position-based quorum system, which is easy to construct and guarantees that the update quorums always intersect with the query quorums so that at least one location server in the query quorum is aware of the most recent location of the mobile node. Clusters are introduced for large scale ad hoc networks for scalability. Experiment results show that the proposed scheme provides good scalability when network size increases. Copyright © 2005 John Wiley & Sons, Ltd.

In ad hoc wireless networks, to compute the transmission power of each wireless node such that the resulting network is connected and the total energy consumption is minimized is defined as a Minimum Energy Network Connectivity (MENC) problem, which is an NP-complete problem. In this paper, we consider the approximated solutions for the MENC problem in ad hoc wireless networks. We present a theorem that reveals the relation between the energy consumption of an optimal solution and that of a spanning tree and propose an optimization algorithm that can improve the result of any spanning tree-based topology. Two polynomial time approximation heuristics are provided in the paper that can be used to compute the power assignment of wireless nodes in both static and low mobility ad hoc wireless networks. The two heuristics are implemented and the numerical results verify the theoretical analysis.

This paper considers the problem of broadcasting in large ad hoc wireless networks. We focus on the energy-efficient broadcast routing in stationary networks and consider the case where wireless nodes can dynamically control their transmission power for each broadcast session. The minimum spanning tree (MST) has the property that the longest edge in the tree is the shortest among all the spanning trees, We introduce a new algorithm called minimum longest edge (MLE) that constructs a broadcast tree using MST. This algorithm provides a scheme to balance the energy consumption among all nodes. The simulation results show that MLE improves the energy balance and network lifetime for a wide range of networks, and the improvement is more significant when the network size increases.

Wireless sensor networks have recently attracted lots of research effort due to the wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be able to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that the MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but; on average, the incremental power heuristic is always better than MST.