FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 33, N o 4, December 2020, pp. 617-630 https://doi.org/10.2298/FUEE2004617M © 2020 by University of Niš, Serbia | Creative Commons License: CC BY-NC-ND DISTRIBUTED MULTI-HOP ROUTING ALGORITHM FOR WIRELESS SENSOR NETWORKS  Morteza Mohammadi Zanjireh, Jaafar Gadban Department of Computer Engineering, Imam Khomeini International University, Qazvin, Iran Abstract. In a Wireless Sensor Network (WSN), routing is the process of finding a cost- effective route in terms of power consumption. As an evaluation criterion for the WSN performance, network lifetime is directly affected by the routing method. In a wide variety of WSNs, different techniques are used as routing methods, such as shortest distance path. In this paper, we propose a novel algorithm, optimizing power consumption in WSN nodes, based on the shortest path algorithm. In this approach, the energy level of nodes and their geographical distance from each other contribute to the weight of the connecting path. The proposed algorithm is used as a data dissemination method in WSNs with randomly scattered nodes. We also apply Dijkstra’s shortest path algorithm to the same networks. The results showed that the proposed algorithm increases the network lifetime up to 30 % by preventing nodes with low charge levels from early disconnection. Key words: wireless sensor network, routing, network lifetime, Dijkstra’s algorithm. 1. INTRODUCTION A Wireless Sensor Network (WSN) [1][2][3][4][5][6][7][8] is an ad hoc network consisting of a set of distributed, small, low-power, low-cost sensor nodes that communicate through a wireless link and have limited memory, computational, and communication resources. In addition, sensor nodes can have such special equipment as Global Positioning System (GPS) antenna helping them locate themselves (location-aware networks) [9]. Each node continuously monitors the environmental condition, collects detailed information about it, and then transmits the collected data to a special node, called a sink or Base Station (BS) [10]. This station passes the received data to the server from where the end- user can access it. The WSNs do not rely on a pre-existing infrastructure, such as routers in wired networks or access points in managed wireless networks [11]. Moreover, sensor nodes are positioned  Received April 1, 2020; received in revised form June 14, 2020 Corresponding author: Morteza Mohammadi Zanjireh Department of Computer Engineering, Imam Khomeini International University, 34148-96818 Qazvin, Iran E-mail: Zanjirehm@eng.ikiu.ac.ir 618 M. M. ZANJIREH, J. GADBAN randomly and therefore, all the protocols and algorithms have self-organizing capability [12]. In addition, they can be homogeneous or heterogeneous based on the types of storage and processing capacities, battery power, and sensing and communication capabilities [13][14]. They also can be static, in which sensors are in fixed positions, or dynamic considering nodes as moving objects [13]. Additionally, WSNs can be single-hop or multi-hop[4][5][6][8][15]. In multi-hop fashion, a sensor node plays a dual role, working as data originator and data router, but in a single-hop one, the sensor sends the collected data directly to the BS[1][16][17]. Applications of WSN range from small-size healthcare surveillance systems to large- scale environmental monitoring. Such networks can only attain their objectives as long as they are “alive”. The WSN lifetime, therefore, is an important metric forming an upper bound for the network availability. This metric, depending on the lifetimes of all the sensor nodes, evaluates the performance, availability, and security of the network in an application- specific way [18]. One of the most important tasks in the WSN, affecting its lifetime, is communication. In such a network, routing [1] is the process of finding a cost-effective route in terms of power consumption. The simplest method to send data packets to the BS is direct transmission in which each sensor node communicates with the BS individually. The second approach is flooding protocol [19][20][21] whereby each node must transmit the received packet to all of its neighbors. This process continues until the packet reaches its destination or the maximum number of hops. On the other hand, the gossiping algorithm is a version of flooding protocol [22] in which a node sends the packet to a randomly selected neighbor. The shortest distance or hop path algorithms, such as Dijkstra’s and Bellman-Ford [23], are also well-known, time and energy-efficient solutions to determine the best path for data transmission [24]. The routing techniques are classified based on architecture, protocol operation, and topology (route selection strategies) of the network. Each routing algorithm can be included in more than one category [25]. Based on the network architecture, there are three subcategories [26]; flat, hierarchical, and location-based. As a source initiated technique, flat or “data-centric” routing [1][27] uses a network setup message, including hop counts and remaining energy level of neighbor nodes, to find the route. Hierarchical routing [17][28][29][30][31] is an energy-efficient technique determining the role of each node based on its energy level. In location-based routing techniques, each sensor node is aware of its location [27]. Operation based routing protocols want to achieve optimal performance and save the scarce resources of the network. These techniques include query, negotiation, Quality of Service (QoS), path selection, and coherent based routing [1][32][33]. The main idea behind topology routing protocols is that how the source node computes and maintains the paths to the destination nodes [10][13][34][35][36]. This category is subdivided into proactive, reactive, and hybrid-based routing. Selecting an appropriate routing algorithm is a fundamental task in WSN applications and directly affects the network lifetime. Inefficient routing algorithm drains off the energy of nodes faster and consequently lowers network availability. The performance of some previously mentioned methods is limited [37]. For example, since BS is usually located far away from sensor nodes, direct transmission not only results in high transmission costs but drains off the energy of nodes faster and reduces system lifetime as well. In flooding technique, nodes ignore the amount of their available energy (resource blindness) and duplicated data packets are sent to the same node (implosion). Having one copy of a message, the gossiping approach avoids this problem but has a longer propagation time. The overlap is another problem of flooding Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 619 technique that happens when two nodes share the same geographical region. Though used in many WSN applications [24], shortest path algorithms have unbounded message complexity and significantly high overhead which make them unsuitable for WSNs due to the energy problem. Shortest hop path algorithms are also used in many protocols for WSNs. In this asynchronous approach, path construction is easy and straightforward, whereas the message complexity cannot be calculated and the initiator node cannot know whether the algorithm terminates. Although numerous methods have been proposed to increase the WSN lifetimes, there is still much ongoing research on how to optimize energy consumption in them. In this research, we propose a distributed multi-hop algorithm. Our goal is to balance the energy consumption between network nodes by creating energy-efficient paths from the BS to all nodes and changing them when the energy levels of constituent nodes drop under a critical level. The proposed algorithm is based on the well-known Dijkstra’s shortest path algorithm [23]. In order to investigate the performance of our proposed algorithm in the WSNs, we implemented it and Dijkstra’s. The obtained results show that our proposed algorithm increases the lifetime of the network up to 30%. The rest of this paper is organized as follows: “Related work” presents the background of routing algorithms in WSNs. The third section introduces the proposed routing algorithm. “Results and discussion” discuss experiment details and experimental results. Finally, the conclusion and the discussion about future work are given in the last section. 2. RELATED WORK Sensor Protocols for Information via Negotiation (SPIN)[38] is a data-centric routing protocol based on a negotiation model to propagate information in the WSN. SPIN overcome the shortage of flooding by negotiation and adapting the resources. In this algorithm, nodes negotiate with each other about their data requirements. This process ensures that there is no redundant data transmission in the network. Directed Diffusion (DD)[39] is a data-centric, query-based routing protocol for data propagation. In this protocol, the BS sends interest message to the network and a sensor node sends gradients towards the BS if its data matches with interest. The path is forming while the source is sending gradients. Rumor Routing (RR) [40], is a variant of the DD algorithm and an example of hybrid routing. This protocol sends queries to the nodes that have observed an event instead of flooding a message into the whole network. Low Energy Adaptive Clustering Hierarchy (LEACH)[41] is a hierarchical routing protocol that adopts an equal probability method to select cluster heads in a circle and random manner. It also distributes the energy of the whole network evenly to each node. COUGAR [42] is another data-centric routing protocol that makes a new query layer between the WSN and its applications. Destination-Sequenced Distance Vector (DSDV) [13] is a popular, highly proactive, loop-free routing protocol. It uses distance vectors to find the shortest path to the destination. Ad hoc On-Demand Distance Vector (AODV) [36] is a scalable, loop-free, reactive routing protocol for mobile ad hoc network, capable of both supporting unicast and multicast routing. Greedy Perimeter Stateless Routing (GPSR) [35] is another reactive geographical routing protocol for WSNs. In this method, each node only needs its neighbors' positions without other topological information. Every node is assumed to have a mechanism, 620 M. M. ZANJIREH, J. GADBAN maybe a GPS device [43], to identify its own location. Distance Routing Effect Algorithm for Mobility (DREAM) [43] is also a geographical routing protocol considered as both proactive and reactive. The Distributed Bellman-Ford (DBF)[43] is a routing algorithm based on shortest distance paths in WSNs suitable for distributed systems. Query-Based Protocol (PEQ) [24] and Inter-Cluster Communication (ICE)[44] are protocols working based on shortest hop path algorithms. ICE uses an acknowledgment based approach to discover faulty paths. 2.1. Dijkstra’s algorithm The Dijkstra’s [23] algorithm is a well-known solution to find the shortest path between two vertices in a weighted, directed graph so that the sum of the weights of its constituent edges is minimized. The Dijkstra’s algorithm assumes that the number of vertices is finite and all edge costs are non-negative. Calculating the shortest path between one node and every other node in the graph, Dijkstra’s algorithm is appropriate for WSN applications. In Figure.1, the green path represents the shortest path between node X and the Base found by Dijkstra’s algorithm. Fig. 1 Shortest path between Base and node X calculated by Dijkstra’s algorithm 3. THE PROPOSED ALGORITHM In this section, we propose an algorithm maximizing the lifetime of the network and balancing power consumption between its nodes. Most of the algorithms mentioned in the previous section have their own deficiencies. For example, flooding algorithm suffers from impulsion, overlap, and resource blindness. Gossiping has high propagation time. SPIN does not guarantee the delivery of data and is not suitable for applications requiring reliable data. DD has high overhead at sensor nodes and is not suitable for the applications requiring a continuous flow of data. RR fails in large networks. COUGAR has extra overhead and Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 621 memory usage and requires synchronization for successful in-network data computation. However the shortest path algorithm is one of the mostly used algorithms for data propagation in WSNs [22], this method has serious problems. One of its problems is that these nodes are located near to the BS and consume more energy than others. Moreover, the shortest distance approach drains off the energy of important nodes playing a bridge role between two parts of the network. Thus, to balance energy consumption in the WSN, we propose a flat routing algorithm, called Layered Routing (LR), that deploys a semi-dynamic transmit range. In this multipath, reactive method, a lower transmission range is set for those nodes near the BS, where higher transmission ranges are set for those nodes that are far away from the BS to reach the BS directly and without using the low energy nodes in the connection path. Our proposed algorithm makes various assumptions, such as: 1. All nodes are stationary. 2. All nodes have the same capabilities (processing, memory, radio, and battery power). 3. Each node has a distinct node ID. 4. Links between nodes are symmetric (i.e. If there is a link from a to b, there exists a reverse link from b to a). 5. Nodes are not aware of their positions (they are not equipped with a GPS receiver). 3.1. Description of proposed algorithm In order to apply the algorithm, the network has to be divided into layers according to the distance between the nodes and the BS. For example, nodes within the 20 m radius of the BS are in the first layer, and nodes within the 40 m radius of the BS, which are not in the first layer, are in the second one. In addition, a unique ID is assigned to each node initially. The routing procedure works as follows: 1. The BS sends a request message to the surrounding nodes within a specific range (e.g. 20 m) to form the first layer. 2. Nodes receiving the request, reply with an acknowledgment message through previous layers (except the first layer in which nodes contact the BS directly). 3. The BS dedicates an ID to each of these nodes and broadcast these IDs (the layer is constructed). 4. The BS increases the transmitting range (40 m). 5. The first 4 steps are repeated (network layering) until no node replies to the BS with the acknowledgment message (i.e. the whole network is layered, Figure 2). 6. To define the paths, a table, Figure 3, is being made to link nodes in different layers with each other and with the BS. The weight of the link between two nodes is determined by considering their distance, is computed in the receiving node via receiving signal strength between them and the sender's residual energy. 7. After running the network, the BS monitors the residual energy in the nodes. When the energy level of a certain fraction of the nodes is less than a predefined threshold (e.g. 10 % of the initial energy), the BS increases the transmitting range to establish a new connection that does not include the low energy nodes. 622 M. M. ZANJIREH, J. GADBAN Fig. 2 A layered WSN (Layers are defined and each node has an unique ID) Fig. 3 Connections table produced by the LR algorithm 3.2. Simulation setups We examine the performance of the LR algorithm using MATLAB R2016b. The simulation results are compared with the performance of Dijkstra’s shortest path algorithm. In the simulated WSN, there are two kinds of nodes: BS and sensor. The efficient transmitting distance among nodes is 25 m for Dijkstra’s and varies between 15 to 50 m for the LR algorithm. In this experiment, the WSN consists of 100 sensor nodes and one BS. These sensor nodes are scattered randomly in a square 100 m by 100 m and the BS is placed in the center of it (Figure 4). Moreover, all the sensor nodes are static and have no mobility. The initial power of a sensor node is 0.5 J and the BS has no energy restriction. The energy consumption for transmitting and receiving a bit per meter are 5*10^(-8) J and 0, respectively. Also, the ideal listening energy cost is set to zero. We also assume that there is no data loss or data collision in the simulation. Each sensor node generates random data (6400 bit per packet) and transmits it to the next node on its path with the highest weight. Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 623 Table 1 Simulation study parameters Parameter Value Area 100*100 m^2 Base station position (50,50) Number of sensors 100 Transmitting Energy(per bit and per meter) 5*10^(-8)J Receiving Energy(per bit and per meter) 0 Initial energy 0.5 J Transmitting range of the Dijkstra’s algorithm (except for experiments in Figure 9) 25 m Transmitting range (proposed algorithm) 15-50 m The simulation continues until there is no connected sensor to the BS. The simulation starts by defining layers and giving IDs to the sensors. Each layer is defined based on its distance from the BS. Sensors’ transmitting signal range is dynamic; it starts with low value and goes up when the energy of the sensors near the BS drops down. Table 2 illustrates the relationship between the transmitting signal range and the number of low energy sensors. Table 2 The relationship between the transmitting signal range and the number of low energy sensors. Number of low energy nodes Transmitting signal range Low energy nodes < 10 % of all nodes 15% of environment length Low energy nodes < 20 % of all nodes 25% of environment length Low energy nodes < 30 % of all nodes 30% of environment length Low energy nodes < 40 % of all nodes 35% of environment length Low energy nodes < 50 % of all nodes 40% of environment length Low energy nodes > 50 % of all nodes 50% of environment length Fig. 4 An example of the random distribution of nodes in WSN 624 M. M. ZANJIREH, J. GADBAN 4. RESULTS AND DISCUSSION Since the nodes are randomly distributed, WSNs with the same number of nodes may have different performance. Therefore, the Dijkstra’s and the LR algorithm are both applied to the same network each time. Each round of the simulation manages to send messages from all alive nodes, with at least one connection, to the BS. Therefore, when the simulation reaches 100 rounds, there will be approximately 10000 messages received by the BS. The connection and the status of nodes are different after each round of simulation. Figure 5 presents the network status after 500 rounds of simulation with Dijkstra’s as the routing method. In Figure 5, node number 1 represents the BS and a dead node does not have any connections. We can notice that after 500 rounds the BS and the remaining alive nodes are disconnected and the network is considered dead. Fig. 5 The connection of nodes after 500 rounds of simulation with Dijkstra’s algorithm as routing method When we applied the LR algorithm to the same network, we can achieve different results (Figures 6 and 7). In these figures, the network holds this transmitting range as long as the number of low energy nodes is under 10 nodes, thereafter the transmitting range is increased. Therefore, more nodes can reach the BS directly and the low energy nodes around it are no longer mediators for signal transmission. As the number of low energy nodes increases, the transmitting range increase as well. This allows more distant nodes to communicate directly to the BS, i.e., low energy nodes are eliminated from the previous connecting paths and consequently, low energy nodes can save more power and remain alive. Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 625 Fig. 6 The connection of nodes after 1000 rounds of simulation with the LR algorithm as routing method (transmitting range 40m) Fig. 7 The connection of nodes after 1200 rounds of simulation with the LR algorithm as routing method (transmitting range 50m) It can be seen that the LR algorithm used the residual energy of nodes in an efficient way to keep the network as alive and functional as possible (1200 rounds of simulation with the LR algorithm versus 500 rounds with Dijkstra’s), and this can be considered as a credible enhancement in Dijkstra’s performance. 626 M. M. ZANJIREH, J. GADBAN The results show that the LR algorithm avoided early splitting of the network. Taking into account the combination of the nodes' distance and the amount of residual energy in the weighting process, the LR algorithm increased the network lifetime. Figure 8 shows that Dijkstra’s split the network and consumed the energy of important nodes faster than the LR algorithm. In other words, using the LR algorithm, nodes can communicate longer (more round of simulation) than the case that Dijkstra’s is used. Fig. 8 A comparison of the performance of the Dijkstra’s and the LR algorithm The results show that both algorithms tend to consume the energy of nodes near the BS faster than the others’ although the LR algorithm tries to overcome this problem by increasing the transmitting range. The simulation has been repeated using different transmitting ranges for Dijkstra’s algorithm (25, 35, 45 and 55 m). Results are shown in Figure 9. Figure 10 also presents a comparison of the number of rounds between the LR algorithm and Dijkstra’s as the routing protocols. The results witness the LR’s better performance in randomly produced networks compared to Dijkstra’s. In another experiment, we changed the size of the WSN (200 m by 200 m) to check the LR performance. The results were promising, that is, this algorithm is flexible against random distribution. Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 627 Fig. 9 Number of Rounds for each transmitting range in Dijkstra’s algorithm Fig. 10 The LR algorithm vs. Dijkstra’s algorithm 628 M. M. ZANJIREH, J. GADBAN 5. CONCLUSION AND FUTURE RESEARCH In this paper, we proposed a novel distributed multi-hop algorithm for WSNs. we used the combination of geographical distance between two nodes and residual energy of them to define the weight of a path. This combination provided flexibility to reassign the communication path for the network. To investigate the effectiveness of the proposed algorithm, we simulated it in the randomly produced WSNs and the results showed that it avoided early split of the network to different parts and thus increased its lifetime. Furthermore, the usage of the residual energy to determine the transmitting range of the nodes not only prevented the network from early death but also provided every node with the ability to communicate with the BS even if its neighbors are dead. The proposed algorithm was compared to Dijkstra’s shortest path algorithm and the results were 30% better than that of Dijkstra’s. On the light of promising results of the proposed algorithm, it could be useful to take into consideration application of the proposed algorithm along with other energy-efficient techniques in WSNs. In this research, we split the network into layers based on their distance from the BS and different transmission ranges are used for different layers. In future work, we will try to make transmitting range adjustment on smaller levels (layer level or on single sensor level) which could enhance the performance and the lifetime of the network. This study did not consider data delay; any future work should study data delay in the proposed algorithm. Moreover, the BS location has an impact on a WSN performance and lifetime; any future work should take this feature into consideration among with having more than one BS in the network. List of abbreviations Ad hoc On-Demand Distance Vector (AODV) Base Station (BS) Destination-Sequenced Distance Vector (DSDV) Directed Diffusion (DD) Distance Routing Effect Algorithm for Mobility (DREAM) Distributed Bellman-Ford (DBF) Global Positioning System (GPS) Greedy Perimeter Stateless Routing (GPSR) Inter-Cluster Communication (ICE) Layered Routing (LR) Low Energy Adaptive Clustering Hierarchy (LEACH) Quality of Service (QoS) Query-Based Protocol (PEQ) Rumor Routing (RR) Sensor Protocols for Information via Negotiation (SPIN) Wireless Sensor Network (WSN) Funding: This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. Distributed Multi-Hop Routing Algorithm for Wireless Sensor Networks 629 REFERENCES [1] A. Djedouboum, A. Abba Ari, A. Gueroui, A. Mohamadou, and Z. Aliouat, “Big Data Collection in Large-Scale Wireless Sensor Networks,” Sensors, vol. 18, no. 12, p. 4474, 2018. [2] V. Mythili, A. Suresh, M. M. Devasagayam, and R. Dhanasekaran, “SEAT-DSR: Spatial and Energy Aware Trusted Dynamic Distance Source Routing Algorithm for Secure Data Communications in Wireless Sensor Networks,” Cogn. Syst. Res., 2019. [3] B. Xi-Rong, Q. Zhi-Tao, Z. Xue-Feng, and Z. Shi, “An efficient energy cluster-based routing protocol for wireless sensor networks,” In Proceedings of the 2009 Chinese Control and Decision Conference, 2009, pp. 4716–4721. [4] M. M. Zanjireh and H. Larijani, “Analytical modelling of the A-ANCH clustering algorithm for WSNs,” In Proceedings of the 2015 Seventh International Conference on Ubiquitous and Future Networks, 2015, pp. 429–434. [5] M. M. Zanjireh and H. Larijani, “A survey on centralised and distributed clustering routing algorithms for WSNs,” In Proceedings of the 2015 IEEE 81st Vehicular Technology Conference (VTC Spring), 2015, pp. 1–6. [6] M. M. Zanjireh, H. Larijani, and W. O. Popoola, “Energy Based Analytical Modelling of ANCH Clustering Algorithm for Wireless Sensor Networks,” Int. J. Adv. Networks Serv., vol. 7, no. 3/4, 2014. [7] M. M. Zanjireh, H. Larijani, and W. O. Popoola, “Activity-aware clustering algorithm for wireless sensor networks,” In Proceedings of the 2014 9th International Symposium on Communication Systems, Networks & Digital Sign (CSNDSP), 2014, pp. 122–127. [8] M. M. Zanjireh, A. Shahrabi, and H. Larijani, “Anch: A new clustering algorithm for wireless sensor networks,” In Proceedings of the 2013 27th International Conference on Advanced Information Networking and Applications Workshops, 2013, pp. 450–455. [9] A. Kumar, H. Y. Shwe, K. J. Wong, and P. H. Chong, “Location-based routing protocols for wireless sensor networks: A survey,” Wirel. Sens. Netw., vol. 9, no. 1, pp. 25–72, 2017. [10] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A distance routing effect algorithm for mobility (DREAM),” In Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, 1998, pp. 76–84. [11] K. Maraiya, K. Kant, and N. Gupta, “Application based study on wireless sensor network,” Int. J. Comput. Appl., vol. 21, no. 8, pp. 9–15, 2011. [12] M. R. Ahmed, X. Huang, D. Sharma, and H. Cui, “Wireless sensor network: characteristics and architectures,” Int. J. Inf. Commun. Eng., vol. 6, no. 12, pp. 1398–1401, 2012. [13] C. E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” ACM SIGCOMM Comput. Commun. Rev., vol. 24, no. 4, pp. 234–244, 1994. [14] Z. Zhu and S. H. Yang, “A possible hardware architecture of wireless sensor nodes,” In Proceedings of the 2006 IEEE International Conference on Systems, Man and Cybernetics, 2006, pp. 3377–3381. [15] M. Singh and V. K. Prasanna, “Optimal energy-balanced algorithm for selection in a single hop sensor network,” In Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications, 2003, pp. 9–18. [16] M. Ilyas and I. Mahgoub, Handbook of sensor networks: compact wireless and wired sensing systems. 2004. [17] S. Saranya and M. Princy, “Routing Techniques in Sensor Network–A Survey,” Procedia Eng., vol. 38, pp. 2739–2747, 2012. [18] I. Dietrich and F. Dressler, “On the lifetime of wireless sensor networks,” ACM Trans. Sens. Networks, vol. 5, no. 1, 2009. [19] A. Kumar and S. Pahuja, “A Comparative Study of Flooding Protocol and Gossiping Protocol in WSN,” Int. J. Comput. Technol. Appl., vol. 5, no. 2, pp. 797–800, 2014. [20] P. Kumarawadu, D. J. Dechene, M. Luccini, and A. Sauer, “Algorithms for node clustering in wireless sensor networks: A survey,” In Proceedings of the 2008 4th International Conference on Information and Automation for Sustainability, 2008, pp. 295–300. [21] Q. Zhang, R. H. Jacobsen, and T. S. Toftegaard, “Bio-inspired low-complexity clustering in large-scale dense wireless sensor networks,” In Proceedings of the 2012 IEEE Global Communications Conference (GLOBECOM), 2102, pp. 658–663. [22] J. N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: a survey,” IEEE Wirel. Commun., vol. 11, no. 6, pp. 6–28, 2004. [23] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, 1959. 630 M. M. ZANJIREH, J. GADBAN [24] O. Yilmaz, S. Demirci, Y. Kaymak, S. Ergun, and A. Yildirim, “Shortest hop multipath algorithm for wireless sensor networks,” Comput. Math. with Appl., vol. 61, no. 1, pp. 48–59, 2012. [25] O. Younis, M. Krunz, and S. Ramasubramanian, “Location-unaware coverage in wireless sensor networks,” Ad Hoc Networks, vol. 6, no. 7, pp. 1078–1097, 2008. [26] X. Chen and P. Yu, “Research on hierarchical mobile wireless sensor network architecture with mobile sensor nodes,” In Proceedings of the 2010 3rd International Conference on Biomedical Engineering and Informatics, 2010, pp. 2863–2867. [27] S. Fedor and M. Collier, “On the problem of energy efficiency of multi-hop vs one-hop routing in wireless sensor networks,” In Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW’07), 2007, pp. 380–385. [28] R. Aggarwal, A. Mittal, and R. Kaur, “Hierarchical Routing Techniques for Wireless Sensor Networks: A Comprehensive Survey,” Int. J. Futur. Gener. Commun. Netw., vol. 9, no. 7, pp. 101–112, 2016. [29] D. Bhattacharyya, T. H. Kim, and S. Pal, “A comparative study of wireless sensor networks and their routing protocols,” Sensors, vol. 10, no. 12, pp. 10506–10523, 2010. [30] V. Kumar, S. B. Dhok, R. Tripathi, and S. Tiwari, “A review study of hierarchical clustering algorithms for wireless sensor networks,” Int. J. Comput. Sci. Issues, vol. 11, no. 3, p. 92, 2014. [31] S. P. Singh and S. C. Sharma, “A survey on cluster based routing protocols in wireless sensor networks,” Procedia Comput. Sci., vol. 45, pp. 687–695, 2015. [32] M. Abdullah and A. Ehsan, “Routing protocols for wireless sensor networks: classifications and challenges,” in Journal of Electronics and Communication Engineering Research, Dec. 2014, vol. 2, pp. 5–15. [33] M. Ullah and W. Ahmad, “Evaluation of routing protocols in wireless sensor networks,” Blekinge Institute of Technology. Karlshamn, Blekinge, Sweden., 2009. [34] X. Hou, D. Tipper, and S. Wu, “A gossip-based energy conservation protocol for wireless ad hoc and sensor networks,” J. Netw. Syst. Manag., vol. 14, no. 3, pp. 381–414, 2006. [35] B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing for wireless networks,” in In Proceedings of the 6th annual international conference on Mobile computing and networking, 2000, pp. 243–254. [36] C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” In Proceedings of the WMCSA’99. Second IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90–100. [37] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Comput. networks, vol. 38, no. 4, pp. 393–422, 2002. [38] J. Kulik, W. Heinzelman, and H. Balakrishnan, “Negotiation-based protocols for disseminating information in wireless sensor networks,” Wirel. networks, vol. 8, no. 2/3, pp. 169–185, 2002. [39] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: A scalable and robust communication paradigm for sensor networks,” In Proceedings of the 6th annual international conference on Mobile computing and networking, 2000, pp. 56–67. [40] D. Braginsky and D. Estrin, “Rumor routing algorthim for sensor networks,” In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002, pp. 22–31. [41] L. XingGuo, W. JunFeng, and B. LinLin, “LEACH protocol and its improved algorithm in wireless sensor network,” In 2016 international conference on cyber-enabled distributed computing and knowledge discovery (CyberC), 2016, pp. 418–422. [42] Y. Yao and J. Gehrke, “The cougar approach to in-network query processing in sensor networks,” ACM Sigmod Rec., vol. 31, no. 3, pp. 9–18, 2002. [43] K. M. Chandy and J. Misra, “Distributed computation on graphs: Shortest path algorithms (TR-LCS- 8203),” Texas University At Austin, 1982. [44] A. Boukerche and A. Martirosyan, “An energy-aware and fault tolerant inter-cluster communication based protocol for wireless sensor networks,” In Proceedings of the IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, 2007, pp. 1164–1168.