TMCnet News
Energy Efficient Least Spanning Routing Tree Algorithm Based on Virtual Grid in Wireless Sensor Networks [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Due to the limitation of energy resources, energy efficiency is a key issue in wireless sensor networks (WSNs). Clustering or shortest routing are proved to be an important way to improve the scalability and prolong the lifetime of wireless sensor networks, but rarely consider the energy efficient and the shortest path at the same time. In this paper, we propose an energy efficient least spanning routing tree algorithm (EELSRT) based on clustering and virtual grid ideas to prolong network lifetime and shorten path while emphasizing energy conservation at the same time. Selecting cluster head includes initialization stage ,dynamic selecting active node and dynamic selecting head stage, namely, partitions the whole network to many cluster and divides each cluster into N×N grid which there is only one active node and others are sleeping, the active node is responsible for receiving, sending and updating table in its grid ,the cluster head is dynamic generates from all active nodes, head is responsible for receiving, sending and maintaining information in its cluster. Then all cluster heads dynamic constructs a least spanning routing tree to prolong network lifetime, save energy and shorten path. Simulation results show that the performance of EELSR on lifetime and energy consumption have further improved by using clustering and least spanning tree, It is a promising approach and deserves more future research. Copyright © 2013 IFSA. Keywords: Wireless sensor networks (WSN), Energy efficient, Least spanning tree, Routing algorithm, Virtual grid. (ProQuest: ... denotes formulae omitted.) 1. Introduction Wireless sensor networks (WSNs) is a new network paradigm that involve the deployment of hundreds-even thousand-of low-cost, energy-limited, small, and application-specific sensor nodes to create applications for factory monitoring and control, disaster response, military sensing intelligent house control, and, etc. [1], Since WSN is typically deployed in an uncontrolled or unreachable environment, each sensor node carries a limited, generally irreplaceable energy source, therefore, energy conservation is the most important performance objective [2] to extend network lifetime while designing WSN protocols. The fundamental notion of clustering scheme is to divide a network into several segments which are generally called by clusters, where a cluster head (CH) is located in the center of each cluster [3]. Consequently, all sensors in WSNs are organized into the clusters where each sensor has its own CH. The key advantage of clustering scheme is to reduce the distance of transmission by communicating with CHs over relatively short distances [4], Also, it can reduce the energy consumption by eliminating redundant transmissions. A CH fuses a collected data into a single data and transmits it to a sink [5]. As cluster heads are responsible for receiving and aggregating the data from their cluster members and transmitting the aggregated data along distance to base station (BS), the energy consumption of cluster heads is much larger than that of cluster members. In order to balance the energy among nodes, most clustering protocols adopt a cluster head rotation mechanism. Cluster head rotation methods used by the existing clustering algorithms can be divided into time-driven cluster head rotation and energydriven cluster head rotation. In time-driven clustering algorithms [6], the role of cluster head is rotated in the entire network periodically according to a predetermined time threshold. This method can effectively balance the network energy consumption. At the same time, since each round of cluster head rotation is carried out in the entire network, the large over head that occurs every time clusters are reformed causes a lot of unnecessary waste. In addition, none of the existing algorithms in this class gives the optimal value of the period [7]. In energy-driven clustering algorithms [8], the roles of cluster head are rotated when the residual energy of cluster head is less than a threshold. Cluster topology maintenance only happens during local cluster head rotation. Thus, the large cost of global topology reconstruction is avoided. A particular WSN, cluster-based WSN (CWSN), is characterized by adopting a cluster-based routing protocol (CRP). In CRP, a set of cluster-heads will be selected after the duration of time which is either periodic or non-periodic. The selected cluster-heads then serve as the cluster centers in a specific clustering algorithm which divides the remaining sensor nodes into several clusters [9]. In CWSN, a member node delivers sensed data to data sink through its cluster-head. Through use of CRP, energy can be conserved because sensed data from member nodes are aggregated to high-level information by a cluster-head in a cluster. Such data aggregation extends network lifetime by filtering redundant and information-less sensed data. In light of the obvious advantage of CRP, many protocol based on the CRP principle. In [10], present a theoretical model and a simple clustering algorithm called Location-based Unequal Clustering Algorithm (LUCA) were proposed, 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. LEACH [11] is a typical clustering protocol proposed for periodical data gathering applications in wireless sensor networks. In LEACH, each node independently elects itself as a cluster head with a probability. Cluster heads receive and aggregate data from cluster members and then send the aggregated data to the BS by single-hop communication. In order to balance energy dissipation, the role of cluster head is periodically rotated among the nodes. LEACH protocol is simple and does not require a large communication over head. However, the performance in heterogeneous networks is not very well, because it does not elect cluster heads based on residual energy of nodes. Energy efficient unequal clustering (EEUC) [12] is a distributed unequal clustering algorithm that elects cluster heads based on the residual energy of nodes. Tentative cluster heads use uneven competition ranges to construct clusters of uneven sizes. The clusters closer to the BS have smaller sizes than those farther away from the BS; thus, the cluster heads closer to the BS can preserve some energy for the inter cluster data forwarding. In this way, the energy consumption among cluster heads is balanced. Similar to LEACH, EEUC adopts timedriven cluster head rotation that may cause a lot of unnecessary waste inevitably. An Unequal Clusterbased Routing (UCR) protocol was proposed in [13]. It groups the nodes into clusters of unequal sizes. Cluster heads closer to the base station have smaller cluster sizes than those farther from the base station, thus they can preserve some energy for the inter-cluster data forwarding. A greedy geographic and energy-aware routing protocol is designed for the inter cluster communication, which considers the trade off between the energy cost of relay paths and the residual energy of relay nodes. However, these algorithms some consider clustering, but not consider re-clustering; some consider re-clustering, but not shorten path. In this paper, we propose an energy efficient least spanning routing tree algorithm based on virtual grid (EELSRT) for wireless sensor network to prolong network lifetime and shorten path while emphasizing energy conservation at the same time. We use virtual grid ideas to divide each cluster into N*N grids which there is only one active node. Clustering includes partitioning stage and choosing stage, namely, partitions the multi-hop network and then chooses cluster-heads, cluster head is responsible for receiving, sending and maintaining information in its cluster. Then all cluster-heads will construct a least spanning routing tree to prolong network lifetime, save energy and shorten path. Simulation results show that the EELSRT performance has further improved by using virtual grid to divide cluster, dynamic clustering and least spanning tree, it is a promising approach and deserves more future research. 2. System Model Energy efficient clustering is a typical application in wireless sensor networks. Our motivation is to study the problem in this kind of application. In this section, we will make some assumptions about the system model and give a statement about network model, energy model and state conversion model. 2.1. Network Model We consider the wireless sensor networks where N nodes in field A are homogenous and energy constrained and the sensor network has the following properties [14]: 1) This network is a static densely deployed network. It means a large number of sensor nodes are densely deployed in a two-dimensional geographic space, forming a network and these nodes do not move any more after deployment. 2) There exists only one Sink node, which is deployed at stationary place outside the WSNS. 3) The energy of sensor nodes cannot be recharged. 4) Sensor nodes are location-aware, i.e. sensor node can get its location information through other mechanisms such as GPS or position algorithms. Each node is assigned a unique identifier [15]. 5) The radio power can be controlled, i.e., a node can vary its transmission power depending on the distance to the receiver [16]. First, the whole area has been divided into many same squares, namely, there are many clusters, and each node can directly communicate with other nodes in a cluster. Then the cluster was divided into MxN small area (the value of M, N is determine by the cluster's size, there are MxN grid in a cluster, each grid is named Gi,k(k=l.. MxN). The network model based on virtual grid is shown un Fig.l. We suppose M=3 and N=3, each small square call as a virtual grid, node distribute into this virtual grid, Cl has 9 virtual grid such as G 1,1,G 1,2, Gl,3,Gl,4,Gl,5,Gl,6,Gl,7,Gl,8 and Gl,9, we suppose virtual grid Gl,5 as a duster head grid, and the pentagram as the cluster head, for arbitrary adjacent virtual grid G 1,1 and G 1,2, each node in Gl,l can communicate with all nodes in Gl,2, and vice versa. In a cluster, the red dot as the working node in each grid and each node can communicate with cluster head, and we suppose the number of simultaneous working node is 1 (square dot), others are sleeping (circular dots). In order to guarantee the network normal working and prolong network lifetime, one sleeping node in a virtual grid will be awaken at the right time so as to instead of the energy-exhausted node or disabled node [17]. 2.2. Energy Model We adopt a simplified power model of radio communication in document [18], namely, in order to send a k-bit packet information and the sending distance is d, the sending energy consumption is ... (l) The distance of node I and node j is dij: ... (2) The receiving energy consumption is Erx{E) - Eelec X k (3) Where Eelec is the energy/bit consumed by the sender and receiver electronics, J/bit, Eeiec=50 nJj/bit, Samp is the J/(bitxm2), Samp =100pJ/bit/m2.we commonly assume that the sending distance and d2 is directly proportional for shorter distance, while the sending distance and d4 is directly proportional for longer distance, so we can see the directly sending to long distance is consumed more energy than multihop sending. But the differentiation from the document [19], we consider the processing consumption in order to proximity real scene, the energy consumption of cluster head is Ep: ... (4) So the residual energy of cluster head is: ... (5) Where nl,n2 are the cluster head respectively sending and receiving times before time Ti. The residual energy of ordinary node j is: ... (6) 3. Energy Efficient Least Spanning Routing Tree Algorithm Based on Virtual Grid (EELSRT) In this work, we consider the wireless networks where all nodes in the network are homogenous and energy constrained, the whole network was departed many cluster and each cluster was divided into N*N virtual grid which there is only one active node and others are sleeping, the head is selected from all active nodes in cluster. In this environment, instead of using a flat configuration, adopting the dynamic clustering and least spanning routing tree approach can statistically multiplex many connections into a few paths so that the overall interferences can be reduced with well-controlled access. 3.1. Dynamic Selecting Head The process of constructing cluster-head is comprised of two phases, as illustrated below: Stepl. Initialization: the whole sensing area has been formed many cluster, each cluster has been divided into N*N grids, there is only one active node which the initial active node is randomly generated by all nodes in its grid and others are sleeping, the initial cluster head is randomly generated from active nodes in cluster. Sink broadcasts a information which includes ID, location etc, when a head receives this message then stores this information and response its ID, location etc to sink and its neighbor heads, so after some time, each head will know its neighbor information and the sink information and build its neighbor head's table which as shown in Table 1, while each head builds its member table which as shown in Table 2 and each node builds its member table which as shown in Table 3. When a new head was generated, the active nodes and new head will update their tables. Step2. Dynamic selecting active node: after an event happens, active node is responsible for sensing, sending data to head, while receiving message from head, then computes its residual energy (Er(a)) and compares with the active node energy threshold (Ev), if Er(a) is less than Ev, the active node will selects a new sleeping node as the new active node from all sleeping nodes in its grid and sends updating message to head, head will update its member table, and the new active node is responsible for this grid and the old active node is sleeping. Step3. Dynamic selecting head: head is responsible for collecting data from all active nodes in cluster and receiving data from neighbor heads, and transmits these to next hop, and computes its residual energy (Er(h)), if Er(h) is large than ET (head energy threshold), it will continue to work; else, first selects a new head from all active nodes which its residual energy is maximum and sends the new head information to all active nodes and its neighbor heads; second, after one neighbor head receives this message, it updates its neighbor table; three, after one active node receives this message, it updates its member table; last, head sends its member table and neighbor table to the new head and to sleeping, the new head will responsible for this cluster. 3.2. Constructing Least Spanning Routing Tree According to Prim algorithm, suppose undirected graph G (V,E,D), where V is the set of cluster-heads and the number is N, namely, V= {CH 1 ,CH2... CHN,sink}, E is the set of connections of cluster-head, namely, E={<Chi,CHj>...<CHk,sink>} and D is the distance of cluster-heads, namely, D={di,j, di,k,....} the process of constructing least spanning tree as illustrated below: Step 1. Initialization:Vl=sink, El=null, and V2=V-V1. Step 2. Sect a edge: which has minimum distance from sink to one cluster-head (suppose is CHi), which CHi is directly connect with Sink, then set,Vl={Sink, CHi}, El={(sink, CHi)}, V2=V2-V1. ?Step 3. For each cluster-head CHk in VI do: select a minimum distance dk,j, which CHkeVl, CHjeV2 and (CHk, CHj) eE, but is noteEl, then Vl=VluCHj, El={( CHk, CHj)} uEl, V2=V2-CHj. Step 4. If V2 is empty then end, else go to step 3. Step 5. End. As illustrated in Fig. 2 and Fig. 3, Fig. 2 shows the initial least spanning tree, after some time, if the power of CHI's cluster-head is lower than threshold, nodes in CHI will execute dynamic clustering head to choose a new cluster-head, this time system will execute constructing least spanning tree algorithm, and make a new least spanning tree as Fig. 3 we can know the total-path of new least spanning tree is shorter than old least spanning tree. 4. Simulation Results This section provides a detailed quantitative analysis comparing the performance of our scheme with no clustering algorithm and with clustering, but no least spanning tree algorithm. The experiment is carried out using the same initial power, the experiment consists of 500 nodes, randomly deployed in 450 m><450 m square area. The radio transmission range is dynamic changed according to the DTRAP method adopted in the initial phase for constructing a multi-cluster [20] and constructing a least spanning tree environment. However, after the construction of a multi-cluster and a least spanning tree sensor network, each node and cluster-head can estimate the distance each other, and thus send messages with the desired SNR using only minimum power. When cluster-head's energy is lower than threshold, system will execute constructing cluster-head and constructing least spanning tree algorithm, so it can forma new clusterhead and a least spanning tree. Besides, in the real word, the channel quality may cause interference in the packet. But, because we focus on traffic which is delay-sensitive rather than error-sensitive, the channel quality is assumed to be uniform in the experiment, and each node is equipped with the same initial power 5 J. Summary of parameters and defined values are shown in Table 4. As shown in Fig. 4, the conventional method which gives no clustering and no least spanning tree, drains its power most rapidly. With clustering added and no least spanning tree gives a longer life when compared with the conventional method. When added clustering and least spanning tree, we can know the lifetime is longer than only using clustering. Fig. 5 shows the energy consumed and its standard deviation from clustering and least spanning tree method are decreased as the value of density increases, but in general, the values obtained are higher than those conventional methods or only using clustering method. 5. Conclusions In this paper, based on virtual grid and dynamic selecting cluster head ideas, we present an energy efficient least spanning routing tree (EELSRT) algorithm for wireless sensor network. Simulation results show that, compared with no clustering and only clustering, but not using least spanning tree algorithm, the performance of EELSRT on lifetime and energy consumption have further improved by using clustering and least spanning tree. It is a promising approach and deserves more future research. Acknowledgements We acknowledge the support of University Natural Science Foundation of Jiangsu Province (No. 08KJD520003), six personnel peak project of Jiangsu Province (DZXX-055) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions, we sincerely thank the anonymous reviewers for their constructive comments and suggestions. References [1]. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks, Vol. 38, No. 4, 2002, pp.393-422. [2]. M. Ilyas, I. Mahgoub, Handbook of sensor networks: compact wireless and wired sensing systems, New York, CRC Press, 2005. [3]. C. Li, M. Ye, G. Chen, J. Wu, An energy-efficient unequal clustering mechanism for wireless sensor networks, in Proceedings of the 2nd IEEE International Conference on Mobile ad-hoc and Sensor Systems (MASS'05), November 2005, pp. 123-129. [4]. T. Shu, M. Krunz, S. Vrudhula, Power balanced coverage-time optimization for clustered wireless sensor networks, in Proceedings of the ACM MobiHoc '05, May 2005, pp. 111-120. [5]. Q. Tian, E. J. Coyle, Optimal distributed detection in clustered wireless sensor networks: The weighted median, in Proceedings of the IEEE INFOCOM'2006, April 2006. [6]. M. Liu, J. Cao, G. Chen, et al., EADEEG: An energyaware data gathering protocol for wireless sensor networks, Journal of Software, Vol. 18, No. 5, 2007, pp. 1092-1109. [7]. Jiguo Yu, Yingying Qi, Guanghui Wang, An energydriven unequal clustering protocol for heterogeneous wireless sensor networks, Control Theory Applications, Vol. 9, No. 1,2011, pp. 133-139. [8]. H. Huang, J. Shen, An energy-driven adaptive cluster head rotation algorithm for wireless sensor networks, Journal of Electronics & Information Technology, Vol. 31, No. 5,2009, pp. 1040-1044. [9]. Wei-Tsung Su, Ko-Ming Chang, Yau-Hwang Kuo, eHIP: An energy-efficient hybrid intrusion prohibition system for cluster-based wireless sensor networks, Computer Networks, Vol. 51, 2007, pp. 1151-1168. [10]. Sungryoul Lee, Han Choe, Byoungchang Park, Yukyoung Song, Chong-Kwon Kim, LUCA: An energy-efficient unequal clustering algorithm using location information for wireless sensor networks, Wireless Personal Communications, Vol. 56, 2011, pp. 715-731. [11]. W. B. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy efficient communication protocol for wireless micro-sensor networks, in Proceedings of the IEEE Hawaii International Conference on System Science, Hawaii, USA, January 2000, pp. 1-10. [12]. C. Li, M. Ye, G. Chen, et al., An energy-efficient unequal clustering mechanism for wireless sensor networks, in Proceedings of the IEEE International Conference on Mobile Ad hoc and Sensor Systems Conference, Washington 2005, pp. 597-604. [13]. Guihai Chen, Chengfa Li, Mao Ye, Jie Wu, An unequal cluster-based routing protocol in wireless sensor networks, Wireless Network, Vol. 15, 2009, pp.193-C207. [14]. M. Ye, C. F. Li, G. H. Chen, J. Wu, EECS: an energy efficient clustering scheme in wireless sensor networks, in Proceedings of the IEEE International Workshop on Strategies for Energy Efficient in Ad hoc and Sensor Networks (IWSEEASN'05), April 2004, pp. 214-226. [15]. Fengjun Shang, Anping Xiong, Mehran Abolhasan, Tadeusz Wysocki, An unequal clustering protocol for wireless sensor networks, Journal of Computational Information Systems, Vol. 6, No. 2, 2010, pp. 477-485. [16]. Ming Liu, Jiannong Cao, Yuan Zheng, et al., An energy-efficient protocol for data gathering and aggregation in wireless sensor networks, The Journal of Super Computing, Vol. 43,2008, pp. 107-125. [17]. Si-Wang Zhou, Ya-Ping Lin et al., A wavelet data compression algorithm using ring topology for wireless sensor networks, Journal of Software, Vol. 18, No. 3,2007, pp. 669-680. [18]. S. R. Gandham, M. Dawande, R. Prakash, S. Venkatesan, Energy efficient schemes for wireless sensor networks with multiple mobile base stations," in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM'03), San Francisco, USA, December 2003, pp. 377-381. [19]. D. Braginsky, D. Estrin, Rumor routing algorithm for sensor networks, in Proceedings of the WSNA'02, Atlanta, USA, September 2002, pp. 22-30. [20]. Jain-Shing Liu, Chun-Hung Richard Lin, Energyefficiency clustering protocol in wireless sensor networks, Ad Hoc Networks, Vol. 3, 2005, pp. 371-388. Jinxue ZHANG, Ming ZHANG College of Electronic Engineering, Huaihai Institute of Technology, Jiangsu, 222005, China Tel.:+86-13003467058 E-mail: [email protected] Received: 1 August 2013 /Accepted: 25 October 2013 /Published: 30 November 2013 (c) 2013 International Frequency Sensor Association |