Wireless Sensor Network
Vol.5 No.2(2013), Article ID:27987,5 pages DOI:10.4236/wsn.2013.52002

BSDCH: New Chain Routing Protocol with Best Selection Double Cluster Head in Wireless Sensor Networks

Majid Noori1, Alireza Khoshtarash2

1Department of Software Engineering, Islamic Azad University, Mashhad, Iran

2Department of Software Engineering, Islamic Azad University, Ghochan, Iran

Email: M_noory@yahoo.com, arkh314@yahoo.com

Received November 6, 2011; revised December 8, 2011; accepted December 20, 2011

Keywords: Routing Algorithm; Wireless Sensor Networks; Optimum Energy Use


The Optimum use of energy is one of the significant needs in wireless sensor networks, because sensor devices would usually use the battery power. In this article, we give the suggested routing algorithm (BSDCH) with determining an optimum routine due to the energy use and the number of passed hobs. To transfer date from nodes’ sensor to BS (Base Station), data sending has been utilized in chains. In BSDCH algorithm, the nodes’ space is divided into several regions. In this article, each part is called a cluster. In each cluster, a node which is the best due to energy and distance comparison with other cluster nodes it is continuously selected with a given Formula (4) which is called main CH (Cluster Head) and forms a chain in that cluster and in each node cluster, it is selected by Formula (5) as secondary CH with the least distance and the best situation to BS and main CH. the secondary CH task is to receive data from the main CH and send data to the BS. As far as the main cluster head would waste too much energy to send data to BS, so to send data through secondary CH, we can keep main CH energy for more time. In the time of sending data from nodes to main CH, a multi chain is utilized. In the time of making nodes’ chain, nods are connected straight into its main CH radius and other nodes are connected in their sending radius which would have the least distance to main CH. Finally, also, BSDCH has been compared with PEGASIS [1] and PDCH [2]. The simulation results are shown which are indicator of a better BSDCH performance.

1. Introduction

With advancement in processors and wireless contact technology, WSN will be utilized in every where. WSN has a lot of sensors. Sensors are usually distributed in to a far environment and after collection data and doing a series of first processes, they are sent to BS [3,4]. Sensor networks are utilized in fields such as military, medicine, environmental and domestic ones, but in all these fields, each would have a major role in wireless sensor network performance. So, how to routine data and its transfer to BS is done would be very important, because sensors would utilize battery power and have a limited energy. A proper routing method with on optimum energy use and selecting the shortest route to transfer data would be important.

Generally, routing algorithms in sensor networks are as follows [5,6]:

1) On the basis of network structure (flat, multi phase and situation based)

2) On the basis of how the protocol performance would be (according to multiroutine, discourse, survey and service quality).

Increase of network life time, developing and load parallel are the most important needs of a lot of WSN uses. A proper routine among sensors in a network is a proper solution to reach these purposes. Routing in WSN is one of the important research subjects. In this article, we would like to determine an optimum way due to energy use and the least passed hob to send data packages to BS.

Also, in this article we would discuss PDCH problems and find some solutions for a few WSN problems PDCH routing protocol problems PDCH. In part 2, the related works have been explained. In part 3, a radio model of system has been survived. Then BSDCH details is introduced in part 4 and simulation has been show in part 5. Finally, it is also concluded.

2. Related Works

In this part, we compare PEGASIS as the first method in the field and PDCH as a total reference. In PEGASIS, network is divided into similar clusters. In each cluster, the node which has to most energy is selected as a CH, to form a chain, it uses GREADY method. Each node is only connected to a node and receives from that data which this issue makes that in some situations node due to getting its neighbor through other node is not able to send data to it and data to far hand node is not in its sending radius. Which is one of the major deficits. PDCH is one of the newest performed works in this field that it would use initial method PEGASIS to form a chain with a few change. In other words, the limitation of connecting each node to a node has been removed. So, in PEGASIS in each chain, we just have two final nodes, but in PDCH, we would have two or some final nodes which cause subtree in main tree and a better performance of this protocol. On the other hand, in selecting leader in PDCH, 2 nodes are selected which one is main CH and connects and exchange data among intercluster nodes and the other secondary CH would transform data from main CH to BS. In PEGASIS, the leader is first selected and then chain is formed by that but in PDCH, chain is first formed and then it is selected by nodes which are in the main chain, main CH and Cluster Heads secondary branch of the chain. In choosing cluster heads, there is a big limitation and node is selected as a main CH which is in the main tree chain and of course it is connected to one or some nodes in secondary branches. Despite the fact that we have a better performance of PEGASIS method. But, the selection of CH besides this method would have some limitation in selecting nodes such as CH. And only some nodes out of cluster nodes would have the right to select as cluster would have which prevent selecting more efficient nodes as cluster heads. So the main consideration in the chain method which is to select the best nodes as a CH has not been removed. But the first choices for main CH and seconddary CH (Figure 3) is shown.

3. Radio Model for BSDCH

Before studying BSDCH algorithms details we define system model and the related energy. A system including Ntotal sensor has been distributed accidentally in an environment and as BS is located in the middle of environment. The system model is divided into parts with a length of SL.

Energy model of sending and receiving and data bit (l) has been considered according to energy model in LEACH [7]. Then, If the distance of sender to receiver (d) is more than do a multi model (with waste coefficient of route 4) is used, other wise, open space mode (with waste coefficient of route 2) in used


where Eelect, the sufficient energy to activate electronics orbit and εfs and εmp, both strengthening activating energy power for two multi route location and open space. A more general form on this relation, constant coefficient of p and q in expressed as following


for receiver, use energy to receive Bit is as follows:


4. The Details of BSDCH

We have given a new solution to choose the best node as a main and secondary CH and also formed a chain in according to PDCH routings protocol height. First, all nodes are distributed in network by accident. In BSDCH, all nodes are aware with their own place and after being distributed, they are divided into equal regions (Figure 1).

4.1. Main Cluster Head Election Phase

One of the difficulties of multi phase protocols is to select the most suitable node as a CH. One of the difficultties of PDCH algorithm is not to select the best node as a main CH. According to forming a chain, one of the ways of paralleling energy use in a cluster is to create a similar distance for all nodes of main CH, Which is of course problematic to PDCH algorithm which is solved through approaching main CH to the middle of the cluster. As mentioned before in PDCH method, firs chain is formed and then anode is selected as a main CH out of nodes which are connected to more than 2 nodes which this is a big limitation in the field and nodes in both sides of cluster and far from middle may be selected as a volunteer of choosing CH which would makes those nodes which are far from cluster head and take too much energy to send its own data to cluster head from network and nodes which are nearer to get a few energy and would cause a nonparalleling in energy use in network. But in BSDCH method first, CH node is selected without any limitation. So, we can select the best node due to location. In BSDCH protocol we would use who factors to select main CH.

Figure 1. Network divide.

1) Energy of the rest of the node.

2) Node distance to cluster center.

So, we can select any node due to Formula (4) which would have the least F, as main CH node.


Etotal is initial energy of each node and Eremind-i is energy of each node in this time and dto-center is distance of each Node to cluster center. The initial part of this formula would cause selecting node with the most energy in cluster and the second part of that one would specify a node with the least distance to BS in each cluster also, two coefficient α, β have been used to increase or decrease the significance of each part which is the energy significance or distance to cluster center. If we reduce importance of node energy as CH is more than its distant to cluster center and vice versa. In addition, α + β ≤ 1 (Figure 2). As can be seen, with this formula, node with the least distance to cluster center and the most energy extent is select as main CH which would reduce number of passed hobs to reach nodes to main CH and so energy use would decrease.

4.2. Secondary Clustery Head Election Phase

In PDCH algorithm, among node which are related to more than two neighbors, one node is selected as main CH and among neighbor of main CH, node which is not in a main tree, is selected as secondary CH which its role is to receive data from main CH and send it to BS but how this node is selected would face with some limitations. The most important disadvantage of the method is that because, we must select one node out of main CH nodes neighbor in secondary trees. So possibly, the node would have a few energy or not have a proper situation in proportion with BS. In BSDCH algorithm, because all near nodes to main CH send their data in one hob to main CH, so a lot of its around nodes are out of main chain which in this way, it can be a volunteer of secondary CH. In our method, secondary CH is determined by Formula (5). In this formula node with the most energy and the least distance to main CH and the best location to BS is selected as secondary CH.


In this formula, dTO-CH is node distance to main CH and dTO-BS is node distance to BS. α + β + x ≤ 1 How an initial node is selected as a secondary cluster head is shown in Figure 3.

4.3. Chain Construction Phase

After selecting main and secondary CH, a control pack-

Figure 2. Main leader selection in first round.

Figure 3. Form chain and secondary leader in first round.

age in cluster is distributed by main CH node and would form chain in cluster. The package to form chain would include ID of sender node and distance to main CH. After sending the package to form chain nodes which are in the radius of sending main CH, a main CH as a next hob is selected and then, receiver nodes would begin to send it again in the radius of its sending. This process continues until all cluster nodes receive chain forming package then, from chain final node of any node, reserved packages would check themselves in the memory and like (Figure 4), node which is in its sending radius and through it would pass a fewer distance to send data to main CH (the farthest node to itself in sending radius and the nearest node to main CH as next hob and every node would keep its nest hob ID node and in the time of sending ID data, would keep receiver node in head. In this way, because we increase sending radius to reach the package to the farthest neighbor, near neighbor also would receive data in this radius. But after receiving header of package, we see that package belongs to other node and refuse to receive the rest. Although this issue causes receiving energy waste through nodes into radius, we would have a better performance through sending

Figure 4. Data sent to the BS.

data to the nearest neighbor.

Because in this method about 32 bit with the same wasting of package may be received by neighbor nodes wrongly. But in utilized method in previous articles (greedy), due to send data to near neighbor, we would have more hobs which would lose 4000 bit for any extra hob a receiver energy of total package. In comparison with together energy waste is not comparable in both above methods.

5. Simulation and Evaluation

In this part, we compare BSDCH algorithm with PDCH algorithm due to the number of alive nodes, network total energy, energy use variance in each period and the number of sending data package to BS with use of simulator software MATLAB. The utilized extents in simulation have give in Table 1. Also, in simulation α = 2 (open space model), λ = 20 meter has been supposed. In this simulation, it is assumed that in each round, CH of each cluster is selected continuously. After selecting CH, network nodes begin to form chain and then if a node would feel an event around itself, begin to send touched data from environment to BS.

5.1. Network Life Time

A comparison between the number of alive nodes in network life time for three protocol has been computed (Figure 5). BSDCH has increased network life time significantly in comparison with PDCH algorithm and PEGASIS which is the most important agent is to parallel load among nodes of each cluster in network.

5.2. Rate of Reducing Energy Network

Rate of reducing energy network accounts for compareson with energy efficiency in two algorithm. More flat the level of BSDCH, the more parallel energy use would be and is its. Just distribution on to all nodes (Figure 6) would how the comparison of remind energy on to 3 protocols. As can be seen in this figure, energy use chart in BSDCH in comparison with PDCH and PEGASIS would have a more flat gradient which is an indicator of optimum energy use in BSDCH.

5.3. Comparison of Number of Hobs

In this part, to compare delay service quality parameter in two algorithms, we computed the number of package hobs from origin to final destination to do this, number of hobs has been averaged in each passed 50 rounds in to network (Figure 7) to consider delay for every hob, it is obvious that if a package passes fewer hobs from origin to destination, it would have a fewer final to final delay. But with increasing number of hobs. Not only number of

Table 1. Simulate parameters.

Figure 5. Number live nodes per round.

Figure 6. Remind energy all nods.

hobs would increase, but also efficiency of transforming chain energy of package from origin to destination would destroy. There is too much difference in given solution with PDCH algorithm. In this part, we did not compare suggested algorithms with PEGASIS. Because, improving the number of hobs of PEGASIS would cause not to show proper performance of other protocols.

5.4. Number of Lost Events

One of the most important parameter sin sensor networks is the ability to confide in that network. This service quality parameter in fact can be defined due to the network ability in discovery of events in network lime time. The more network can report more events, it would have more confidence in itself. In (Figure 8), there is a comparison among 3 algorithm due to the number of losing events. It is obvious that chart is lower and would indicate that fewer events have been organized out of sensors’ view which its most important reason is to have a paralleled load and a high life time of nodes. As can be see in this figure, it is obvious that BSDCH algorithm would have a more confidence due to event discovery. In this part, we didn’t compare suggested algorithms with PEGASIS. Because, improving the number of hobs of PEGASIS would cause not to show proper performance of other protocols.

6. Acknowledgements

Above, we studied chain routing protocol with the best

Figure 7. Number hobs between nod and BS.

Figure 8. Not sense events.

CH with PDCH and PEGASIS algorithms. We saw that PDCH and PEGASIS algorithms would not have good performance to send data to sink due to energy use and number of passed hobs. In this article, we give a new routing protocol and call it BSDCH. BSDCH would improve network life time. Also, to send data with more speed or fewer hobs is done. With α = 0/8 and β = 0/2 in this formula above mentioned simulation CH has been done. So, it would cause that in selecting CH, distance to cluster center would have a more importance in proportion with energy node and energy parallel among all nodes is more than other methods of WSN, PDCH and PEGASIS which would improve life-time network. Overlap in our protocol is more, because, in every sending, the package is received by multiple nodes. But in the previous methods, in every sending, only one node can receive the package. The routing method BSDCH, for sending data and selects CH of more complex (Powerful processor for the calculation. The powerful transmitter nodes) is compared to other methods.


  1. S. Lindsey and C. Raghavendra, “PEGASIS: Power-Efficient Gathering in Sensor Information Systems,” IEEE Aerospace Conference Proceedings, Vol. 3, 2002, pp. 1125-1130. doi:10.1109/AERO.2002.1035242
  2. L. P. Wang and Z. Cai, “Improved Algorithm of PEGASIS Protocol Introducing Double Cluster Heads,” International Conference on Computer, Mechatronics, Control and Electronic Engineering, Changchun, 24-26 August 2010.
  3. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, Vol. 40, No. 8, 2002, pp. 102-116. doi:10.1109/MCOM.2002.1024422
  4. D. Estrin, R. Govindan, J. Heidemann and S. Kumar, “Next Century Challenges: Scalable Coordination in Sensor Networks,” Proceedings of 5th Annual ACM International Conference Mobile Computing Networking, Seattle, 15-19 August 1999, pp. 263-270. doi:10.1145/313451.313556
  5. K. Akkaya and M. Younis, “A Survey of Routing Protocols in Wireless Sensor Networks,” Elsevier Ad Hoc Network Journal, Vol. 3, No. 3, 2005, pp. 325-349. doi:10.1016/j.adhoc.2003.09.010
  6. J. N. Al-Karak and A. E. Kamal, “Routing Techniques in Wireless Sensor Network: A Survey,” IEEE Wireless Communications, Vol. 11, No. 6, 2004, pp. 6-28. doi:10.1109/MWC.2004.1368893
  7. W. Heinzelman, A. Chandrakasan and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 1, No. 4, 2002, pp. 660-670. doi:10.1109/TWC.2002.804190