A Load Balanced Connection Aware Clustering Algorithm for Data FlowMethod and Exploit the Continuation of Wireless Sensor Networks

A Load Balanced Connection Aware Clustering Algorithm for Data FlowMethod and Exploit the Continuation of Wireless Sensor Networks

1K. Murugesan, 2P. Kanagaraj,3S. Jagatheswaran,4P. Devapriya

1PG Student, 2PG Student, 3PG Student, 4PG Student

K.S.R College of Engineering, Tamilnadu,India.

Abstract- Wireless sensor networks have concerned significant attention over the past few years. A growing list of monitoring and tracking applications can employ WSNs for increased effectiveness; especially in hostile and remote areas. In these applications a large number of sensors are needed and requiring effective management of the network. Forming clusters has been the most popular approach to support scalability and energy efficient transmission in Wireless sensor networks (WSN). Significant attention has been paid to clustering strategies and algorithms yielding a large number of publications. In this paper, we propose Load Balanced Connection Aware Clustering algorithm (LBCACA) to make clusters and choose cluster head in WSNs. It considers sensor node status, connection condition, connection density, distance from base station and transmission count to find effective cluster head and build clusters.

1. INTRODUCTION

   A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control.In WSNs, battery power of the sensor node is limited, so the efficient use of energy is a must in topology control. At the same time, since there are usually a large number of nodes in WSNs, the node can only get part of the network topology information. As a result, the clustering algorithms are needed to select the appropriate sub-cluster in local network.Grouping sensor nodes into clusters has been widely pursued by the research community in order to achieve the network scalability objective. Every cluster would have a leader, often referred to as the cluster-head (CH). Although many clustering algorithms have been proposed in the literature for ad-hoc networks [15], the objective was mainly to generate stable clusters in environments with mobile nodes. Many of such techniques care mostly about node reachability and route stability, without much concern about critical design goals of WSNs such as network longevity and coverage.

   Recently, a number of clustering algorithms have been specifically designed for WSNs [610].

   In addition to supporting network scalability, clustering has numerous advantages. It can localize the route set up within the cluster and thus reduce the size of the routing table stored at the individual node [11]. Clustering can also conserve communication bandwidth since it limits the scope of inter- cluster interactions to CHs and avoids redundant exchange of messages among sensor nodes [12]. Moreover, clustering can stabilize the network topology at the level of sensors and thus cuts on topology maintenance overhead. Sensors would care only for connecting with their CHs and would not be affected by changes at the level of inter-CH tier [13]. The CH can also implement optimized management strategies to further enhance the network operation and prolong the battery life of the individual sensors and the network lifetime [12]. A CH can schedule activities in the cluster so that nodes can switch to the low-power sleep mode most of the time and reduce the rate ofenergy consumption. Sensors can be engaged in a round-robin order and the time for their transmission and reception can be determined so that the sensors reties are avoided, redundancy in coverage can be limited and medium access collision is prevented [1417]. Furthermore, a CH can aggregate the data collected by the sensors in its cluster and thus decrease the number of relayed packets[18].

   The main challenge of clustering is to select proper nodes to act as cluster heads and gateways. Previous researches have proposed many cluster head election approaches for constructing cluster. In this paper, Load Balanced Connection Aware Clustering Algorithm (LBCACA) is proposed to determine an energy-efficient, reliable routing path and also balanced clustering structure is formed. The LBCACA primarily considers node status and link condition, density distribution, distance from the base station and uses a novel clustering metric called the predicted transmission count (PTX), to evaluate the qualification of nodes for cluster heads and gateways to construct clusters.

2. RELATED WORKS

   Generally, Wireless sensor networks involve a large number of sensors ranging in the hundreds or even thousands. Clustering is an effective mean for managing such high population of nodes. In this section we present a literature survey of published clustering algorithms for WSNs. The

   work of Baker and Ephremides [19,20] is among the early ones on clustering of wireless networks. The focus is mainly on forming an efficient network topology that can handle the mobility of nodes. By clustering, CHs are hoped to form a backbone network to which cluster members can connect while on the move.In [21], Nagpal and Coore proposed CLUBS, an algorithm that forms clusters through local broadcastnand converge in a time proportional to the local density of nodes. Basically, cluster formation in CLUBS is based on the following three conditions: Every node in the network must be connected to a cluster, Maximum diameter of all clusters in the network should be same and Clusters should support the intra-cluster communication which means nodes in a cluster must be able to communicate with each others.The major problem of CLUBS algorithm is the clusters having their CHs within 1-hop range of each other. If this is the case, both clusters will collapse and CH election process will restart.Unlike most of the published schemes, the goal of Banerjee and Khuller is to form a multi-tier hierarchical clustering [22].A number of clusters properties such as cluster size and the degree of overlap, which are useful for the management and scalability of the hierarchy is also considered while grouping the nodes. In this scheme, any node in the WSN can initiate the cluster formation process. Initiator with least node ID will take precedence, if multiple nodes started cluster formation process at the same time. The algorithm proceeds in two phases: Tree discovery and Cluster formation.

   Bandyopadhyay and Coyle [23] proposed EEHC; a distributed, randomized clustering algorithm for WSNs with the objective of maximizing the network lifetime. CHs collected the sensors readings in their individual clusters and send an aggregated report to the base-station.LEACH is one of the most popular clustering algorithms for WSNs [10]. It forms clusters based on the received signal strength and uses the CH nodes as routers to the base-station. All the data processing such as data fusion and aggregation are local to the cluster. LEACH forms clusters by using a distributed algorithm, where nodes make autonomous decisions without any centralized control.FLOC [24] is a distributed technique that produces approximately equalsized clusters with minimum over-lap. The assumed radio model classifies nodes based on their proximity to te CH into inner (i-band) and outer (o-band).Unlike other distributed clustering schemes, ACE employs an emergent algorithm [25]. Emergent algorithms much like artificial neural networks evolve to optimal solution through a mix of local optimization steps. The main idea of ACE is to allow a node to assess its potential as a CH before becoming one and stepping down if it is not the best CH at the moment.

   HEED [9] is a distributed clustering scheme in which CH nodes are picked from the deployed sensors. HEED considers a hybrid of energy and communication cost when selecting CHs. Unlike LEACH, it does not select cell-head nodes randomly. Only sensors that have a high residual energy can become cell-head nodes. In HEED, each node is mapped to exactly one cluster and can directly communicate with its CH.Ding et al. [26] have proposed DWEHC to achieve more aggressive goals than those of HEED. Basically, generating

   balanced cluster sizes and optimizing the intra-cluster topology. DWEHC proceeds in a distributed manner and has O(1) time complexity. Each sensor calculates its weight after locating the neighboring nodes in its area. The weight is a function of the sensors energy reserve and the proximity to the neighbors. In a neighborhood, the node with largest weight would be elected as a CH and the remaining nodes become members.Wang et al. [27] promoted the idea of clustering the WSN based on the queries and attributes of the data. The main motive is to achieve efficient dissemination of data in the network. The concept resembles the data-centric design model of WSNs.Ying Liao et al. proposed a load-balanced clustering algorithm for WSNs on the basis of their distance and density distribution, making it essentially different from the previous clustering algorithms[30].Sheng-Shih Wang et al.[31] proposed a link-aware clustering mechanism, called LCM, to determine an energy-efficient and reliable routing path. It considers predicted transmission count to elect a cluster head. With the analysis of the above papers we propose Load Balanced Connection Aware Clustering Algorithm (LBCACA) to increase the life time of wireless sensor networks.

3. LOAD BALANCED CONNECTION AWARE CLUSTERING ALGORITHM

   The possible applications of clustering algorithms, proposed previously, are in uniformly distributed WSNs without considering the distance from the base station. However, in the practical application of WSNs, the nodes are usually randomly arranged. In this case, if the clustering algorithm doesnt take the distribution of nodes into account, using uniform clustering strategy may lead to unbalanced topological structure, and some nodes die rapidly because of excessive energy decline. The purpose of LBCACA is to generate clusters with more balanced energy and avoid creating excessive clusters with many nodes. Figure 1 shows the process involved in LBCACA.The basic idea of LBCACA is based on the connectivity density and the distance from the base station to calculate k(clustering radius) and predicted transmission count. The clustering radius is determined by density and distance: if two clusters have the same connectivity density, the cluster much farther from the base station has larger cluster radius; if two clusters have the same distance from the base station, the cluster with the higher density has smaller cluster radius.

   LBCACA can be divided into three stages: cluster head selecting phase, clusters building phase and cycle phase.

   | |

   d(A) = 10 10. (2)

   Choose random node

   Calculate density and distance

   Calculate predicted transmission count

   Choose cluster head

   Form clusters

   Change the cluster head

   Fig 1. Steps in LBCACA

   1. Cluster Head Selecting Phase

      LBCACA follows a distributed approach to establish hierarchical structure in self-organizing mode without central control.LBCACA selects the random nodes to trigger clustering process first. Then the trigger node A calculates its connected density and distance from the base station to determine cluster radius r by (1), and becomes the temporary cluster head.

      r = floor [d(A)/dk(A )] (1)

      Where d (A) is the distance from the base station of A, dk (u) is the connectivity density of node A, is the sensor parameters determined by specific applications of WSNs, and floor is the calculation of rounding.d(A) can be calculated as follows.

      where RSSI is received signal strength indicator, and S is the signal strength with 1 meter distance from the basestation [21]. Nk (A) is k-hop neighbors of node u.

      Nk (A) = {b B |b = a d(a, b) k} (3)

      where d(a, b) is the hops between node a and node a. We use hops to indicate distance approximately. Node connection density is calculated by (4), and |Nk (A)| is the number of k- hop neighbors of node a.

      dk (a) =( |(t, v) E/t, v Nk (u) {u}|)/ |Nk (u)| (4)

      LBCACA follows a distributed approach to build hierarchical structure in self-organizing mode without central control. In this phase, the node with the highest weight in k-hop neighbors of Ut is elected as cluster head. The weight of the node is calculated by (5), which takes the residual energy, connection density, and times of being elected as cluster head of nodes into account. Thus, we can generate clusters more balanced in energy and position.

      W(a) = × P[dk (a)] + × P[Re(a)/E(a)] × P[H(a)],

      0 , , 1, <+<1 (5)

      where , , as the effect factors are defined by specific application, Re(a) is the residual energy of node a, E(a) is the initial energy of node a, H(a) is the times of the node a being elected as cluster head.

      The proposed LBCACA also considers node status and link condition, and predicted transmission count (PTX), to evaluate the suitability of CH or GW candidates. The PTX represents the capability of a candidate for persistent transmission to a specific neighboring node. This study considers the transmit power, residual energy, and link quality to derive the PTX of CH or GW candidate. Each node in the network periodically broadcasts a message to obtain the distance, forward delivery ratio, and reverse delivery ratio of its neighbors, thereby making it possible to determine the ETX. When node si , receives report messages form sj , it can use Eq. (6) to derive the PTX,

      PTX = /(ETXij · Etx (k, dij )) (6)

      where is the residual energy of si , dij is the distance between si and sj, and Et x(k, di j ) is the energy consumption for si to transmit a k-bit message over a distance dij . A large PTX value and weight indicates a high possibility of becoming a Cluster head.

      In the initial stage, the node A triggers the clustering process and sends Hello messages to its k-hop neighbors. The neighbors in k-hop utilize (9) to calculate the respective weight, and then the node with the highest weight will become the cluster head. From then on, cluster head node broadcasts (Head_message) in its k-hop neighbors to declare itself as cluster head and asks them to join the cluster. Head_message

      includes the ID of cluster head node (HID), the ID of the sending node (SID) and the number of hops from the cluster head (HD). When a node receives Head_message, SID can be used to maintain a path to reach the cluster head. The algorithm discards broadcast package when HD is over k to ensure that the cluster is no more than k-hop. When a neighbor node receives Head_message, even if it is already in a cluster, it sends Join_message to the cluster head to request joining the new cluster as long as its weight is lower. Head_message is limited to transmission within k-hop, so it may happen that some nodes couldnt receive any Head_message.

   2. Cluster forming Phase

      LBCACA sets the threshold of cluster size. The number of cluster nodes cannot exceed the threshold to avoid forming large clusters, which will cause extra overhead and thus reduce network lifetime. When the cluster head node receives Join_message sent by the rdinary node, it will compare the size of cluster with threshold to accept new member and update the count of cluster nodes if the size is smaller than threshold, or reject the request. If the rejected node has cluster head already, the clustering process ceases. Otherwise, it finds another appropriate cluster to join. Each member node of cluster maintains a cluster information table, which saves the HID, HD, SID and other information. If a node receives transmitting packet in work, it will update its cluster information table correspondingly. For example, the node checks HD in a newly received packet, if HD is smaller, then it updates the value of HD in table, with SID updated. That is to say, it has found a shorter path to cluster head and sets the new SID as its forwarding node. There is only a single HID entry in the ordinary node because it belongs to one cluster head, but the overlapping cluster node has multiple HID information entries for different clusters.

   3. Cycle phase

   LBCACA avoids the fixed cluster head scheme, with periodic replacement to balance the node energy consumption. The cluster is stable for a while until the process of reelecting cluster head is triggered in T (k). The cluster head gathers the weight of all member nodes, and then selects the node with highest weight as the next head node. In this way, the communication costs are decreased. The reelecting of cluster head occurs in the old cluster, so the broadcast of temporary head and the corresponding responses of all the k-hops neighbors are unnecessary.

4. CONCLUSION

   In this paper, Load Balanced Connection Aware Clustering algorithm (LBCACA) is proposed to build clusters and choose cluster head in WSNs. Sensor node status, connection condition, connection density, distance from base station and predicted transmission count are considered to elect the cluster head. This algorithm can support scalability and energy efficient transmission and it also increase wireless sensor network lifetime.

5. REFERENCES

1. V. Kawadia, P.R. Kumar, Power control and clustering in Ad Hoc networks, in: Proceedings of IEEE INFOCOM, San Francisco, CA, March 2003.

2. M. Chatterjee, S.K. Das, D. Turgut, WCA: a Weighted Clustering Algorithm for mobile Ad Hoc networks, Cluster Computing 5 (2) (2002) 193204.

3. A.D. Amis, R. Prakash, T.H.P. Vuong, D.T. Huynh, Max-Min Dcluster formation in wireless Ad Hoc networks, in: Proceedings of IEEE INFOCOM, March 2000.

4. A.B. McDonald, T. Znati, A mobility based framework for adaptive clustering in wireless ad-hoc networks, IEEE Journal on SelectedAreas in Communications 17 (8) (1999) 14661487.

5. S. Basagni, Distributed clustering algorithm for ad-hoc networks, in: Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), Fremantle, Australia, June 1999.

6. G. Gupta, M. Younis, Load-balanced clustering in wireless sensor networks, in: Proceedings of the International Conference on Communication (ICC 2003), Anchorage, Alaska, May 2003.

7. S. Bandyopadhyay, E. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003.

8. S. Ghiasi, A. Srivastava, X. Yang, M. Sarrafzadeh, Optimal energy aware clustering in sensor networks, Sensors Magazine MDPI 1 (1) (2004) 258269.

9. O. Younis, S. Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed clustering approach for Ad Hoc sensor networks, IEEE Transactions on Mobile Computing 3 (4) (2004) 366379.

10. W.B. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, Application specific protocol architecture for wireless microsensornetworks,IEEE Transactions on Wireless Networking (2002).

11. K. Akkaya, M. Younis, A survey on routing protocols for wireless sensor networks, Elsevier Journal of Ad Hoc Networks 3 (3) (2005) 325349.

12. M. Younis, M. Youssef, K. Arisha, Energy-aware management in cluster-based sensor networks, Computer Networks 43 (5) (2003) 649 668.

13. Y.T. Hou, Y. Shi, H.D. Sherali, On energy provisioning and relaynode placement for wireless sensor networks, IEEE Transactions on Wireless Communications 4 (5) (2005) 25792590.

14. Y. Xu, J. Heidemann, D. Estrin, Geography-informed energy conservation for ad hoc routing, in: Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom01), Rome, Italy, July 2001.

15. M. Adamou, I. Lee, I. Shin, An energy efficient real-time medium access control protocol for wireless ad-hoc networks, in: WIP Session of IEEE Real-time Systems Symposium (RTSS01), London, UK, December 2001.

16. T. Wu, S. Biswas, A self-reorganizing slot allocation protocol for multi- cluster sensor networks, in: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), April 2005.

17. G. Jolly, M. Younis, An energy efficient, scalable and collision less MAC layer protocol for wireless sensor networks, Wireless Communications and Mobile Computing 5 (3) (2005) 285304.

18. K. Dasgupta, K. Kalpakis, P. Namjoshi, An efficient clustering based heuristic for data gathering and aggregation in sensor networks, in: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC, 2003), New Orleans, LA, March 2003.

19. D.J. Baker, A. Ephremides, The architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications, COM-29 (11) (1981) 16941701.

20. D.J. Baker, A. Ephremides, J.A. Flynn, The design and simulation of a mobile radio network with distributed control, IEEE Journal on Selected Areas in Communications (1984) 226237.

21. R. Nagpal, D. Coore, An algorithm for group formation in an amorphous computer, in: Proceedings of the 10th International Conference on Parallel and Distributed Systems (PDCS98), Las Vegas, NV, October 1998.

22. S. Banerjee, S. Khuller, A clustering scheme for hierarchical control in multi-hop wireless networks, in: Proceedings of 20th Joint Conference

    of the IEEE Computer and Communications Societies (INFOCOM01), Anchorage, AK, April 2001.

23. S. Bandyopadhyay, E. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003.

24. M. Demirbas, A. Arora, V. Mittal, FLOC: a fast local clustering service for wireless sensor networks, in: Proceedings of Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS04), Palazzo deiCongressi, Florence, Italy, June 2004.

25. H. Chan, A. Perrig, ACE: an emergent algorithm for highly uniform cluster formation, in: Proceedings of the 1st European Workshop on Sensor Networks (EWSN), Berlin, Germany, January 2004.

26. P. Ding, J. Holliday, A. Celik, Distributed energy efficient hierarchical clustering for wireless sensor networks, in: Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems(DCOSS05), Marina Del Rey, CA, June 2005.

27. K. Wang, S. Abu Ayyash, T.D.C. Little, P. Basu, Attributebased clustering for information dissemination in wireless sensor networks, in: Proceeding of 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON05), Santa Clara, CA, September 2005.

28. C. R. Lin and M. Gerla, Adaptive clustering for mobile wireless networks, IEEE J. Sel. Areas Commun., vol. 15, no. 7, pp. 12651275, Sep. 1997.