Organizing sensor nodes into a clustered architecture is an effective method for load balancing and prolonging the network lifetime. However, a serious drawback of the clustering approach is the imposed energy overhead caused by the “global” clustering operations in every round of the global round-based policy (GRBP). To mitigate this problem, this paper proposes a hierarchical clustering-task scheduling policy (HCSP), which triggers node-driven clustering as opposed to GRBP's time-driven clustering. Based on HCSP, each cluster is reconfigured only once at each local super round. Therefore, the cluster reconfiguration frequency varies on-demand and may differ from one cluster to another throughout the network lifetime. However, in order to refresh the entire network structure, global clustering is performed at the end of every global hyper round. Accordingly, HCSP aims to achieve a more flexible, energy-efficient, and scalable clustering-task scheduling than that of GRBP. This policy mitigates the clustering overhead, which is the worst disadvantage of clustering approaches. Energy consumption calculations and extensive simulations show the effectiveness of HCSP in saving energy and in prolonging the network lifetime.

Traffic lights (TLs) are used to control traffic at road intersections. Typically, the TL control mechanism on the road operates according to a fixed periodic schedule to change the light (red/yellow/green). A different schedule may be employed at late night or early morning hours. Such fixed light control does not react to changing traffic conditions, and is unaware of (unresponsive to) congestion. In this paper, we propose a novel framework dynamic TL control (DTLC) at road intersections. DTLC relies on a sensor network to collect traffic data and includes novel protocols to handle congestion and facilitate more efficient traffic flow. The proposed low-overhead algorithms are practical to employ in live traffic flow scenarios. Through analysis and simulations, we demonstrate the benefits of DTLC in optimizing traffic flow metrics, such as traffic throughput, vehicle waiting time, and waiting line length. This paper is a step toward employing smart TLs, which are part of the future envisioned "Smart City."

Traffic control at road intersections is based on traffic lights (TLs). The control mechanism typically used for traffic lights operates based on a periodic schedule to change the light (red/yellow/green). In many cases, a different schedule is used in late night/early morning hours. This fixed control mechanism does not adequately account for changing traffic conditions, and is unaware of/unresponsive to congestion. In this work, we propose a framework for dynamic traffic light control at intersections. The framework relies on a simple sensor network to collect traffic data and includes novel protocols for traffic flow control to handle congestion and facilitate flow. We show that our proposed algorithms have low overhead and are practical to employ in live traffic flow scenarios. Through extensive simulations, we demonstrate the benefits of our framework in optimizing traffic flow metrics, such as traffic throughput, average vehicle waiting time, and vehicle waiting line length.

The cognitive radio (CR) paradigm calls for open spectrum access according to a predetermined etiquette. Under this paradigm, CR nodes access the spectrum opportunistically by continuously monitoring the operating channels. A key challenge in this domain is how the nodes in a CR network (CRN) cooperate to access the medium in order to maximize the CRN throughput. Typical multichannel MAC protocols assume that frequency channels are adjacent and that there are no constraints on the transmission power. However, a CRN may operate over a wide range of frequencies, and a power mask is often enforced on the transmission of a CR user to avoid corrupting the transmissions of spectrum-licensed primary-radio (PR) users. To avoid unnecessary blocking of CR transmissions, we propose a noveldistance-dependentMAC protocol for CRNs. Our protocol, called DDMAC, attempts to maximize the CRN throughput. It uses a novel probabilistic channel assignment mechanism that exploits the dependence between the signal's attenuation model and the transmission distance while considering the traffic profile. DDMAC allows a pair of CR users to communicate on a channel that may not be optimal from one user's perspective, but that allows more concurrent transmissions to take place, especially under moderate and high traffic loads. Simulation results indicate that, compared to typical multichannel CSMA-based protocols, DDMAC reduces the blocking rate of CR requests by up to 30%, which consequently improves the network throughput.

In this work, we investigate a statistical approach for dynamic spectrum access and radio resource management (RRM) in opportunistic cognitive radio (CR) networks. We propose a distributed MAC protocol for such networks that enables unlicensed users to dynamically utilize the available spectrum while limiting the imposed interference on primary (PR) users. Our proposed protocol is novel in three aspects. First, it does not require CR users to coordinate with PR users. Second, it does not assume any predefined CR-to-PR power mask, and thus can exploit the available spectrum more efficiently. Third, it provides the PR users with a statistical guarantee on the fraction of time that their reception may be corrupted by CR users. To avoid corrupting PR user receptions, the protocol computes the maximum power that a CR transmission can use based on current network conditions. We show how to compute this maximum power by deriving models for the PR-to-CR and PR-to-PR interference. Simulation experiments illustrate that our MAC protocol can satisfy the statistical guarantee for PR users under various user deployment models and traffic loads.

Employing multi-input multi-output (MIMO) links can improve energy efficiency in wireless sensor networks (WSNs). Although a sensor node is likely to be equipped with only one antenna, it is possible to group several sensors to form a virtual MIMO link. Such grouping can be formed by means of clustering. In this paper, we propose a distributed MIMO-adaptive energy-efficient clustering/routing scheme, coined cooperative MIMO (CMIMO), which aims at reducing energy consumption in multi- hop WSNs. In CMIMO, each cluster has up to two cluster heads (CHs), which are responsible for routing traffic between clusters (i.e., inter-cluster communications). CMIMO has the ability to adapt the transmission mode and transmission power on a per-packet basis. The transmission mode can be one of four transmit/receive configurations: 1 times 1 (SISO), 2 times 1 (MISO), 1 times 2 (SIMO), and 2 times 2 (MIMO). We study the performance of CMIMO via simulations. Results indicate that our proposed scheme achieves a significant reduction in energy consumption, compared to non-adaptive clustered WSNs.

Cognitive radio (CR) is the key enabling technology for an efficient dynamic spectrum access. It aims at exploiting an underutilized licensed spectrum by enabling opportunistic communications for unlicensed users. In this work, we first develop a distributed cognitive radio MAC (COMAC) protocol that enables unlicensed users to dynamically utilize the spectrum while limiting the interference on primary (PR) users. The main novelty in COMAC lies in not assuming a predefined CR-to-PR power mask and not requiring active coordination with PR users. COMAC provides a statistical performance guarantee for PR users by limiting the fraction of the time during which the PR users' reception is negatively affected by CR transmissions. To provide such a guarantee, we develop probabilistic models for the PR-to-PR and the PR-to-CR interference under a Rayleigh fading channel model. From these models, we derive closed-form expressions for the mean and variance of interference. Empirical results show that the distribution of the interference is approximately lognormal. Based on the developed interference models, we derive a closed-form expression for the maximum allowable power for a CR transmission. We extend the min-hop routing to exploit the available channel information for improving the perceived throughput. Our simulation results indicate that COMAC satisfies its target soft guarantees under different traffic loads and arbitrary user deployment scenarios. Results also show that exploiting the available channel information for the routing decisions can improve the end-to-end throughput of the CR network (CRN).

The scarcity of unlicensed spectrum has triggered great interest in cognitive radio (CR) technology as a means to improve spectrum utilization. An important challenge in this domain is how to enable nodes in a CR network (CRN) to access the medium opportunistically. Multi-channel MAC protocols for typical ad hoc networks assume that frequency channels are adjacent and that there are no strict constraints on the transmission power. However, a CRN may occupy a wide range of frequencies. In addition, a power mask is often enforced on the transmission power of a CR user to avoid corrupting the transmissions of spectrum-licensed primary-radio (PR) users. Obviously, CR users operating in different licensed bands will be subject to different PR-to-CR interference conditions. To avoid unnecessary blocking of CR transmissions under these constraints, we propose a novel distance-dependent MAC protocol for CRNs (DDMAC) that attempts to maximize the CRN throughput. DDMAC introduces a novel suboptimal probabilistic channel assignment algorithm that exploits the dependence between the signal's attenuation model and the transmission distance while considering the traffic profile. The protocol allows a pair of CR users to communicate on a channel that may not be optimal from one user's perspective, but that allows more transmissions to take place simultaneously, especially under moderate to high traffic loads. Simulation results indicate that compared to typical multi-channel CSMA-based protocols, DDMAC decreases the connection blocking rate of CR transmission requests by up to 30%, which improves the network throughput at no additional cost in energy consumption. On the whole, our protocol is simple yet effective. It can be incorporated into existing multi-channel systems with little extra processing overhead.

Abstract Time synchronization is essential for several ad‐hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a time synchronization framework for clustered, multi‐hop sensor networks. We assume that relative node synchronization is sufficient, that is, consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within two‐hops) and perform inter‐regional synchronization in O(LLSync) × Niter time, where O(LLSync) denotes the complexity of the underlying low‐level synchronization technique (used for single‐hop synchronization), and Niter denotes the number of iterations where the low‐level synchronization protocol is invoked. Thus, our main objective is rapid convergence. We propose novel fully distributed protocols, SYNC‐IN and SYNC‐NET, for regional and network synchronization, respectively, and prove that Niter is O(1) for all protocols. Our framework does not require any special node capabilities (e.g., being global positioning systems (GPS)‐enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter‐cluster routing, and low‐level synchronization protocols. We formulate a density model for analyzing inter‐regional synchronization, and evaluate our protocols via extensive simulations. Copyright © 2007 John Wiley & Sons, Ltd.

When sensors are redundantly deployed, a subset of senors should be selected to actively monitor the field (referred to as a "cover"), while the rest of the sensors should be put to sleep to conserve their batteries. We consider networks in which all the nodes are not aware of their locations or the relative directions of neighbors. We develop several geometric and density-based tests for deciding whether a sensor should turn itself off without degrading the quality of field coverage. These tests rely on estimated neighbor distances and locally advertised two-hop neighborhood information. We design an algorithm (LUC) that exploits these tests for computing covers. Based on LUC, we propose two distributed protocols (LUC-I and LUC-P) that periodically select covers and switch between them to extend "coverage time" and tolerate unexpected failures. Our protocols are highly efficient in terms of message overhead and processing complexity. We implement LUC-I in TinyOS and evaluate it using the TOSSIM simulator. Experimental results indicate that our approach significantly prolongs coverage time.

Improving the network throughput is a primary objective in mobile ad hoc networks (MANETs), which is motivated by the over-conservative nature of the 802.11 standard. Transmission power control (TPC) was proposed for improving spatial reuse and reducing energy consumption in MANETs. Previous TPC protocols either incur extra hardware cost (e.g., require multiple transceivers) or do not fully exploit the potential of power control. In this work, we propose distributed, single-channel MAC protocols for MANETs that exploit TPC and account for different packet sizes in the system to further maximize spatial reuse. We model channel contention in the network as a non-cooperative game. Multiple potential transmitters are first involved in an admission phase which enables terminals to compute the transmission powers that achieve a Nash equilibrium (NE) for a given utility function. Subsequently, successful contenders in the same neighborhood can simultaneously proceed with their transmissions. Simulation results show that our protocols significantly improve the network throughput (in terms of transmitted bits/second or the number of admitted contenders) over previously proposed schemes. Our results also indicate that these gains do not require additional energy cost

Several sensor network applications, such as environmental monitoring, require data aggregation to an observer. For this purpose, a data aggregation tree, rooted at the observer, is constructed in the network. Node clustering can be employed to further balance load among sensor nodes and prolong the network lifetime. In this paper, we design and implement a system, iHEED, in which node clustering is integrated with multi-hop routing for TinyOS. We consider simple data aggregation operators, such as AVG or MAX. We use a simple energy consumption model to keep track of the battery consumption of cluster heads and regular nodes. We perform experiments on a sensor network testbed to quantify the advantages of integrating hierarchical routing with data aggregation. Our results indicate that the network lifetime is prolonged by a factor of 2 to 4, and successful transmissions are almost doubled. Clustering plays a dominant role in delaying the first node death, while aggregation plays a dominant role in delaying the last node death

Abstract — Time synchronization is essential for several ad-hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a clusteringbased time synchronization framework for multi-hop sensor networks. We assume that relative node synchronization is sufficient, i.e., consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within 2-hops) and perform inter-regional synchronization in O(LLSync) × Niter time, where O(LLSync) denotes the complexity of the underlying low-level synchronization technique (used for single hop synchronization), and Niter denotes the number of iterations where the low-level synchronization protocol is invoked. We propose two novel fully-distributed protocols, SYNC-IN and SYNC-NET, for regional and network synchronization, respectively, and prove that Niter is O(1) for both protocols. We exploit the tradeoff between rapid convergence (and consequently energy-efficiency) and perceived accuracy. Our framework does not require any special node capabilities (e.g., being GPS-enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter-cluster routing, and low-level synchronization protocols. We formulate a density model for analyzing interregional synchronization, and evaluate our protocols via extensive simulations. Index Terms — Sensor networks, time synchronization, node clustering I.

We design and implement an efficient on-line approach, FlowMate, for clustering flows (connections) emanating from a busy server, according to shared bottlenecks. Clusters can be periodically input to load balancing, congestion coordination, aggregation, admission control, or pricing modules. FlowMate uses in-band (passive) end-to-end delay measurements to infer shared bottlenecks. Delay information is piggybacked on feedback from the receivers, or, if impossible, TCP or application round-trip time estimates are used. We simulate FlowMate and examine the effects of network load, traffic burstiness, network buffer sizes, and packet drop policies on clustering correctness, evaluated via a novel accuracy metric. We find that coordinated congestion management techniques are more fair when integrated with FlowMate. We also implement FlowMate in the Linux kernel v2.4.17 and evaluate its performance on the Emulab testbed, using both synthetic and tcplib-generated traffic. Our results demonstrate that clustering of medium to long-lived flows is accurate, even with bursty background traffic. Finally, we validate our results on the Internet Planetlab testbed.

Prolonged network lifetime, scalability, and load balancing are important requirements for many ad-hoc sensor network applications. Clustering sensor nodes is an effective technique for achieving these goals. In this work, we propose a new energy-efficient approach for clustering nodes in ad-hoc sensor networks. Based on this approach, we present a protocol, HEED (hybrid energy-efficient distributed clustering), that periodically selects cluster heads according to a hybrid of their residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED does not make any assumptions about the distribution or density of nodes, or about node capabilities, e.g., location-awareness. The clustering process terminates in O(1) iterations, and does not depend on the network topology or size. The protocol incurs low overhead in terms of processing cycles and messages exchanged. It also achieves fairly uniform cluster head distribution across the network. A careful selection of the secondary clustering parameter can balance load among cluster heads. Our simulation results demonstrate that HEED outperforms weight-based clustering protocols in terms of several cluster characteristics. We also apply our approach to a simple application to demonstrate its effectiveness in prolonging the network lifetime and supporting data aggregation.

Clustering sensor nodes increases the scalability and energy efficiency of communications among them. In hostile environments, unexpected failures or attacks on cluster heads (through which communication takes place) may partition the network or degrade application performance. In this work, we propose a new approach, REED (Robust Energy Efficient Distributed clustering), for clustering sensors deployed in hostile environments. Our primary objective is to construct a k (i.e., k-connected) network, where k is a constant determined by the application. Fault tolerance can be achieved by selecting k independent sets of cluster heads (i.e., cluster head overlays) on top of the physical network, so that each node can quickly switch to other cluster heads in case of failures or attacks on its current cluster head. The independent cluster head overlays also provide multiple vertex-disjoint routing paths for load balancing and security. Network lifetime is prolonged by selecting cluster heads with high residual energy and low communication cost, and periodically reclustering the network in order to distribute energy consumption among sensor nodes. We prove that REED can asymptotically achieve k tolerance if certain constraints on node density are satisfied. We also investigate via simulations the clustering properties of REED, and show that building multiple cluster head overlays does not consume significant energy.

Topology control in a sensor network balances load on sensor nodes and increases network scalability and lifetime. Clustering sensor nodes is an effective topology control approach. We propose a novel distributed clustering approach for long-lived ad hoc sensor networks. Our proposed approach does not make any assumptions about the presence of infrastructure or about node capabilities, other than the availability of multiple power levels in sensor nodes. We present a protocol, HEED (Hybrid Energy-Efficient Distributed clustering), that periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED terminates in O(1) iterations, incurs low message overhead, and achieves fairly uniform cluster head distribution across the network. We prove that, with appropriate bounds on node density and intracluster and intercluster transmission ranges, HEED can asymptotically almost surely guarantee connectivity of clustered networks. Simulation results demonstrate that our proposed approach is effective in prolonging the network lifetime and supporting scalable data aggregation.

We design an efficient on-line approach, FlowMate, for partitioning flows at a busy server into flow groups that share bottlenecks. These groups are periodically input to congestion coordination, aggregation, load balancing, admission control, or pricing modules. FlowMate uses in-band packet delay measurements to the receivers to determine shared bottlenecks among flows. Packet delay information is piggybacked on returning feedback, or, if impossible, flow (e.g., TCP) round trip time estimates are used. We simulate FlowMate to examine the effect of network load, traffic burstiness, network buffer sizes, and packet drop policies on partitioning correctness. Our results demonstrate accurate partitioning of medium to long-lived flows even under heavy load and self-similar background traffic. Experiments with HTTP/1.1 flows demonstrate difficulties in partitioning bursty foreground traffic. We also study fairness of coordinated congestion management when integrated with FlowMate.