An efficient routing protocol for the QoS support of large‐scale MANETs

The hierarchical routing algorithm is categorized as a kind of routing method using node clustering to create a hierarchical structure in large‐scale mobile ad hoc network (LMANET). In this paper, we proposed a new hierarchical clustering algorithm (HCAL) and a corresponded protocol for hierarchical routing in LMANET. The HCAL is designed based on a cost metric in the form of the link expiration time and node's relative degree. Correspondingly, the routing protocol for HCAL adopts a reactive protocol to control the existing cluster head (CH) nodes and handle proactive nodes to be considered as a cluster in LMANET. Hierarchical clustering algorithm jointly utilizes table‐driven and on‐demand routing by using a combined weight metric to search dominant set of nodes. This set is composed by link expiration time and node's relative degree to establish the intra/intercommunication paths in LMANET. The performance of the proposed algorithm and protocol is numerically evaluated in average end‐to‐end delay, number of CH per round, iteration count between the CHs, average CH keeping time, normalized routing overhead, and packet delivery ratio over a number of randomly generated benchmark scenarios. Furthermore, to corroborate the actual effectiveness of the HCAL algorithm, extensive performance comparisons are carried out with some state‐of‐the‐art routing algorithms, namely, Dynamic Doppler Velocity Clustering, Signal Characteristic‐Based Clustering, Dynamic Link Duration Clustering, and mobility‐based clustering algorithms.     

Cluster‐based mobility management algorithms for wireless mesh networks

Wireless mesh networks (WMNs) have been the recent advancements and attracting more academicians and industrialists for their seamless connectivity to the internet. Radio resource is one among the prime resources in wireless networks, which is expected to use in an efficient way especially when the mobile nodes are on move. However, providing guaranteed quality of service to the mobile nodes in the network is a challenging issue. To accomplish this, we propose 2 clustering algorithms, namely, static clustering algorithm for WMNs and dynamic clustering algorithm for WMNs. In these algorithms, we propose a new weight‐based cluster head and cluster member selection process for the formation of clusters. The weight of the nodes in WMN is computed considering the parameters include the bandwidth of the node, the degree of node connectivity, and node cooperation factor. Further, we also propose enhanced quality of service enabled routing protocol for WMNs considering the delay, bandwidth, hopcount, and expected transmission count are the routing metrics. The performance of the proposed clustering algorithms and routing protocol are analyzed, and results show high throughput, high packet delivery ratio, and low communication cost compared with the existing baseline mobility management algorithms and routing protocols.     

基于TinyOS的无线传感器网络LEACH算法的改进

LEACH协议是无线传感器网络中最流行的分簇路由协议之一.针对LEACH算法簇分布不均匀以及网络能耗不均衡等问题提出了一种高效节能多跳路由算法.在簇建立阶段,新算法根据网络模型计算出最优簇头间距值,调整节点通信半径以控制簇的大小,形成合理网络拓扑结构;在数据传输阶段,簇头与基站之间采用多跳的通信方式,降低了节点能耗.在TinyOS操作系统下,使用nesC语言设计实现了LEACH-EEMH算法.基于TOSSIM平台的仿真结果表明,新算法较LEACH算法在均衡网络能耗、延长网络寿命方面具有显著优势.     

A Performance Comparison of Flat and Cluster Based Routings in Mobile Ad Hoc Networks

The objective of this paper is to study the performance comparison between flat and cluster-based routings in MANETs. Previous study shows that an earlier proposed cluster-based routing, Cluster based Routing Protocol (CBRP), has poorer performance due to its inefficient clustering algorithms based on Least Clusterhead Change (LCC) and Lowest ID (LID). Thus, in this paper, we first propose a new cluster-based routing, namely efficient cluster based routing protocol (ECBRP), which is based on a more efficient and stable clustering scheme. In addition, a new information table update mechanism utilizing routing events and data forwarding events is introduced in ECBRP to enhance the clustering and routing performance. The performance comparison in terms of packet delivery ratio and normalized routing overhead between flat and cluster based routings are studied extensively. Two flat routings (Dynamic Source Routing (DSR) and Ad Hoc On-demand Distance Vector (AODV)) and two cluster-based routing (CBRP and ECBRP) under various scenarios such as traffic load, mobility, network size and network area are considered in our study. By evaluating the performance of ECBRP and CBRP, we can study how the performance of a CBRP is affected by its underlying cluster structure. Simulation results show that ECBRP can achieve satisfying routing performance and outperform other routing schemes, DSR, AODV and CBRP, under the same simulated scenarios.     

Novel chemical reaction optimization based unequal clustering and routing algorithms for wireless sensor networks

Energy conserving of sensor nodes is the most crucial issue in the design of wireless sensor networks (WSNs). In a cluster based routing approach, cluster heads (CHs) cooperate with each other to forward their data to the base station (BS) via multi-hop routing. In this process, CHs closer to the BS are burdened with heavier relay traffic and tend to die prematurely which causes network partition is popularly known as a hot spot problem. To mitigate the hot spot problem, in this paper, we propose unequal clustering and routing algorithms based on novel chemical reaction optimization (nCRO) paradigm, we jointly call these algorithms as novel CRO based unequal clustering and routing algorithms (nCRO-UCRA). In clustering, we partition the network into unequal clusters such that smaller size clusters near to the sink and larger size clusters relatively far away from the sink. For this purpose, we develop the CH selection algorithm based on nCRO paradigm and assign the non-cluster head sensor nodes to the CHs based on derived cost function. Then, a routing algorithm is presented which is also based on nCRO based approach. All these algorithms are developed with the efficient schemes of molecular structure encoding and novel potential energy functions. The nCRO-UCRA is simulated extensively on various scenarios of WSNs and varying number of sensors and the CHs. The results are compared with some existing algorithms and original CRO based algorithm called as CRO-UCRA to show the superiority in terms of various performance metrics like residual energy, network lifetime, number of alive nodes, data packets received by the BS and convergence rate.     

A Binary PSO Approach for Improving the Performance of Wireless Sensor Networks

Wireless sensor networks are used for low-cost unsupervised observation in a wide-range of environments and their application is largely constrained by the limited power sources of their constituent sensor nodes. Techniques such as routing and clustering are promising and can extend network lifetime significantly, however finding an optimal routing and clustering configuration is a NP-hard problem. In this paper, we present an energy efficient binary particle swarm optimization based routing and clustering algorithm using an intuitive matrix-like particle representation. We propose a novel particle update strategy and an efficient linear transfer function which outperform previously employed particle update strategies and some traditional transfer functions. Detailed experiments confirmed that our routing and clustering algorithm yields significantly higher network lifetime in comparison to existing algorithms. Furthermore, our results suggest that Binary PSO is better equipped to solve discrete problems of routing and clustering than its continuous counterpart, PSO.

     

A novel method to evaluate clustering algorithms for hierarchical optical networks

The routing issues in multi-layer and multi-domain optical networks have drawn much attention in current research. With the introduction of the path computation element, routes can be calculated more efficiently in multi-domain optical networks. However, the optimal degree of routing approach in multi-layer and multi-domain optical networks is also determined by the clustering algorithms deployed for construction of hierarchical networks. Therefore, it is important to investigate the way to evaluate the impact of the clustering algorithm on the routing approach (e.g., blocking probability) in optical networks with dynamic traffic, which has not been studied sufficiently. In this paper, a novel method to describe and evaluate the clustered structures generated by different clustering algorithms for hierarchical optical networks is proposed. This method deploys a novel evaluation metric that represents blocking probability of clustered optical networks, so it can be used as guidelines for designing clustered structures. Besides theoretical analysis, simulations are carried out on different network topologies and clustered types to validate the effectiveness of the method presented.     

面向高动态移动自组织网络的生物启发分簇算法

分簇可以有效地提高大规模移动自组织网络的性能.但高动态的移动自组织网络具有节点移动性强、网络拓扑变化快的特点,应用传统的分簇算法会造成网络性能迅速下降,频繁的簇拓扑更新造成了簇结构的不稳定和控制开销的增加.为了解决传统分簇算法无法适应高动态的大规模移动自组织网络的问题,提出了一种基于生物启发的移动感知分簇算法,该算法对多头绒泡菌的觅食模型进行了改进,使其适用于移动自组织网络领域.由于该算法与节点的移动特性进行了结合,所以该算法可以有效地在高动态移动自组织网络中进行簇的建立与维护.实验结果表明,相较于其他传统分簇算法,本文算法提高了平均链路连接保持时间和平均簇首保持时间,使得簇结构更加稳定,提高了对高动态、大规模移动自组织网络的适应能力.     

Graph cut based clustering for cognitive radio ad hoc networks without common control channels

Clustering is an efficient tool to improve the routing and data transmission performance in large scale networks. However, in cognitive radio ad hoc networks (CRAHNs), clustering design is challenging due to the dynamic spectrum access and the blind information environment. In this paper, we propose a novel distributed clustering algorithm for CRAHNs, where neither a dedicated common control channel (CCC) nor prior topology information is required. First, a neighbor discovery protocol without relying on CCC is proposed to construct the local topology. Then, we model the network as a undirected graph and formulate the clustering process as a graph cut problem. We design a mincut based heuristic algorithm to approximate the optimal clustering solution. After this, we also present a synchronize protocol to achieve the global consistency of cluster memberships. Finally, we propose a proactive cluster maintenance mechanism to reduce the interferences caused by PU activities. We validate our work through comparisons with other clustering methods. The simulation results show that, by adjusting the cluster structure according to the changing spectrum, the proposed method reduces the interference and improves the network efficiency.     

LUCA: An Energy-efficient Unequal Clustering Algorithm Using Location Information for Wireless Sensor Networks

Over the last several years, various clustering algorithms for wireless sensor networks have been proposed to prolong network lifetime. Most clustering algorithms provide an equal cluster size using node??s ID, degree and etc. However, many of these algorithms heuristically determine the cluster size, even though the cluster size significantly affects the energy consumption of the entire network. In this paper, we present a theoretical model and propose a simple clustering algorithm called Location-based Unequal Clustering Algorithm (LUCA), where each cluster has a different cluster size based on its location information which is the distance between a cluster head and a sink. In LUCA, in order to minimize the energy consumption of entire network, a cluster has a larger cluster size as increasing distance from the sink. Simulation results show that LUCA achieves better performance than conventional equal clustering algorithm for energy efficiency.     

无线传感器网络分簇路由协议研究

在无线传感器网络中,分簇型路由在路由协议中占据重要的地位,该协议方便拓扑结构管理,能源利用率高,数据融合简单。文章从簇头生成、簇形成和簇路由3个角度对典型的分簇路由算法LEACH,HEED,EEUC,PEGASIS进行了系统描述,从网络生命周期和节点存活数量等方面,对比了其优缺点,结合该领域的研究现状,指出了未来研究的方向。     

An optimized forwarding protocol for lifetime extension of wireless sensor networks

Optimized routing (from source to sink) in wireless sensor networks (WSN) constitutes one of the key design issues in prolonging the lifetime of battery‐limited sensor nodes. In this paper, we explore this optimization problem by considering different cost functions such as distance, remaining battery power, and link usage in selecting the next hop node among multiple candidates. Optimized selection is carried out through fuzzy inference system (FIS). Two differing algorithms are presented, namely optimized forwarding by fuzzy inference systems (OFFIS), and two‐layer OFFIS (2L‐OFFIS), that have been developed for flat and hierarchical networks, respectively. The proposed algorithms are compared with popular routing protocols that are considered as the closest counterparts such as minimum transmit energy (MTE) and low energy adaptive clustering hierarchy (LEACH). Simulation results demonstrate the superiority of the proposed algorithms in extending the WSN lifetime. Copyright © 2008 John Wiley & Sons, Ltd.     

Mobile backbone synthesis for ad hoc wireless networks

In this paper, we present an extended mobile backbone network topology synthesis algorithm (ETSA) for constructing and maintaining a dynamic backbone structure for mobile ad hoc wireless networks. We present and analyze the mathematical features of the proposed scheme. Using these results, we prove that: (1) The ETSA scheme converges in constant time; (2) The length of each control packet is bounded by a constant value that is independent of the number of network nodes; (3) The size of the backbone network depends only on the size of the operational area and is independent of nodal density. We compare the performance features of this scheme with those characterizing other protocols that employ clustering operations and/or use selective forwarding on demand routing methods. In addition, we present an on-demand routing protocol (MBNR) that makes use of the underlying dynamically self-configuring backbone network infrastructure and demonstrate its performance advantages when compared with an on-demand routing protocol that is based on a flat architecture, as well as with other backbone-based routing protocols.     

A Review on Hierarchical Routing Protocols for Wireless Sensor Networks

The routing protocol for Wireless Sensor Networks (WSNs) is defined as the manner of data dissemination from the network field (source) to the base station (destination). Based on the network topology, there are two types of routing protocols in WSNs, they are namely flat routing protocols and hierarchical routing protocols. Hierarchical routing protocols (HRPs) are more energy efficient and scalable compared to flat routing protocols. This paper discusses how topology management and network application influence the performance of cluster-based and chain-based hierarchical networks. It reviews the basic features of sensor connectivity issues such as power control in topology set-up, sleep/idle pairing and data transmission control that are used in five common HRPs, and it also examines their impact on the protocol performance. A good picture of their respective performances give an indication how network applications, i.e whether reactive or proactive, and topology management i.e. whether centralized or distributed would determine the network performance. Finally, from the ensuring discussion, it is shown that the chain-based HRPs guarantee a longer network lifetime compared to cluster-based HRPs by three to five times.     

Topology control of tactical wireless sensor networks using energy efficient zone routing

The US Department of Defense (DoD) routinely uses wireless sensor networks (WSNs) for military tactical communications. Sensor node die-out has a significant impact on the topology of a tactical WSN. This is problematic for military applications where situational data is critical to tactical decision making. To increase the amount of time all sensor nodes remain active within the network and to control the network topology tactically, energy efficient routing mechanisms must be employed. In this paper, we aim to provide realistic insights on the practical advantages and disadvantages of using established routing techniques for tactical WSNs. We investigate the following established routing algorithms: direct routing, minimum transmission energy (MTE), Low Energy Adaptive Cluster Head routing (LEACH), and zone clustering. Based on the node die out statistics observed with these algorithms and the topological impact the node die outs have on the network, we develop a novel, energy efficient zone clustering algorithm called EZone. Via extensive simulations using MATLAB, we analyze the effectiveness of these algorithms on network performance for single and multiple gateway scenarios and show that the EZone algorithm tactically controls the topology of the network, thereby maintaining significant service area coverage when compared to the other routing algorithms.     

Distributed, scalable routing based on vectors of link states

We have present a new method for distributed routing in computer networks and internets using link-state information. Link vector algorithms (LVA) are introduced for the distributed maintenance of routing information in large networks and internets. According to an LVA, each router maintains a subset of the topology that corresponds to adjacent links and those links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates; each such update specifies a link and its parameters. The LVA can be used for different types of routing. The correctness of the LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router and each router is able to differentiate old updates from new. The LVA are shown to have better performance than the ideal link-state algorithm based on flooding and the distributed Bellman-Ford algorithm     

Simulation of the Tree Algorthm in ATM Networks

ＡＴＭｉｓｄｅｐｅｎｄｅｎｔｏｎｔｈｅｄｉｆｆｅｒｅｎｔｃｈａｒａｃｔｅｒｉｓ ｔｉｃｓｉｎａｎｉｎｔｅｇｒａｔｅｄｗａｙｔｏｔｒａｎｓｍｉｔｓｅｒｖｉｃｅｓ[1 ] .ＡＴＭｎｅｔｗｏｒｋｍａｙｉｎｃｌｕｄｅｖｉｄｅｏ ,ｖｏｉｃｅａｎｄｉｍａｇｅｓ,ｉｎｔｅｒａｃｔｉｖｅｃｏｍｐｕｔｅｒｄａｔａａｎｄｆｉｌｅｔｒａｎｓｆｅｒｓ.Ａｎｉｍ ｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｏｆａｎＡＴＭｎｅｔｗｏｒｋｉｓｔｏｓｕｐｐｏｒｔｍｕｌｔｉｍｅｄｉａｓｙｓｔｅｍｓ,ｓｕｃｈａｓｖｉｄｅｏｃｏｎｆｅｒｅｎｃｉｎｇ…     

传感器网络中一种分布式数据汇聚层次路由算法

由于传感器网络具有能量约束,低速率冗余数据和多对一传输等特点,传统的端到端集中式路由算法一般不适合传感器网络.提出了一种分布式数据汇聚层次路由算法,该算法利用能量核的思想汇聚数据和减少传输到目的节点的信息.模拟结果表明:比较传统的端到端集中式路由算法,该算法可以显著减少能量消耗;与一般的数据汇聚算法相比,该算法在保证能量消耗少的条件下,具有复杂度低和可扩展性好的特点.     

A green cluster‐based routing scheme for large‐scale wireless sensor networks

In wireless sensor networks (WSNs), clustering has been shown to be an efficient technique to improve scalability and network lifetime. In clustered networks, clustering creates unequal load distribution among cluster heads (CHs) and cluster member (CM) nodes. As a result, the entire network is subject to premature death because of the deficient active nodes within the network. In this paper, we present clustering‐based routing algorithms that can balance out the trade‐off between load distribution and network lifetime “green cluster‐based routing scheme.” This paper proposes a new energy‐aware green cluster‐based routing algorithm to preventing premature death of large‐scale dense WSNs. To deal with the uncertainty present in network information, a fuzzy rule‐based node classification model is proposed for clustering. Its primary benefits are flexibility in selecting effective CHs, reliability in distributing CHs overload among the other nodes, and reducing communication overhead and cluster formation time in highly dense areas. In addition, we propose a routing scheme that balances the load among sensors. The proposed scheme is evaluated through simulations to compare our scheme with the existing algorithms available in the literature. The numerical results show the relevance and improved efficiency of our scheme.     

Stability‐aware multi‐metric clustering in mobile ad hoc networks with group mobility

Clustering can help aggregate the topology information and reduce the size of routing tables in a mobile ad hoc network (MANET). The maintenance of the cluster structure should be as stable as possible to reduce overhead and make the network topology less dynamic. Hence, stability measures the goodness of clustering. However, for a complex system like MANET, one clustering metric is far from reflecting the network dynamics. Some prior works have considered multiple metrics by combining them into one weighted sum, which suffers from intrinsic drawbacks as a scalar objective function to provide solution for multi‐objective optimization. In this paper, we propose a stability‐aware multi‐metric clustering algorithm, which can (1) achieve stable cluster structure by exploiting group mobility and (2) optimize multiple metrics with the help of a multi‐objective evolutionary algorithm (MOEA). Performance evaluation shows that our algorithm can generate a stable clustered topology and also achieve optimal solutions in small‐scale networks. For large‐scale networks, it outperforms the well‐known weighted clustering algorithm (WCA) that uses a weighted sum of multiple metrics. Copyright © 2008 John Wiley & Sons, Ltd.