International Journal of Interactive Mobile Technologies – ISSN: 1865-7923 – Vol. 13, No. 01, 2019 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink https://doi.org/10.3991/ijim.v13i01.9539 Khalil H. A. Al-Shqeerat (*) Qassim University, Buraydah, Saudi Arabia kh.alshqeerat@qu.edu.sa Abstract—In Wireless Sensor Networks, no physical backbone infrastructure used in addition to all sensors are energy constrained and impractical to recharge. The behaviour of networks becomes unstable once the first node dies. The key challenge in such networks is how to reduce energy consumption to increase the network lifetime, especially with the different amount of energy in heterogeneity environments. In this paper, the virtual backbone routing solution is suggested to reduce energy consumption in a wireless sensor network. An integrated approach combines both advantages of hierarchical cluster-based architecture and shortest spanning tree topology for constructing a virtual backbone with a mobile sink. The clustering solution is used to divide the network into clusters and reduces the number of nodes included in the communication. While the shortest spanning tree technique is used to construct a backbone among all cluster heads and mobile sink every time the sink traverses to a new location. The proposed approach aims to construct an efficient data aggregation spanning tree used to send or receive data between the mobile sink and elected cluster heads in wireless sensor net- works. It constructs an efficient virtual backbone to decrease the energy con- sumption and prolong the lifetime of the network. Performance evaluation results show how the proposed approach prolongs the lifetime of wireless sensor networks compared to some conventional clustering protocols. Keywords—Wireless Sensor Networks, Heterogeneous, Clustering, Backbone, Mobile Sink, Shortest Spanning Tree. 1 Introduction Wireless Sensor Networks (WSNs), refers to a set of low energy and un-rechargeable battery autonomous sensors that sense and monitor the surrounding environment to per- form particular tasks through wireless communication infrastructure [1]. The sensed data could be transmitted directly (single-hop) or via multi-hop relaying toward a sink. Although single-hop data transmission is easy to implement and feasible in networks deployed in the small sensing area, the multi-hop transmission manner is more convenient in short-distance and large dense areas [2]. iJIM ‒ Vol. 13, No. 1, 2019 53 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink In cluster-based WSNs, the network is split into separate areas called clusters. In every area, a cluster head (CH) node is elected among several nodes, and it is respon- sible for collecting sensed data from other sensor nodes within the same cluster and transmitting it to the central sink. Clustering provides scalability, high efficiency, and low latency for sensor networks [3]. However, the critical challenge is how to choose the convenient CHs inside clusters, and how to manage these clusters to balance traffic load to improve the energy efficiency of sensor nodes and further to prolong the net- work lifetime [4]. In such type of networks, sensor nodes consume the most amount of their energy when transmitting data to the sink. Therefore, an unbalanced energy situa- tion might be occurred due to the distribution of non-uniform sensors. In the single-hop mode, sensors that away from sink consume more energy due to the long distance to the sink and die first, while other sensors near to the sink keep the energy level up. On the other hand, sensors with a multi-hop transmission mode that near the sink consume most of their energy while those far away still retain most of their initial energy. This problem in multi-hop is called hotspot [5]. It can be overcome when a sink moves and changes its location, which leads to change its neighbours and balance energy among most sensor nodes. In recent years, many cluster-based routing protocols with mobile sink have been proposed to alleviate this energy hole among sensors [6]. However, sink mobility might cause adverse impacts on the topology of the entire network, which can mainly reduce the routing performance in WSNs [7]. This paper provides an integrated cluster-based approach to reduce the energy con- sumption of heterogeneous sensor nodes in WSNs by constructing a virtual backbone based on the random mobility of the sink. The suggested approach uses Dijkstra algo- rithm for constructing a shortest spanning tree from the mobile sink (MS) to all elected CHs at particular round. Dijkstra algorithm is a conventional technique that widely used for this purpose. It is simple and easy to maintenance. The rest of the paper is structured as follows. Section II reviews some previous re- searches on cluster-based protocols with a spanning tree routing strategy for construct- ing a backbone in WSNs. The system model is presented in Section III. In Section IV, the suggested approach is demonstrated in details. Section V presents a discussion of our approach and simulation results. 2 Literature Review This section reviews related solutions and approaches that have been proposed for reducing energy consumption to extend the lifetime of WSNs. Most of the previous researches have focused on building the virtual backbone from either sensor nodes or elected CHs towards the sink. The authors in [8] have proposed a novel backbone-based virtual infrastructure (BVI) approach to support mobile sink without global position information to avoid flooding of the entire network. It supports multi-hop clusters and uses rendezvous CHs to reduce the number of CHs and overcome registering the location of MS to all CHs in the network. Consequently, it reduces the overhead of the communication result in 54 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink MS registration. Multiple spanning trees are built from every rendezvous CH to as a root to all other CHs in the BVI. An Energy-aware Virtual Backbone Tree (EVBT) distributed algorithm is proposed in [9] to provide communication between all sensor nodes and central sink. The con- structed tree is rooted at every node and spans the whole network. The sensed data are transmitted from sensor nodes to the sink along backbone tree. In a dense sensor net- work, EVBT consumes low energy compared with the flooding based clustering algo- rithms, such as TopDisc and STEM. A Multi-hop Cluster Based Stable Backbone Trees (MCBT) proposed in [10] is a distributed algorithm to construct a stable backbone based on the residual energy of CHs in order to prolong the lifetime of the network. Moreover, it distributes the traffic load among nodes around the CH for balancing energy consumption. ViTAMin in [11] avoids any wasted energy in both EVBT and MCBT by selecting the efficient upstream link. It constructs a virtual backbone using characteristic distance to achieve the minimal energy consumption between sensor nodes. It adds information about residual energy to the BCR packet to enable nodes that out of backbone tree to select an efficient upstream node. The authors in [12] have proposed a Cluster-Based and Tree-Based Power Efficient Data Collection and Aggregation Protocol (CTPEDCA) based on clustering and Mini- mum Spanning Tree (MST) routing strategy for cluster heads in WSNs. MST is used to improve the transmission routing mechanism between the cluster heads so that only one CH can send collected data directly to the sink in every round. In [13], Minimum Spanning Multi-Tier Protocol (MSMTP) have been proposed based on minimum spanning tree routing strategy and tier formation of sensor nodes. Multi-hop data transmission connection is established among nodes in the same cluster for constructing a minimum spanning tree structure involve all nodes of homogeneous WSNs, and then the sensor node with the highest residual energy among highest rank tier will transmit an aggregated data to the sink. An enhanced MSMTP has been proposed for heterogeneous WSNs in [14]. The re- sults of simulation have proved that this suggested protocol nearby 2x better than cor- responding homogeneous one. In [15], a novel hybrid optimization algorithm called Bee Algorithm-Simulated An- nealing Weighted Minimal Spanning Tree (BASA-WMST) routing has been proposed. The sensor nodes are divided randomly into the best possible number of self-determin- ing clusters with the optimal route. The shortest paths inside clusters are selected using a weighted minimum spanning tree. The weights in the tree are dynamically changed based on the energy level of each sensor nodes during route selection. An efficient algorithm has been proposed by [16] for selecting suitable positions of rendezvous points (RPs) to construct an efficient mobile sink trajectory in WSNs. The algorithm is based on a virtual path and minimum spanning tree. It is suitable for small- and moderate-size networks with delay-bound applications. The proposed approach in [17] distributes sensor nodes by events into clusters. Min- imum spanning tree routing strategy is deployed for intra-cluster routing. An event- based hierarchical architecture is used to reduce power consumption of sensor nodes by reducing unnecessary data transmissions toward the sink. In each cluster, only leaf iJIM ‒ Vol. 13, No. 1, 2019 55 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink nodes are periodically responsible for detecting any abnormal events. The report on the abnormal event is transmitted to the sink only if the majority of sensors sense the same event. 3 System Model This section describes the network and energy models, which are used for develop- ing the suggested approach. The heterogeneous WSN is divided into several clusters in addition to a mobile environment for the central sink. 3.1 Network Model The network area is consist of a set of sensor nodes that are stationary and deployed randomly into clusters in a rectangular area as shown in Figure 1. Sensor nodes are non- uniform and energy constrained. Fig. 1. Cluster-based heterogeneous WSN The heterogeneity of nodes could be represented by giving two different values in energy. A percentage of sensor nodes are classified as advanced nodes equipped with more energy resources than other normal nodes. All nodes are communicated over sym- metric wireless links. The sensor nodes into clusters transmit their sensed data to the mobile sink through elected cluster heads via a single- or multi-hop transmission. Initially, the mobile sink locates at the centre of the network, and it is aware of all sensors' geographic locations. Then it traverses randomly inside the central perimeter of the network to gather data from neighbouring CHs. We assume that the mobile sink has sufficient storage to buffer collected data with no need to recharge a battery. 56 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 3.2 Energy Model The critical energy dissipation model used in this study had been used in some pre- vious literature such as [4], [18], [19]. Figure 2 shows the main components of the en- ergy model. Fig. 2. The energy dissipation model This radio model assumes that energy dissipated for transmitting or receiving data is symmetric. Losses of both Friss free space 𝜀𝜀"# and multi-path 𝜀𝜀$% depend on the trans- mitter-amplifier model used, and the particular distance d between sender and receiver. For simplicity, assume the distance between the sensor node and its CH or sink is less than 𝑑𝑑'. Therefore, to transmit k-bit length message over distance d, the energy ex- pended ETx by the radio model is: 𝐸𝐸)* = , 𝑘𝑘 .𝐸𝐸0102 + 𝑘𝑘 .𝜀𝜀"#.𝑑𝑑4 , 𝑖𝑖𝑖𝑖 𝑑𝑑 ≤ 𝑑𝑑' 𝑘𝑘 .𝐸𝐸0102 + 𝑘𝑘 .𝜀𝜀$%.𝑑𝑑9 , 𝑖𝑖𝑖𝑖 𝑑𝑑 > 𝑑𝑑' (1) where 𝐸𝐸0102 is the electronic energy dissipated to transmit or receive data. k is the amount of bits sent. As shown in the equation, if 𝑑𝑑 ≤ 𝑑𝑑', a free space channel model is accepted, other- wise, the multi-path channel is used. By equaling the two expression at d = d0, the distance threshold d0 is exressed as 𝑑𝑑' = ;𝜀𝜀"# 𝜀𝜀$%⁄ . To receive a k-bit message the radio expends energy equal to: 𝐸𝐸=> = 𝑘𝑘 · 𝐸𝐸0102 (2) Let assume in a specific area there are n number of nodes are distributed uniformly. If there are C number of clusters that can be formed in a selected area, so the average number of nodes might be distributed in a particular cluster is 𝑛𝑛/𝐶𝐶. The CH dissipates its energy when receiving signals from (𝑛𝑛/𝐶𝐶 − 1) nodes, aggregating sensed data by itself and other nodes in the same cluster, and also when transmitting the aggregated data to the sink. The dissipated energy by CH is equal to: 𝐸𝐸GH = I J G − 1K.𝐸𝐸=L + J G 𝑘𝑘.𝐸𝐸MN + 𝐸𝐸)L (3) where EDA is energy dissipated to aggregate data by CH. If the MS is far from the CH node, and the distance to the MS > 𝑑𝑑', then the energy dissipation of CH follows the multi-path model (𝑑𝑑9 power loss) as shown in Formula 4: iJIM ‒ Vol. 13, No. 1, 2019 57 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 𝐸𝐸GH = I J G − 1K𝑘𝑘 .𝐸𝐸0102 + J G 𝑘𝑘.𝐸𝐸MN + 𝑘𝑘 .𝐸𝐸0102 + 𝑘𝑘 .𝜀𝜀$%.𝑑𝑑OP QR9 (4) On the other hand, if the cluster is close enough to the sink, so the energy dissipated by CH is equal to: 𝐸𝐸GH = I J G − 1K𝑘𝑘 .𝐸𝐸0102 + J G 𝑘𝑘.𝐸𝐸MN + 𝑘𝑘 .𝐸𝐸0102 + 𝑘𝑘 .𝜀𝜀"#.𝑑𝑑OP QR4 (5) Each non-CH node needs to transmit its sensed data to the elected CH node. There- fore, the energy dissipation follows the Friss free-space model (𝑑𝑑4 power loss), as long as the distance between them is small. Formula 5 shows the energy dissipated by non- CH node: 𝐸𝐸JPJSGH = 𝑘𝑘 .𝐸𝐸0102 + 𝑘𝑘 .𝜀𝜀"#.𝑑𝑑OPGH4 (6) The energy dissipated in every cluster per round is approximately equal to: 𝐸𝐸21T#O0U ≈ 𝐸𝐸GH + J G .𝐸𝐸JPJSGH (7) Finally, The total energy dissipated in the entire network is equal to: 𝐸𝐸OPOW1 = 𝑘𝑘 .I2𝑛𝑛 .𝐸𝐸0102 + 𝑛𝑛 .𝐸𝐸MN + 𝜀𝜀"# .(𝐶𝐶 .𝑑𝑑OP QR4 + 𝑛𝑛 .𝑑𝑑OP GH4 )K (8) 4 Approach Design The integrated Cluster-based Virtual Backbone (CVB) approach is a shortest span- ning tree routing algorithm uses an MS as a root and all elected CHs in clusters as leaves for the constructed tree. All data gathered by the CHs are transmitted to the root along the backbone of the shortest spanning tree generated using Dijkstra algorithm. CVB is a multi-level cluster-based routing algorithm. It has three phases, which are the Initial Phase, Virtual Backbone Construction Phase, and Data Transmission Phase. 4.1 Initial Phase Like [4], the operation of the CVB approach is divided into rounds. In every round, nodes make autonomous decisions to select CH without any centralized control. A clus- ter head node consumes much more energy than other non-cluster head nodes. In such type of networks to balance energy consumption, each node takes its turn as a cluster head periodically. In every round, each sensor node elects itself to be a CH according to a priori probability Pi [4]. Generally, the number of chosen CHs in the current round is selected according to the following expression: 𝐶𝐶 = ∑ 𝑃𝑃[(𝑡𝑡).1 J []^ (9) Each node might become a CH at round r with probability, 58 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 𝑃𝑃[ = , G JSG.(U $P_ J G⁄ ) , 𝑖𝑖𝑖𝑖 𝑖𝑖 ∈ 𝐺𝐺 0 ,𝑜𝑜𝑡𝑡ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑖𝑖𝑒𝑒𝑒𝑒 (10) where G is the set of non-elected nodes in the last ((𝑒𝑒 𝑚𝑚𝑜𝑜𝑑𝑑 𝑛𝑛 𝐶𝐶⁄ )) rounds. In the suggested heterogeneous sensor networks like in [18], there are m percentage advanced nodes with extra energy α more than other normal nodes. Let us consider the optimal probability of the node to become a CH is: 𝑝𝑝P%O = 𝐶𝐶 𝑛𝑛⁄ . So, the weighed probabilities for normal and advanced nodes are, respectively: 𝑃𝑃JPU = klmn ^op.$ (11) 𝑃𝑃W_q = klmn ^op.$ .(1 + 𝛼𝛼) (12) When we add weighted probabilities for normal and advanced nodes, the probability equation for normal nodes is expressed as: 𝑃𝑃[ = , kslt ^Skslt.(U $P_ ^ kslt⁄ ) , 𝑖𝑖𝑖𝑖 𝑖𝑖 ∈ 𝐺𝐺 0 ,𝑜𝑜𝑡𝑡ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑖𝑖𝑒𝑒𝑒𝑒 (13) Thus, for advanced nodes, 𝑃𝑃[ = , kuvw ^Skuvw.(U $P_ ^ kuvw⁄ ) , 𝑖𝑖𝑖𝑖 𝑖𝑖 ∈ 𝐺𝐺 0 ,𝑜𝑜𝑡𝑡ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑖𝑖𝑒𝑒𝑒𝑒 (14) Figure 3 shows procedures of CH-node selection in the suggested approach. After CHs are elected, they broadcast an advertisement message to the MS and any other node within their radio range. This advertisement message contains its ID, resid- ual energy, and distance to MS. Non-elected nodes start searching the closest CH to join within clusters according to the signal strength of all available CHs based on received advertisement message. After that, each sensor sends a join message to own cluster head to form cluster where they are located. The cluster head sets up a TDMA schedule to assign time slots to all mem- bers of the cluster. A clustering infrastructure in WSNs enables nodes to transmit their data within the cluster locally. To avoid any inter-cluster interference or collision, sensor nodes use CSMA-based MAC protocol to access a channel before transmitting their sensed data to the cluster head. Figure 4 shows the pseudocode of Clustering procedures in the sug- gested approach. According to experimental results of common cluster-based algorithms such as LEACH, and SEP, there is no guarantee to elect at least one cluster head every round during the last rounds of the operation. The absence of a CH in some rounds might cause unreliability and prevents sensor nodes from providing feedback about their environment to the sink. iJIM ‒ Vol. 13, No. 1, 2019 59 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink Fig. 3. Pseudocode of a CH-Selection procedures Fig. 4. Pseudocode of a Clustering procedures 60 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 4.2 CVB Construction Phase CVB approach uses a tree structure to construct a virtual backbone for increasing the efficiency of energy. The multi-hop relaying between cluster heads to the mobile sink is a kind of multi- hop communication based on constructing a connected spanning tree. The mobile sink uses information sent in advance by CHs to construct a backbone from itself to all elected CHs at that round. In case of absence CHs in any round, the CVB approach resolves the unreliability problem by constructing a special virtual backbone between the mobile sink and all existing nodes (alive-nodes) in the network. Fig. 5. Pseudocode of a CVB procedures iJIM ‒ Vol. 13, No. 1, 2019 61 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink The integrated CVB approach consists of three main lists: dis_SPT, visited, and par- ent lists. dis_SPT includes the shortest paths from MS to all CHs in the network, all covered nodes labelled in the visited list, and the best parent of any CH-node is stored into parent list. Initially, the MS as root is covered and labelled in the visited list, while all CHs are not discovered yet and labelled as infinity in the dis_SPT list. According to information collected in the previous phase, the closest CH to MS with the least distance is labelled in the visited list and then added to the dis_SPT_list. Consequently, step-by-step the shortest possible paths are found, and labels in the lists are changed based on the chosen node until covering all CHs at current round. The shortest paths always are selected from source (MS) to the covered CH-node. The construction of spanning tree is completed after covering all CH-nodes in the net- work. CVB construction procedures have been shown in Figure 5. 4.3 Data Transmission Phase Once the virtual backbone has been constructed, and the TDMA schedule is set, the data transmission phase starts. In this phase, CHs must be in standby mode and keep own receivers turned on to be able to receive data at any time. A CH-node receives packets from sensor nodes within the same cluster during their allocated transmission time. It combines the aggregated data and its own sensed data into a single outgoing packet, and then transmit it to the next CH (its parent) over the constructed virtual backbone. To overcome overload and congestion problems in the network, the CH-parent stores the received packet temporary and then encapsulate it with other aggregated data into a single message for sending it to its parent, and so forth until delivering the MS. 5 Performance Analysis The performance of the suggested CVB approach is evaluated through comprehen- sive simulation. Primary measures used to evaluate the performance of the proposed approach are described in Table 1. Table 1. Performance Evaluation Measures Measure Description Network lifetime The period from the start of operation until the death of the last sensor node. Stability period The time interval from the beginning of operation until the failure of the first sensor node in the network. alive/round This measure reflects the number of alive-nodes per round. Residual Energy The amount of sensor energy remained at a particular round. 62 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 5.1 Simulation Environment The MATLAB software was used to evaluate the performance of the proposed CVB approach and compare it with the most common cluster-based hierarchical protocols, LEACH and SEP protocols. On the other hand, to evaluate multi-hop communication provided through the span- ning tree, we compared CVB with SEP protocol in the multi-hop scenario. In the simulation environment, we have distributed 100 sensor nodes randomly over a 100×100 m2 network area. Sensor nodes are heterogeneous, 20% of deployed nodes are advanced and equipped with 300% more energy than rest normal nodes (i.e., m=0.2 and α=3). Table 2 lists the experimental parameters used in the simulation environment. Table 2. Parameters List Parameter Value Optimal election probability (Popt) 0.1 Initial Energy of normal node (E0) 0.5 J Electronic energy (Eelec) 50 nJ/bit Data aggregation energy (EDA) 5 nJ/bit free space coefficient (εfs) 10 pJ/bit/m2 multi-path coefficient (εmp) 0.0013 pJ/bit/m4 Packet size (k) 4000 bits Number of rounds 10000 Initially, the mobile sink is located in the centre. Since the second round, it moves randomly within the central perimeter of the network area. Therefore, the maximum distance between the farthest nodes to the mobile sink is approximately 75m. All compared protocols, LEACH, SEP, and Multi-hop-SEP are implemented in a heterogeneous mode with sink mobility environment. We assume that the communica- tion between nodes is symmetric. Furthermore, the consumed energy for transmitting or receiving data are almost the same. 5.2 Evaluation and Discussion According to empirical results in this simulation, the lifetime of the tested network has increased significantly by CVB in comparison with other protocols as shown in Figure 6. First, we have compared CVB approach to LEACH and SEP protocols. Figure 7 shows the number of alive sensor-nodes during network operation. CVB is approxi- mately stable in the period from 2000-5000 rounds, while other protocols are going down. Furthermore, Figure 7 shows how the number of normal nodes decreases rapidly in a short time compared to the advanced nodes. iJIM ‒ Vol. 13, No. 1, 2019 63 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink Fig. 6. Network lifetime Fig. 7. The number of alive nodes per round In addition, we have chosen to compare between LEACH and suggested approach as both based on the same probabilistic decision. However, the lifetime of normal nodes in the CVB approach is longer than in LEACH as shown in Figure 8. Figure 9 illustrates the significant variation between advanced nodes of the three tested protocols. The lifetime of advanced nodes in the CVB is increased approximately 40% more than SEP and 15% longer than LEACH. 64 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink Fig. 8. CVB vs LEACH Fig. 9. A lifetime of advanced nodes For testing the behaviour of constructed spanning tree, we implemented the SEP protocol with multi-hop transmission mode. Figure 10 shows the lifetime of the CVB compared to Multi-hop SEP. AS evident in both protocols, the normal nodes are sharply die in a short time. For decreasing the energy consumption of normal nodes, the suggested approach improves iJIM ‒ Vol. 13, No. 1, 2019 65 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink the behaviour of normal nods by tracking their status. If the residual energy of a node is less than half, so it will not be elected as a cluster head anymore. This decision in- creases the lifetime of normal nodes but it effects on the overall lifetime of the network as shown in Figure 11. Fig. 10. CVB vs. Multi-hop SEP Fig. 11. The enhanced CVB 66 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink Figure 12 and Figure 13 confirm that the energy consumption of the CVB approach is less than LEACH and SEP, even when we add the extra cost of constructing the backbone-spanning tree. Fig. 12. Residual energy of normal nodes Fig. 13. Residual energy of advanced nodes iJIM ‒ Vol. 13, No. 1, 2019 67 Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink 6 Conclusion One of the primary and critical tasks in wireless sensor networks is to provide effi- cient communication infrastructure. Virtual backbones have been proposed as an effi- cient mechanism for minimal energy consumption, and offer energy-efficient transmis- sion based on multi-hop routing in heterogeneous wireless sensor networks. The suggested approach combined between characteristics of hierarchical cluster- based routing protocols and spanning tree algorithm. The integrated Cluster-based Vir- tual Backbone (CVB) approach is a cluster-based routing algorithm used Dijkstra algo- rithm to build a shortest spanning tree from MS as a root to all elected CHs in WSN. The proposed approach constructs a connected backbone network that would be resili- ent to sink mobility in WSN. The CVB consists of three phases, Initial Phase, Virtual Backbone Construction Phase and Data Transmission Phase. The simulation results confirm that the proposed approach increases the lifetime of the network and decreases energy consumption compared to LEACH and SEP protocols. 7 Acknowledgement The authors would like to acknowledge the financial support of this work from the Deanship of Scientific Research (SRD), Qassim University, according to the agreement of the funded project No. SRD-1784 in 2016, Qassim, Kingdom of Saudi Arabia. 8 References [1] Sabri, A., and Al-Shqeerat, K. (2014). Hierarchical Cluster-Based Routing Protocols for Wireless Sensor Networks – A Survey. International Journal of Computer Science Issues, 11(1): 93-105. [2] Rao, J., and Biswas, S. (2012). Analyzing multi-hop routing feasibility for sensor data har- vesting using mobile sinks. J. Parall. Distr. Comput., 72: 764–777. https://doi.org/10.1016/j. jpdc.2012.02.017 [3] Younis, O., Fahmy, and S. HEED. (2004). A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. Mob. Comput., 3: 366–379. [4] Heinzelman, W., Chandrakasan A., and Balakrishnan H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications. 1(4): 660–670. https://doi.org/10.1109/TWC.2002.804190 [5] Lian, J., Naik, K., and Agnew, G.B. (2006). Data capacity improvement of wireless sensor networks using non-uniform sensor distribution. Int. J. Distrib. Sensor Network, 2:121–145. https://doi.org/10.1080/15501320500201276 [6] Deng, S., Li, J., and Shen, L. (2011). Mobility-based clustering protocol for wireless sensor networks with mobile nodes. I. Eng. Technology. 1: 39–47. [7] Sheng, Y., Baoxian, Z., Cheng, L., and Hussein, T. (2014). Mouftah. Routing Protocols for Wireless Sensor Networks with Mobile Sinks: A Survey. IEEE Communications Magazine. 150–157. [8] Oh, S., Lee, E., Park, S. Jung, J., and Kim, S.H. (2010). Communication Scheme to Support Sink Mobility in Multi-Hop Clustered Wireless Sensor Networks. In Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications 68 http://www.i-jim.org Paper—An Integrated Approach for Constructing Cluster-based Virtual Backbone with Mobile Sink (AINA 2010), Perth, WA, Australia, 20–23 April. 866–872. https://doi.org/10.1109/AINA.2010.103 [9] Bosheng Z., Marshall, A., and Lee, T-H. (2005). An energy-aware virtual backbone tree for wireless sensor networks. [10] IEEE Global Telecommunications Conference, (GLOBECOM’05). 1: 162-167. https://doi.org/10.1109/GLOCOM.2005.1577373 [11] Shin, I., Kim, M., Mutka, M., Choo, H, and Lee T. (2009). MCBT: Multi-Hop Cluster Based Stable Backbone Trees for Data Collection and Dissemination in WSNs. Sensors. 9: 6028- 6045. https://doi.org/10.3390/s90806028 [12] Kim, J., and Lee, J. (2012). ViTAMin: A Virtual Backbone Tree Algorithm for Minimal Energy Consumption in Wireless Sensor Network Routing. In Proc. ICOIN 2012, pp. 144- 149. https://doi.org/10.1109/ICOIN.2012.6164366 [13] Wang, W., Wang, B., Liu. Z., Guo, L., and Wei, X. (2011). A Cluster-based and Tree-based Power Efficient Data Collection and Aggregation Protocol for Wireless Sensor Networks. Information Technology Journal. 10 (3): 557-564. https://doi.org/10.3923/itj.2011.557.564 [14] Gaurav, B., and Gulista, K. (2011). Energy- Efficient Routing Protocol for Homogeneous Wireless Sensor Networks. International Journal on Cloud Computing: Services and Archi- tecture (IJCCSA). 1(1): 12-20. [15] Gaurav, B. (2013). Minimum Spanning Tree Based Protocol for Heterogeneous Wireless Sensor Networks. Journal on Wireless Communication Networks. 1 l(4): 12-23. [16] Matheswaran, S., and Muthusamy, M. (2014). A Hybrid Optimized Weighted Minimum Spanning Tree for the Shortest Intrapath Selection in Wireless Sensor Network. Mathemat- ical Problems in Engineering, 2014.https://doi.org/10.1155/2014/713427 [17] Nitesh, K., Azharuddin, M,, and Jana, P. (2017). Minimum spanning tree-based delay aware mobile sink traversal in wireless sensor networks. Int J Commun System. 30:e3270. https://doi.org/10.1002/dac.3270 [18] Yang, K-T, Lai, W.-K., Li S.-M., and Lin Y.-C. (2014). Event-Based Clustering Architec- ture for Power Efficiency in Wireless Sensor Networks. International Journal of Distributed Sensor Networks. https://doi.org/10.1155/2014/612590 [19] Smaragdakis, G., Matta, I., and Bestavros, A. (2004). SEP: A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks. In Proceedings of the International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004), Bos- ton, MT, USA, 22 August. [20] Wang J., Zhang, Z., Xia, F., Yuan, W. and Lee, S. (2013). An Energy Efficient Stable Elec- tion-Based Routing Algorithm for Wireless Sensor Networks. Sensors. 13: 14301-14320. https://doi.org/10.3390/s131114301 9 Author Khalil H. Al-Shqeerat is an associate professor in the Department of Computer Sci- ence at Qassim University – Saudi Arabia. He obtained his Ph.D. in Computing Sys- tems and Networks from the National Technical University - Ukraine, in 2004. Since 2004 he worked also at Zarqa Private University, Hashemite University, and Applied Science University in Jordan. From 2009 to 2011, he has been a head of the Computer Networks Systems Department at Applied Sciences University. His research interests are in Wireless Sensor Networks, Security, Cloud Computing, Mobile Agent, and In- ternet of Things. Article submitted 16 October 2018. Resubmitted 13 November 2018. Final acceptance 16 November 2018. Final version published as submitted by the author. iJIM ‒ Vol. 13, No. 1, 2019 69