INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL ISSN 1841-9836, e-ISSN 1841-9844, 14(6), 691-709, December 2019. A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN J. Siva Prashanth, S.V. Nandury J. Siva Prashanth* Academy of Scientific and Innovative Res., CSIR-IICT Campus, CSIR-Indian Institute of Chemical Technology, Hyderabad, India *Corresponding author: sivaprashanth.j@gmail.com Satyanarayana V. Nandury Academy of Scientific and Innovative Res., CSIR-IICT Campus, CSIR-Indian Institute of Chemical Technology, Hyderabad, India. nvs@iict.res.in Abstract: Envoy Node Identification (ENI) and Halting Location Identifier (HLI) algorithms have been developed to reduce the travel time of Mobile Element (ME) by determining Optimal Path(OP) in Wireless Sensor Networks. Data generated by cluster members will be aggregated at the Cluster Head (CH) identified by ENI for onward transmission to the ME and it likewise decides an ideal path for ME by interfacing all CH/Envoy Nodes (EN). In order to reduce the tour length (TL) further HLI determines finest number of Halting Locations that cover all ENs by taking transmission range of CH/ENs into consideration. Impact of ENI and HLI on energy consumption and travel time of ME have been examined through simulations. Keywords: Envoy Nodes, Halting Locations, travel time, latency. 1 Introduction Wireless Sensor Networks(WSN) are established by thousands of sensors distributed spa- tially over a specified geographical region for monitoring the changes in the environment. WSNs have wide range of applications like, health care monitoring, earth sciences, environmental sci- ences, military applications to detect intrusion of enemies disaster,tracking vehicular movement, etc. Sensor Nodes(SNs) are typically small electronic devices operated by battery with finite amount of energy. Each SN senses the environment and gathers the information about physical changes in the environment.Data generated by SN either periodically or continuously have to be submitted to the centralized processing unit called stationary Base Station (BS). Contingent upon nature of the application, information detected by WSNs send either straightforwardly to a stationary BS or Mobile Element (ME). Usually BS location is fixed. In case if BS is located within the transmission range of a SN, then it will directly submit data to the BS. Otherwise, SN will send the data to its nearest neighbor, which will try to identify the shortest path and relay the data to the BS. There are few challenges associated with this traditional mechanism. Sometimes BS may be located far away from the area of interest, in such scenario SNs will not be able to communicate with the BS, apart from this, in large WSN considerable amount of energy will be spent for transmitting and receiving messages, this leads to high energy consumption and increased network traffic. Copyright ©2019 CC BY-NC 692 J. Siva Prashanth, S.V. Nandury SNs nearest to BS have to allocate time slots for traffic coming from neighbor SNs, this result in traffic congestion. These nodes devour compared to other nodes. Such situation may prompt WSN’s breakdown, as no information would reach BS if these nodes channel out the whole of their battery life. The Above mentioned challenges can be addressed by employing a ME that travels along WSN space to gather data from SNs. The data gathered by the ME, is then submitted to BS [19]. How ever, it increases network latency. Latency can be minimized by identifying Envoy Nodes (EN), where EN is a node that ME must visit, in order to collect data. ME need not to visit exact geographical location of a EN, instead it can collect the data from any location within the transmission range of EN. Inspired by this ME’s tour can be shortened further by identifying a set of locations in such a way that, ME will be able to collect data from all ENs by visiting these locations, these locations are referred to as Halting Locations (HL). In literature various approaches makes use of heuristic approaches like Travelling Salesmen Problem (TSP) and Genetic Algorithms (GA) for defining ME’s optimal tour [7,12,20]. In our previous work we have adopted a clustering method to minimize the energy con- sumption and decrease latency where every SN in a cluster is inside the transmission range of its Cluster Head (CH) [22]. As an extension to the previous work we try to investigate the effect of ME’s TL on energy consumption. In this approach, Envoy Node Identification (ENI) algorithm has been developed to identify the number of ENs to be visited by the ME. ME’s tour consists of visit to all ENs. Optimal path(OP) that covers all ENs in WSN is identified using traditional TSP solver. Tour that has been given by TSP solver can further be reduced by visiting the HLs identified by Halting Location Identifier (HLI) algorithm. Adequacy of ENI and HLI have been evaluated in terms of optimizing the energy consumption and travel time of ME through simulation. An examination of simulation result shows that ENI, HLI outflank the COM and CSS. Overview of research works related to clustering, energy issues and TL-optimization of ME discussed in Section 2. Section 3 presents an overview of proposed optimization approach. ENI and HLI algorithms described in Section 4. Section 5 showcases performance results through simulations carried out. 2 Related work 2.1 Minimizing the TL of mobile element The problem of reducing TL of ME is addressed in [35]. First it carries out the cluster formation process as per [6], then the deployment region is partitioned into virtual grids and intersection points are identified. CHs have to choose one of these intersection points, so that ME can collect data from CHs by visiting these intersection points. Order of nodes to be visited is identified by a TSP solver. A convex hull based method for reducing latency by considering amount of data to be collected is proposed in [36]. In this method a convex hull that covers all nodes is constructed. This process is applied progressively by eliminating nodes on previous layer of convex hull. This process is repeated until no nodes are left for further processing. All possible permutations for visiting nodes in layer - n and n-1are explored in order to identify an OP. This process is applied progressively until all the layers are covered. Optimal TL of ME is obtained by adjusting speed of ME. Two different approaches are presented in [32, 34] for optimizing TL. The first approach enables ME to move unreservedly over the network deployment area, TL optimization depends on the requirement that information from SNs should reach BS in a given deadline. Second A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 693 approach pre-characterizes ME’s path and TL is optimization will be achieved by identifying HLs along the pre-characterized path. Optimal disc coverage is a technique which gives Centre and radius of the optimal disc that covers given set of points. In [11], an attempt made to reduce ME’s TL by using COM and CSS algorithms. An OP connecting all nodes has been identified by employing a TSP. In this approach the location to be visited by ME is referred as collection site. Optimal disc coverage technique [31] was employed by COM for identifying collection sites that must be included in ME’s. Location of two nodes will be given as input to decisional Welzl’s algorithm, if Welzl’s radius is less than or equal to transmission range then the two nodes will be replaced by Welzl’s centre in ME’s tour. CSS identifies the common intersection areas and establishes rendezvous points(RP) in it. The optimality of TL in these methodologies is restricted by the TSP solver. ENI and HLI made an attempt to overcome this limitation. 2.2 Clustering In WSN, when clustering approaches are adopted,members of cluster submit the data to its CHs and CHs submits the data to the BS , in such networks, the CHs near the BS usually tend to become the conduit point for bulk data transmissions between the BS and far away clusters. As a consequence, the energy of CHs nearer to the BS may drain out quickly. To maximize the lifetime of CHs nearer to BS variable size clustering has been proposed in [17,19]. In both the approaches size of the clusters is defined by the distance of CH from BS. Since clusters nearer to BS will be of smaller size, the intra cluster communication and energy consumption for cluster routines is minimized so that the residual energy of CH can be utilized for relaying the incoming data to the BS. Depending on the network topology it may happen that, some clusters accommodate more number of members. When a cluster has more number of cluster members, it leads to high energy consumption at cluster head and cluster head may drain out its energy very early. A clustering algorithm for addressing this problem is given in [27], size of the cluster and degree of a node are the two parameters that played key role in minimizing energy consumption. A clustering algorithm based on common intersection area of SNs is proposed in [7], it groups the nodes having common intersection are in a cluster. Order of to be visited by ME is obtained by using GA. A genetic algorithm based cluster was proposed for reducing latency in [12]. Initially way points to be visited by ME are identified, then using weighing scheme nodes select one of the waypoint. These way points are optimized using genetic algorithms for mini- mizing ME’s tour. An approach for determining optimized path from source to destination was proposed in [8]. As size of the cluster increases CH has to relay more number of packets and it leads to delayed transmission of data. This problem is address by exploiting nodes in common intersection area of clusters [9]. In this approach when waiting time of a packet at CH is more than the pre- defined threshold value, then node submits its data to neighbor CH through nodes in common intersection area. This phenomenon reduces packet loss and minimizes latency. A protocol for minimizing the energy consumption by making use of beacon signal of ME is proposed in [23]. In this protocol a SN senses the environment periodically and goes to the sleep state, when a SN receive a Long Range beacon Signal from ME, it enters into active state. Node transmits data to ME when it receives Short Range beacon Signal and enters into sleep state. Apart from latency and energy consumption fault tolerance is another issue associated with WSN. Even if the node detects fault and decides to reject the data, it takes considerable amount of time and energy. This problem is addressed by introducing Composite Interference Model 694 J. Siva Prashanth, S.V. Nandury (CIM) in [4]. To determine Interference Fault-free Transmission (IFFT) schedule for all active links, a new approach Time Division Multiple Frequency (TDMF) is defined. Based on CIM and TDMF an algorithm for maximizing network throughput, Composite Interference-based Transmission Scheduling (CITS) is developed. 2.3 Energy issues LEACH is one of the popular algorithm which has addressed the energy issues by adopting clustering mechanism [13]. An Energy Efficient Optimal Chain Protocol (EEOC) is proposed in [1]. EEOC has shown better performance than best known approaches in terms of first node die and last node alive. For extending the network lifetime and reducing data redundancy, a novel approach which is combination of chain based data transmission and clustering is proposed in [25]. A new clustering approach for achieving energy efficiency and reliability with the help of backup nodes is proposed in [26]. An attempt to achieve energy efficiency in delay sensitive applications is made in [24]. Raja et.al. tried to minimize the energy consumption by introducing multicasting mecha- nism and unequal size clustering [29]. Energy efficient and reliable routing is achieved using neural networks in [30]. Adoptive sectoring mechanism is used to prolong the network lifetime and reliable routing in [5]. A data collection strategy based on software defined network for enhancing network lifetime is proposed in [18]. A hybrid model of tree and cluster based approach is adopted for addressing hotspot issues, traffic congestion and energy issues in [15,16,21]. Shahinaz M. Al-Tabbakh adopted a tree based heuristic aggregation mechanism to enhance the network lifetime. A protocol for network lifetime improvisation is proposed in [10], it intro- duced a collection tree protocol to maintain dynamic routing table along with link state quality indicator. Considerable amount of energy will be spent in WSN for data aggregation, this problem is addressed by using compressed sensing in [3]. 3 Clustering approach to identify Envoy Nodes Assuming a set of SNs S=s0, s1, ..., sn have been deployed in an area where a set of phenomena are being monitored. Duty of ME is to collect data from all SNs in S. It minimizes multi hop communication and energy consumption, but it leads to increase in latency as ME needs to visit all nodes. Latency can be reduced by identifying a set of Envoy Nodes SEN=en0,en1... enn such that the sensed data of all nodes in the deployment region can be collected by ME by visiting all Envoy Nodes in SEN.The goal is to minimize the number of Envoy Nodes as many as possible. In this paper we propose Cluster mechanism to further reduce the number of Envoy Nodes. 3.1 Cluster head selection Geographical region that has to be monitored by WSN is divided into virtual square grids of side equivalent to 2 * Tr. A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 695 Partitioning process will be started from centre of the optimal disc given by Welzl’s algorithm [31]. Making use of the following equation, assuming d0,d1 as the distance from node s0,s1 ,... to centre ceni of each grid Gi select a cluster head chi. Chi = sj |dj is min {d0, d1...} (1) From (Eq.1) the node sj that is nearer to ceni will be chi for the grid Gi. Since length of each side of grid is 2*Tr, locating CH nearby centre of the grid guaranties single hop communication with maximum number of nodes within the grid, also maximizes node coverage within the grid. 3.2 Cluster formation After obtaining set of cluster heads CLH=ch0,ch1, ..., the nodes that are within one hop distance from a cluster head chi are made to join the cluster CLi. There is possibility that some CHs are closely located, it may lead to the situation that a CH becomes the member of other cluster. In order to avoid such situation cluster heads have to be excluded from cluster formation process as mentioned in (Eq. 2). S′ = S −CLH (2) A node sj in S′ joins the cluster CLi if it belongs to the grid Gi and within the transmission range of CH chi. Sj�CLi∀sj�Gi if dist(sj,chi) < Tr (3) CH collects information from fellow cluster members and aggregates, this aggregated in- formation will be transmitted to ME. Each node in CLi submits it’s data to chi. A node can join only one cluster. As soon as node joins a cluster it will be excluded from further clustering process . However, there is a possibility that few nodes may not fall into any cluster because of the reason that they are not within the transmission range of any of the cluster heads. 3.3 Envoy Node Identification A node sj in S is either a cluster member or a CH or a left over node. If sj joins one of the clusters then it must belong to the set CL0, CL1 ... U CLm it’s data is represented by the cluster head chi and chi belongs to cluster head set CLH. The edge or corner SNs which have not joined any of clusters form a set of left over nodes L are identified as per the equation given below: L = S −{CLH U {CL0 U CL1... CLm}} (4) In addition to the cluster heads, set of envoy nodes SEN must also include the leftover nodes for ME’s tour in order to ensure all nodes are visited. SEN = CLH U L (5) ME can collect data from cluster members of CLi by visiting it’s cluster head chi i.e. ME covers all nodes in Li by visiting chi. This altogether diminishes the quantity of ENs to be visited by the ME prompting significant reduction in the TL. An optimised path for ME’s tour covering all ENs in SEN is determined by using the best known TSP solver Lin-Kernighan [14]. 696 J. Siva Prashanth, S.V. Nandury Algorithm 1 Envey Node Identification - ENI Input: 1: • Deployment Area WSN = s* s • Set of sensor nodes S= { s0, s1, ..., sn, } where si represents (xi, yi) the coordinate of sensor • Set of cluster heads CHS ← { ch0, ch1, ..., chm } • Transmission range Tr Output: 2: • CLH - Set of Cluster heads • SEN - Set of Envoy Nodes Start: 3: (C,R) ← Welzl(n,SNS) . Determine Center C and radius R of Welzls circle 4: CLH ←{φ} 5: Partition WSN Area into square grids Gi of side 2 * Tr with C as the Centre to the extent possible 6: Determine the grid center of each grid in GP where GP ← {G0, G1, ..., Gm } 7: 8: for i = 0 to m do . where m i the number of grids 9: Identify sj closest to each Gi in Welzls circle 10: CLH ← CLH ∪sj 11: end for 12: S′ ← CLH ∪sj 13: for j = 0 to n do 14: CLi ←{φ} 15: for i = 0 to n do 16: if dist(si,chj) ≤ Tr then 17: CLj ← CLj ∪si 18: end ifEnd if 19: end for 20: S′ ← S′ −CLj 21: end for 22: End for 23: L ← CLH ∪S′ 24: SEN ← Lin - Kernighan(L) A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 697 Theorem 1. Set of Envoy Nodes SEN=en0,en1, ..., enk covers all nodes deployed in the net- work. Proof: Let S be a set of all nodes in the network. Suppose sj be a node in the network i.e sj � S Case i: sj is a cluster head. Since sj is a CH it will included in CLH, from (5) SEN covers all CHs, it implies sj is covered by SEN. Case ii: sj is a member of cluster cli in the network. Since sj � cli, it is represented by its cluster head chi, and from (6) all cluster heads are covered by SEN, it implies that node sj is covered by SEN. Case iii: sj is a left over node in the network. Since sj is a left over node it must belong to L, from (5)SEN covers all nodes in L, it implies node sj is covered by SEN. Let sj does not belong to S. If sj 6∈ S it implies it does not belong to the network. Hence it need not be covered by SEN. From above it can be concluded that SEN covers all nodes in the network. 2 4 Halting location based path optimization To further shorten the ME’s path, Halting Locations are identified wherever possible, for each Envoy Nodes in SEN. The HLI optimizes the path determined by ENI by employing the HLIT technique introduced in this paper. TL of ME can be minimized by locating HLs along the tour given by TSP solver. Few ENs may have common intersection area or region, then ME can collect data by identifying a HL in the overlapping region. Set of Halting Locations SHL= hl0,hl1..hlk along ME’s tour that covers all Envoy Nodes in SEN are established by HLI using HLIT technique. Each hli covers one or more Envoy Nodes in SEN. For identifying the HLs, we developed HL Identification Technique (HLIT), it identifies an optimal HLs to substitute some of the ENs along ME’s path. HLIT exploits the fact that the ENs can transmit their information to ME even if they are at a distance Tr from the ME. HLIT enables ME to collect the data of EN form a distance of Tr from the EN where Tr is transmission range of EN .HLIT identifies optimal HLs covering all ENs. j=k∑ j=1 |hlj| = i=m∑ i=1 |eni| = |S| (6) |hlj| denotes number of SNs covered by Halting Location hlj. |eni| denotes number of SNs covered by eni |S| denotes total number of SNs. m and k represents total number of ENs and HLs respectively. Fig.1. is an illustrative example of our approach. Our objective is to achieve (6) with opti- mal values of k and m for obtaining optimal TL of ME. Contingent upon the separations between the ENs, HLIT decides HL dependent on three criteria depicted underneath: Criterion 1: Overlapped Unit disc regions of Envoy Nodes. Let us consider a scenario where the node deployment and ME’s tour is as shown in Fig.1.(a).In Fig.1.(b) it can be observed that distance between EN1 , EN2 is < 2*Tr i.e. there is an overlap region between EN1 and EN2 , any location within the overlap region will be at a distance less than Tr from both the ENs, hence ME can collect data from both ENs by visiting any location within the overlap region. 698 J. Siva Prashanth, S.V. Nandury Figure 1: Illustrative example of Halting Location Identification Technique.(a),(c),(e ) Actual tour of ME (b) HLIT based OP for Criterion 1. (d) Optimized HLIT based OP for Criterion 2. (f) HLIT based OP for Criterion 3 Figure 2: (a) Node Deployment (b) Tour given by TSP solver (c) Tour identified by HLI A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 699 HLIT determines a HL in the overlapping region of EN1 and EN2 , such that the distances from HL and either of two points is ≤ Tr. HLIT modifies SHL as per the equation given below: SHL = SEN −{eni+2,eni+1}∪{hli+1 if 3 eni+1}|dist(eni+2,eni+1) ≤ 2 ∗Tr (7) Halting Location hli+1 in (7) is a location in the common intersection area nearest to ME’s path from which ME will be able to receive data from both eni+1, eni+2. The ENs eni+1, eni+2 are replaced by hli+1 in SHL Since ME covers both eni+1, eni+2 by visiting hli+1. Criterion 2: eni+1 is at a distance ≤ Tr from the path eni to eni+2 Let us consider other node deployment scenario as shown in fig 1.(b). While ME is moving from its starting point to EN2, the path is intersecting with the unit disc region of EN1, that means distance from EN1 to ME in the intersecting region is ≤ Tr , hence ME can collect data form that EN while it is moving. SHL = SEN −{eni+1}if∃{eni+1 |pre_dist(eni,eni+1,eni+2) ≤ Tr (8) In fig.1(d) EN1 is at a distance ≤ Tr from the path defined from starting point to EN2, hence so ME can receive data from EN1 when it is moving along the path from starting point to EN2. In this case neither ME has to visit the exact location of EN1 nor there is a need of iden- tifying HL for EN1 since ME can collect the data while it is moving, hence HLIT modifies HLI based on this criterion as per (8). Criterion 3: eni+1 is at a distance > Tr from the path eni to eni+2 Let us assume the node deployment scenario as per Fig.1.(e). In this case ENs neither have overlap region nor it is covered by ME’s path as discussed in Criterion 2, then a HL within the unit disc region of EN has to be identified for covering each EN. Following equation determines HL for this scenario: SHL = SEN −eni+1 ∪hli+1 if ∃ eni+1|per_dist(en1,eni+1,eni+2) > Tr (9) Perpendicular distance is the minimum distance from a point to the line, inspired by this as per (9) perpendicular distance from eni+1 to the path from eni to eni+2 will be calculated, if it is more than the transmission range then HLIT determines an HL hli+1 at a distance Tr from eni+1 along the direction perpendicular to path from eni to eni+2 . Fig.1(f) is an illustrative example of this approach. While ME is moving from its starting point, perpendicular distance from EN1 to the path from starting point to EN2 is more than the transmission range, hence HLI based on HLIT identifies a halting location HL1 as shown in fig.1(e), fig.2 shows the impact of our approach on TL, for the node deployment given in fig.2(a) ME’s tour is identified by a TSP solver, fig.2(b) represents ME’s tour. Finally, after applying HLI the tour of ME will be as shown in fig.2(c). Algorithm 3 repre- sents HLIT based HLI algorithm to identify HLs. Lemma 2. If unit disc regions of each Envoy Nodes in SEN={eni,eni+1..enl} with transmission range Tr have common intersection area then Halting Location hlp located in the intersection area covers all the Envoy Nodes in SEN. 700 J. Siva Prashanth, S.V. Nandury Algorithm 2 Envey Node Identification - ENI Input: 1: • Set of Envoy Nodes SEN = { en1, en2, ..., enn } • Transmission range Tr Output: 2: • Set of Halting Locations Start: 3: q=0 4: for i = 0 to n− 2 do 5: k ← i+1 6: if eni and eni+1 have common intersection area then 7: while envoy nodes eni, ..., enk have common intersection are do 8: k ← k+1 9: end while 10: Find envoy nodes hlq within the common intersection area of { eni, ..., enk−1 } which is nearer to path from eni to enk 11: SEN ← SEN- {eni, ..., enk − 1 } ∪ hlq 12: else if t thenhe path from eni to enk + 1 covers enk 13: while the path from eni to enk+1 covers set of Envoy Nodes { eni + 1, ..., enk } do 14: k ← k+1 15: end while 16: SEN ← SEN - { eni + 1, ..., enk − 1 } 17: else 18: hlq ← point-to-point eni + 1, eni + 2, ..., Tr 19: SEN ← SEN - eni+1 ∪ hli+1 20: end if 21: q ← q+1 22: end for 23: SHL ← Lin - Kernighan(SEN) Algorithm 3 Point_at_dist (P1, P2, Tr) Input: 1: • Two points P1 and P2 | Pi ← (xi, yi) • Transmission range Tr Output: 2: • Point P ar a distance Tr from P1 along the line (P1, P2) Start: 3: d= dist (P1, P2) 4: x = x1 + (x2 - x1 ) * ( Tr / d ) 5: y = y1 + ( y2 - y1 ) * ( Tr /d) 6: P= ( x,y) A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 701 Proof: Since hlp is in common intersection area, distance from hlp to any Envoy Nodes in SEN is less than or equal to Tr. Therefore hlp covers all the ENs in SEN and hence Envoy Nodes in SEN can be replaced by hlpin SEN. 2 Lemma 3. The path from eni to eni+2 covers Envoy Nodes eni+1 if the distance from Envoy Nodes to the path is less than or equal to transmission range Tr. Proof: From (7) if distance from a Envoy Nodes eni+1 to the path from eni to eni+2 is less than or equal to Tr mobile element can collect data from the eni+1 in its journey. Therefore path from eni to eni+2 covers eni+1 and hence eni+1 can be eliminated from SEN. 2 Lemma 4. Envoy Node eni+1 is covered by Halting Location hlp if it is neither having common intersection area with any other Envoy Nodes nor it is covered by the path from eni to eni+2 Proof: From (10) HLI establishes a Halting Location hlp at a distance of Tr from eni+1 in a direction perpendicular to the path from eni to eni+2 if eni+1 is neither having common intersection area with any other Envoy Nodes nor it is covered by the path from eni to eni+2. Distance from hlp to eni+1 is equal to Tr. Therefore hlp covers eni+1. 2 Theorem 5. Set of Halting Locations SHL={ hl0,hl1..hlm } covers all the nodes in S={s0, s1, ..., sn } deployed across the network. Proof: Let us assume that eni be a Envoy Node in SEN. Case i: Unit disc region of eni with transmission range Tr as radius has common intersection area with a set of Envoy Nodes SEN. From Lemma 2 Halting Location hlp established by HLI covers all ENs in SEN. It implies SEN covers eni. Case ii: Distance from eni to a point on the path from eni−1 to eni+1 is less than Tr. From Lemma 3 path from eni−1 to eni+1 covers eni. It implies SEN covers eni. Case iii: eni is any EN in SEN, other than the one stated in case i and case ii. From Lemma 4 HLI establishes a Halting Location hlp within transmission range of eni. It implies SEN covers eni.In case i, ii and iii it has proven that SHL covers all ENs in SEN and from theorem 1 SEN covers all nodes in S, hence it can be concluded that SHL covers all nodes in S. 2 Lemma 6. Number of elements in SHL is less than or equal to the number elements in SEN. Proof: Let m be the total number of Envoy Nodes in SEN. Let SEN represents a set of Envoy Nodes having common intersection area and k be the total number of Envoy Nodes in SEN. From Lemma 2 Halting Location hlp established by HLI covers all ENs in SEN, so ENs in SEN can be replaced by in SHL, total number of elements in SEN are m−k . If k = 0 total number of elements in SHL are m. Therefore it can be concluded that, number of elements in SHL is less than or equal to the number elements in SEN. 2 702 J. Siva Prashanth, S.V. Nandury Theorem 7. TL of SHL is less than the TL of SEN. Proof: Let us assume t be the TL to cover all the ENs in SEN. Case i: Let us assume that few of ENs in SEN have common intersection area. From Lemma 2 Halting Locations in SHL established by HLI covers all ENs in SEN. Let us assume t1 be the TL to cover all the HLs in SHL. Number of HLs in SHL is lesser than the number of ENs, hence t1 < t. It implies TL of SHL is less than tour length of SEN. Reduced TL contributes to minimize the travel time of ME. Case ii: Let k number of ENs are not having common intersection area with any of the ENs in SEN. From Lemma 4 HLI establishes Halting Location hlp at a distance equal to Tr, the resultant TL will be less than or equal to t-k ∗ Tr, it implies TL of SHL is less than the TL of SEN. 2 5 Simulations and performance analysis Simulations are carried out to examine the efficiency of proposed algorithms in terms of iden- tifying ENs, minimizing TL and travel time of ME, minimizing latency and energy consumption by varying number of nodes, transmission ranges . This section details about the simulation model and analysis on efficiency of proposed approach. 5.1 Simulation model WSN deployment area of size 500x500 m2 have considered for implementing and evaluating the performance of the proposed algorithms ENI and HLI. Homogeneous WSN environment is adopted, where all SNs nodes are equipped with equal transmission range. In order to evaluate the performance of ENI and HLI for higher node density, number of SNs in deployment region varied from 1000 to 5000. Identification of ENs and HLs have been carried out by ENI and HLI respectively. It is assumed that ME requires halting time HT to collect data from ENs. In the simulations value of HT is considered as 2 sec. For calculating the energy consumption in the network values of two terms Eelec and εamp are taken as 50nJ /bit and 100pJ/ bit/ m2, where Eelec is energy spent for running the electric circuitry, and εamp is energy spent for amplification [13], ETx, Erx represents transmission and receiving energies respectively. TSP solver Lin-Kernighan algorithm is employed for defining ME’s optimal tour to cover given set of ENs or HLs. It is assumed that ME moves with a uniform velocity of 10m/sec. Results represented in each graph is mean of 50 simulations Table 1: Simulation parameters Parameter Value Field size 500x500 m2 Node deployment 1000- 5000 Transmission range Tr 20m, 30m, 40m Speed of ME 10 m/sec Halting time HT 2 sec Eelec 50 nJ/bits εamp 100 pJ/bit/m2 A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 703 5.2 Optimizing halting locations In order to test the performance of ENI in terms of number of locations to be visited by ME, a new term Ratio of Halting Locations to the Total number of Nodes deployed (RHLTN) is introduced. RHLTN is calculated as follows: RHLTN = 100 ∗ NumberofHaltingLocations TotalNumberofNodesDeployed (10) Value of RHLTN is inversely proportional to the efficiency of an algorithm, low value of RHLTN indicates that ME can collect the data of all SNs by visiting very few locations, it means algorithm efficiency is high. We have calculated the RHLTN value of HLI and CSS for different transmission ranges (20, 30 and 40) and total number of nodes varying from 1000 to 5000. The graph is plotted by taking number of nodes on X-axis and RHLTN value on Y-axis. In graphs HLI_20, HLI_30 and HLI_40 indicates the RHLTN values of HLI for transmission ranges 20, 30 and 40 respectively. From the fig.3 it can be predicted that, irrespective of transmission ranges HLI outperforms CSS. When total number of nodes is 5000, RHLTN value of HLI is 20. It means ME needs to visit only 20 percent of the nodes in order to complete its tour for collecting the data, whereas for CSS it has to visit 45-50 percent. This phenomenon will have adverse effect on Travel time of ME and energy consumption in the network. Figure 3: Ratio of halting locations to the total number of nodes Minimizing travel time TL refers to the total distance that has to be covered by ME for visiting a set of EN or HLs.Increase in number of ENs result in increased TL of ME. The TL has an immediate impact on the latency engaged with overhauling a query or a demand from a given SN. In order to obtain the OP covering set of ENs identified by ENI a TSP solver Lin-Kernighan algorithm [14] is employed. After obtaining the order of nodes to be visited, HLI establishes HLs using HLIT technique for minimizing the TL. A HL represents one or more ENs. Travel time of ME depends on number of ENs to be visited, speed of it and time taken for transferring data (halting time of ME) from EN to ME . Assuming di,i+1 is the distance between Halting Locations HLi and HLi+1 ; vi,i+1 is the speed of ME while moving from HLi to HLi+1; and HTi is the halting time of ME at HLi, the 704 J. Siva Prashanth, S.V. Nandury amount of time T required by ME to collect data from all Envoy Nodes is calculated as follows: T = n∑ i=1 di,i+1 vi,i+1 + HTi (11) If ME is moving with uniform speed v with a constant halting time HT then (11) becomes T = ∑n i=1 di,i+1 v + n∗HT (12) In our simulations total travelling time of ME is calculated as per (12). It is assumed that ME is moving with a constant speed of 10 m/sec and halting time at each EN is 2 sec. As ME’s speed and halting time are fixed travelling time depends on number of HLs to be visited. Graphs are plotted between total number of nodes deployed and travelling time as shown in the fig.4, in order to study the efficiency of HLI in terms of travelling time of ME. With the help of simulations it is proven that criterions considered in HLIT resulted in reduced travel time of ME. From the graph it can be concluded that latency of the network can be reduced considerably with HLI. Travelling time of ME is very low for different transmission ranges. Simulation results prove that HLI is more suitable for applications in which data is time critical i.e. data has to reach the base station with in the stipulated time interval otherwise the data becomes obsolete. It can be concluded that HLIT technique adopted for identifying HLs in HLI has shown its impact in reducing the travel time of ME considerably irrespective of transmission ranges and number of nodes deployed. ENI and HLI offer better QOS compared to COM and CSS in terms of travel time and energy consumption. Figure 4: Travel Time . 5.3 Minimizing energy consumption Every SN is equipped with finite amount of energy, this energy will be utilized for mon- itoring the targeted area, transmission and receiving of messages etc. For calculating energy consumption in the network the following equation is borrowed from [28]. ETx = Eelec ∗k + εamp ∗k ∗d2 (13) A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 705 ERx = Eelec ∗k (14) ETotal = ETx + ERx (15) Where (13) gives the energy consumption occurred ETx for transmitting k number of bits over a distance d. Energy consumption for receiving k number of bits ERx is given by (14). Total energy consumption ETotal is given by (15). In the literature it is observed that energy spent to hold the data, till the data is transferred to ME is not taken into consideration. We have tried to identify the energy consumption at each ENs for transferring the data to ME. It is assumed that Amount of time taken by ME to reach halting location i from halting location 1 is Holding time TiHold is the amount of time the Envoy Nodes i has to hold the data. From (11) TiHold can be calculated as follows: TiHold = n∑ i=1 ∑n i=1 di,i+1 v + i∗HT (16) Here TiHold is the time taken by ME to reach HL hli since from the starting point of it’s tour, i represents the index of HL in SHL, dj,j−1 is the distance from hlj to hlj−1.v is the speed of ME. By taking holding time into consideration (13) is modified as follows: Ei = 0.1 ∗Eelec ∗k ∗TiHold + �amp ∗k ∗d2i (17) Total energy consumption in the network is calculated as follow: ETotal = k=n∑ k=1 Ek (18) Figure 5: Ratio of Halting Locations to the Total number of Nodes. Through the simulations we have tried to investigate the energy consumption of the network after applying HLI and compared it with CSS. In fig.5, initially there is not much difference whether it is HLI or CSS, but when total number of nodes is 5000, there is huge difference. We tried to diagnose the reason for this phenomenon, it is observed that travel time of ME is 706 J. Siva Prashanth, S.V. Nandury Figure 6: Ratio of Idle time Energy consumption to the Total Energy consumption . influencing the energy consumption in the network, in order to substantiate this conclusion we have analyzed (17), in (17) all parameters are constants except TiHold . Hence energy consumption of a node Eik α Tihold . Increased travel time of ME results in high energy consumption in a node which shortens the network lifetime. In order to investigate the impact of waiting time on energy consumption of a node, we have introduced a term Ratio of Idle time Energy consumption to the Total Energy consumption (%): RIETE = 100 ∗ IdletimeEnergyconsumption TotalEnergyconsumption (19) From the above equation RIETE α Idele time Energy it indicates that higher Idle time Energy consumption leads to the higher value of RIETE. The algorithm with lower RIETE value is more efficient. Fig.6 indicates that more than the 60% of the energy spent by a node due to Idle time. From the graphs it is clear that TiHold is the key factor influencing the energy consumption. Even for higher node densities energy consumption is low with HLI, the reason for this is THold for HLI is low when compared to CSS. 6 Conclusion ENI diminishes the TL of ME by limiting the ENs to be covered by ME. The TL so acquired by ENI is additionally abbreviated by deciding an ideal number of Halting Locations to supplant a portion of the ENs by utilizing the HLIT. Simulations have demonstrated that ENI beats COM by a significant separation for all estimations of Tr and node density. The HLI significantly decreases TL contrasted with best known algorithm, CSS. ENI, HLI offers desirable QOS in terms of latency and resource utilization. Bibliography [1] Agarwal, A.; Gupta, K.; Yadav, K.P. (2016). A novel energy efficiency protocol for WSN based on optimal chain routing, 2016 3rd International Conference on Computing for Sus- A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 707 tainable Global Development (INDIACom), IEEE, 368–373, 2016. [2] Al-Tabbakh, S.M. (2017). Novel technique for data aggregation in wireless sensor networks, 2017 International Conference on Internet of Things, Embedded Systems and Communica- tions (IINTEC), IEEE, 1–8, 2017. [3] Amarlingam, M.; Mishra, P. K.; Rajalakshmi, P.; Giluka, M.K.; Tamma, B.R. (2018). Energy efficient wireless sensor networks utilizing adaptive dictionary in compressed sensing, 2018 IEEE 4th World Forum on Internet of Things (WF-IoT), 383–388, 2018. [4] Begum, B.A.; Satyanarayana, N.V. (2015). Composite interference mapping model for in- terference fault-free transmission in WSN, 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, 2118–2125,2015. [5] Chaudhari, M.;Koleva, P.; Poulkov, V.; Deshpande, V. (2017). Energy efficient reliable data transmission in resource constrained ad-hoc communication networks, 2017 Global Wireless Summit (GWS), IEEE, 17–21, 2017. [6] Chen, T.C.; Chen, T.S.; Wu, P.W. (2008). Data collection in wireless sensor networks assisted by mobile collector, 2008 1st IFIP Wireless Days, IEEE, 1–5, 2008. [7] Chiu, K.-M.; Liu, J.-S. (2011). Robot routing using clustering-based parallel genetic algo- rithm with migration, 2011 IEEE Workshop on Merging Fields of Computational Intelligence and Sensor Technology, IEEE, 42–49, 2011. [8] Cirstea, C.; Davidescu, R.; Jianu, A. (2013. Optimum communication paths for mobile WSNs using genetic algorithms, 2013 36th International Conference on Telecommunications and Signal Processing (TSP), IEEE, 299–303, 2013. [9] Devendra Rao, B.V.; Vasumathi, D.; Nandury, S. V. (2015). Exploiting Common Nodes in Overlapped Clusters for Path Optimization in Wireless Sensor Networks, Proceedings of the Second International Conference on Computer and Communication Technologies: IC3T 2015, Springer, 3, 209, 2015. [10] Diaz, S.; Mendez, D. (2019). Dynamic minimum spanning tree construction and maintenance for Wireless Sensor Networks, Revista Facultad de Ingeniería, 93, 57-69, 2019. [11] He, L.; Pan, J.; Xu, J. (2012). A progressive approach to reducing data collection latency in wireless sensor networks with mobile elements, IEEE Transactions on Mobile Computing, IEEE, 12(7), 1308–1320, 2012. [12] He, L.; Xu, J.; Yu, Y.; Li, M.; Zhao, W. (2009). Genetic algorithm based length reduction of a mobile BS path in WSNs, 2009 Eighth IEEE/ACIS International Conference on Computer and Information Science, IEEE, 797–802, 2009. [13] Heinzelman, W.R.; Chandrakasan, A.; Balakrishnan, H. (2000). Energy-efficient communi- cation protocol for wireless microsensor networks, Proceedings of the 33rd annual Hawaii international conference on system sciences, IEEE, 2, 1-10, 2000. [14] Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic, European Journal of Operational Research, 126(1), 106–130, 2000. [15] Jothikumar, C.; Venkataraman, R. (2019). EODC: An Energy Optimized Dynamic Cluster- ing Protocol for Wireless Sensor Networks using PSO Approach, International Journal of Computers Communications & Control, 14(2), 183-198, 2019. 708 J. Siva Prashanth, S.V. Nandury [16] Kakde, K.R.; Kadam, M. (2017) Performance analysis of tree cluster based data gathering for WSNs, 2017 International Conference on Intelligent Computing and Control (I2C2), 1–5, 2017. [17] Konstantopoulos, C.; Pantziou, G.; Gavalas, D.; Mpitziopoulos, A.; Mamalis, B. (2011). A rendezvous-based approach enabling energy-efficient sensory data collection with mobile sinks, IEEE Transactions on Parallel and Distributed Systems, 23, 809–817, 2011. [18] Liao, W.-H.; Kuai, S.-C. (2017). An Energy-Efficient SDN-Based Data Collection Strategy for Wireless Sensor Networks, 2017 IEEE 7th International Symposium on Cloud and Service Computing (SC2), 91–97, 2017. [19] Liao, Y.; Qi, H.; Li, W. (2012). Load-balanced clustering algorithm with distributed self- organization for wireless sensor networks, IEEE Sensors Journal, 13, 1498–1506, 2012. [20] Liu, J.-S.; Wu, S.-Y.; Chiu, K.-M. (2013). Path planning of a data mule in wireless sensor network using an improved implementation of clustering-based genetic algorithm, 2013 IEEE Symposium on Computational Intelligence in Control and Automation (CICA), 30–37, 2013. [21] Misbahuddin, M.; Putri Ratna, A.A.; Sari, R.F. (2018). Dynamic Multi-hop Routing Proto- col Based on Fuzzy-Firefly Algorithm for Data Similarity Aware Node Clustering in WSNs, International Journal of Computers Communications & Control, 13(1), 99-116, 2018. [22] Prashanth, J.S.; Nandury, S.V.(2015). Cluster-based rendezvous points selection for reduc- ing tour length of mobile element in WSN, 2015 IEEE International Advance Computing Conference (IACC), 1230–1235, 2015. [23] Restuccia, F.; Anastasi, G.; Conti, M.; Das, S.K. (2013). Analysis and optimization of a protocol for mobile element discovery in sensor networks, IEEE Transactions on Mobile Computing, 13(9),1942–1954, 2013. [24] Rubel, M.D.S.I.; Kandil, N.; Hakem, N.; Zuyal, M.D.S.I. (2017). Clustering approach delay sensitive application in wireless sensor network (WSN), 2017 IEEE International Conference on Telecommunications and Photonics (ICTP), 82–86, 2017. [25] Sen, S.; Chowdhury, C.; Neogy, S. (2016). Design of cluster-chain based WSN for energy efficiency, 2016 2nd International Conference on Applied and Theoretical Computing and Communication Technology (iCATccT), 150–154, 2016. [26] Singh, V.K.; Kumar, R.; Sahana, S. (2017). To enhance the reliability and energy efficiency of WSN using new clustering approach, 2017 International Conference on Computing, Com- munication and Automation (ICCCA), 488–493, 2017. [27] Venkataraman, G.; Emmanuel, S.; Thambipillai, S. (2005). DASCA: a degree and size based clustering approach for wireless sensor networks, 2005 2nd International Symposium on Wireless Communication Systems, 508–512, 2005. [28] Venkataraman, G.; Emmanuel, S.; Thambipillai, S. (2008). Energy-efficient cluster-based scheme for failure management in sensor networks, IET communications, 2(4), 528–537, 2008. [29] Vikram, G.R.; Krishna, A.V.N.; Chatrapati, K.S. (2017). Variable initial energy and unequal clustering (VEUC) based multicasting in WSN, 2017 International Conference on Wireless Communications, Signal Processing and Networking (WiSPNET), 82–86, 2017. A Cluster–based Approach for Minimizing Energy Consumption by Reducing Travel Time of Mobile Element in WSN 709 [30] Vinutha, C.B.; Nalini, N.; Veeresh, B.S. (2017). Energy efficient wireless sensor network using neural network based smart sampling and reliable routing protocol, 2017 International Conference on Wireless Communications, Signal Processing and Networking (WiSPNET), 2081–2085, 2017. [31] Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids), New results and new trends in computer science, 359–370, 1991. [32] Xing, G.; Li, Mi.; Wang, T.; Jia, W.; Huang, J. (2011). Efficient rendezvous algorithms for mobility-enabled wireless sensor networks, IEEE Transactions on Mobile Computing, 11(1), 47–60, 2011. [33] Xing, G.; Wang, T.; Jia, W.; Li, Mi. (2008). Rendezvous design algorithms for wireless sensor networks with a mobile base station, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, 231–240, 2008. [34] Xing, G.; Wang, T.; Xie, Z.; Jia, W. (2008). Rendezvous planning in wireless sensor networks with mobile elements, IEEE Transactions on Mobile Computing, 7,1430–1443, 2008. [35] Xu, Ji.; He, L.; Chen, Z.; Huang, G.; Yuan, T. (2008). Reducing the path length of a mobile BS in WSNs, 2008 International Seminar on Future BioMedical Information Engineering, 271–274, 2008. [36] Xu, R.; Dai, H.; Wang, F.; Jia, Z. (2013). A convex hull based optimization to reduce the data delivery latency of the mobile elements in wireless sensor networks, 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, IEEE, 2245–2252, 2013.