{'fraction_non_alphanumeric': 0.029693679201018834, 'fraction_numerical': 0.00770829144044507, 'mean_word_length': 4.499447106524143, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RFDMRP: River Formation Dynamics based Multi-Hop Routing Protocol for Data Collection in Wireless Sensor Networks

In Wireless sensor networks, sensor nodes sense the data from environment according to its functionality and forwards to its base station. This process is called Data collection and it is done either direct or multi-hop routing. In direct routing, every sensor node directly transfers its sensed data to base station which influences the energy consumption from sensor node due to the far distance between the sensor node and base station. In multi-hop routing, the sensed data is relayed through multiple nodes to the base station, it uses less energy. This paper introduces a new mechanism for data collection and routing based on River Formation Dynamics. The proposed algorithm is termed as RFDMRP: River Formation Dynamics based Multi-hop Routing Protocol. This algorithm is explained and implemented using MATLAB. The performance results are compared with LEACH and MODLEACH. The comparison reveals that the proposed algorithm performs better than LEACH and MODLEACH. © 2015 The Authors. Published by Elsevier B.V. Peer-review under responsibility of organizing committee of the Eleventh International Multi-Conference on Information Processing-2015 (IMCIP-2015).


Introduction
Wireless Sensor Networks 1-3 (WSNs) are extensively used in numerous real time applications such as military, medical, disaster detection, structural monitoring, etc. These WSNs contains huge set of small sensor nodes, deployed in the environment for monitoring environmental parameters such as humidity, temperature, pressure, etc. The wireless sensor nodes sense the data from environment based on the application and forwards to the central base station or sink for further processing 4 . This process is called data collection, which is the primary task of the WSNs. In data collection process 4 , the sensor nodes forward the data to the central base station either by direct communication or by multi-hop communication. The direct communication from sensor nodes to base station is energy expensive due the distance between sensor nodes and base station is more, this reduces the lifetime of the network. Alternatively, Multi-hop communication [5][6][7] schemes are used for better network lifetime and performance due to its effective utilization of resources. In multi-hop communication, every sensor node is busy in forwarding the sensed/received data to nearest intermediate (neighbor) nodes or to the base station using multi-hop routing paths. In this process, selection of next (neighbor) node in routing path is very important for forwarding data. The next node or forwarding node in the routing path is not only meant for relaying the data, but also useful for aggregating the data. Data aggregation or Data fusion techniques are used to shrink the size of the data packet to be transmitted to next node by aggregating the data or by eliminating similar data, received from previous nodes 2 . Multi-hop techniques improve the energy conservation of node and the lifetime of the network.
Swarm intelligence is one of the mechanism used for finding the suitable nodes in the routing path between sensor nodes and the base station. In WSNs, swarm intelligence mechanisms 8-10 such as ant colony, bee colony, etc., are already used to elect the next node in the routing path. A nature inspired mechanism known as River Formation Dynamics (RFD) 11 can be introduced in WSNs for suitable node selection in multi-hop routing. RFD mechanism is free from local cycles and this is one of the facts making it suitable for path finding in WSNs. In this paper, Applicability of RFD mechanism in path finding for WSNs is explored. The two parameters hop count distance and residual energy are used by RFD for selecting the suitable nodes. The proposed mechanism is called as RFDMRP (River formation Dynamics based Multi-Hop Routing Protocol). RFDMRP is implemented using MATLAB and performance is analyzed and compared with the existing algorithm such as LEACH and MODLEACH. The metrics network lifetime and energy consumption are used for comparison.
Henceforth the paper is coordinated as follows: Section 2 discusses the conceptual RFD mechanism. The related work is explained in Section 3. Section 4 describes the RFDMRP data collection protocol implementation details. The simulation results analyzed and compared in section 5. Finally, Section 6 concludes the paper.

Related Work
During the last decade, researchers have extensively investigated various techniques on multi-hop routing. The existing multi-hop routing techniques are mainly based on hierarchical or cluster based routing protocols [12][13][14][15][16][17] .
Heinzelman et al. 13 proposed LEACH, a hierarchical cluster based routing algorithm for enhancing the lifetime of the network and reducing the energy usage. In this protocol, the network is managed in the form of clusters. Each cluster consists a set of cluster members that are organized by a Cluster Head (CH). The cluster member forwards the data to respective CH and CHs forward this data to base station. CHs are selected randomly in a distributed manner. Later, LEACH was modified to LEACH-C 12 , where the CH selection process was based on a centralized process, i.e., CHs are elected by the base station based on their residual energy. Mahmood et al. 14 proposed an MODLEACH, modified version of LEACH. In MODLEACH, a CH replacement technique and dual transmitting power levels were proposed to improve the performance based on the metrics such as throughput and lifetime. However, in above techniques due to dynamic cluster formation the distance between CH and the Base Station (BS) is far away and some of the cluster node are also far away from its CHs. Hence, direct data transmission from cluster members to CH and CH to BS leads to more energy consumption. In literature [15][16][17] , enhanced LEACH protocols are proposed. In these protocols, the multi-hop communication is introduced in between the CH and BS to improve the lifetime of the network.

River Formation Dynamics (RFD)
RFD 11 is one of the heuristic optimization method and a subset topic of swarm intelligence. RFD is based on replicating the concept of how water drops combine to form rivers and rivers in turn combine to join the Sea by selecting the shortest path based on altitudes of the land through which they flow. In the process of river formation, the water drops are always flowing from higher altitude position to lower altitude positions. Since, the slope of the two positions is more, then the water flowing from higher positions to lower positions erode and carry the eroded soil to be deposited in the lower positions. By this deposit the altitude of the lower position get increased. Also shortest path is formed from higher to lower position.
The process of RFD mainly consist of two stages viz., Initialization stage and River formation stage 11  There is similarity a between RFD and data collection processes in WSN. In RFD, the source (drop generating) positions generate water drops and these water drops are interested to meet the destination or Sea. Similarly, in WSN data collection process, the sensor nodes generate the data and this data is interested to reach the base station. Hence, the sensor data act like water drops, the source positions like sensor nodes, and base station as Sea. The drops are combined and flows from source to sea to form the rivers based on altitude value of position in RFD. In the same way to forward the data in WSNs, the sensor nodes can form a path to the base station based on hop-count and residual energy.

RFDMRP: RFD based Multi-hop Routing Protocol
RFDMRP, a multi-hop routing protocol, is proposed for data collection in WSN. An example network having 100 randomly deployed sensor nodes and a base station presented in middle of the network. The base station divides the network into various regions such as R 1 , R 2 , R 3 , etc., using the following Equation 1.

T r is transmission range of sensor nodes and distance(B S, V i ) is the Euclidean distance between Base Station and Sensor Node
are the coordinates of Base Station and sensor node (V i ) respectively.
The proposed RFDMRP algorithm is explained in Algorithm 1. This algorithm consists of two stages: Initialization stage and Path Selection and Data Relay stage. These stages are explained in the section given below.

Initialization stage
Initially, in this stage, all the sensor nodes are randomly placed in the environment depends on the application. All nodes in the network computes its hop count distance from the BS. For calculation of hop count, BS broadcasts the Beacon message containing its identity. The node, which receives the Beacon signal responds with its id and its location coordinates. BS calculate the hop count from each node using the node coordinates and send the hop count value to nodes. Each sensor node stores hop count value in Neighbor Node information table (NN table). The NN table consist of Next − Node, Hop Count between Next node and BS (HC − BS), Neighbor Node Remaining Energy (NNRE), Distance (Distance between source node and next node), and Distance from next node to BS (D − to − BS). To calculate the neighbor node information, source nodes (Src − ID) sends a REQUEST packet to the neighboring nodes. The neighboring (Dest − ID) node upon receiving REQUEST packet, search in its NN table for HC − BS, NNRE, and Coordinates. Then, it replies with the REPLY packet to the source node (Src − ID) then source node updates its NNtable. The format of REQUEST and REPLY packets are shown in Fig. 1.

Path selection and data relay stage
In this stage, path is selected between source nodes and the BS by selecting the forward node using RFD mechanism. Once the path is selected, the source node uses the selected path to relay the data to BS. This stage consists of three steps: 1) Forward Node Selection 2) Aggregate and Forward the Data 3) Update Energy of each Node and NN information table.

Forward node selection
In the proposed approach source node sends the sensed data to the base station using multi-hop communication.
In multi-hop communication, the selection of neighbor node for onward data forwarding is an important task. Here RFD mechanism is used for next hop node selection.
Lets assume that the node i is present in Region R n and node j present in Region R m , where m ≤ n. For forwarding or receiving data, the Residual Energy of both node i , and node j must be more than Threshold value (T h ) i.e., R E(i ) ≥ T h and R E( j ) ≥ T h . The node i having the probability to select node j as a forward node is denoted by P(i, j ) and is calculated as follows: where distance(i, j ) is the euclidean distance between node i to node j (i.e., (x i − x j ) 2 + (y i − y j ) 2 ). N N(i ) is Neighbor Node list of node i , i.e. N N(i ) = { j, such that distance(i, j ) ≤ T r }. R E( j ) is residual energy of node j . T h is threshold value = 20% of Initial Energy (E 0 ).

Aggregate and forward the data
Forward nodes perform data aggregation on receiving and/or sensed data and then forward to the next selected forward node towards the BS. The energy consumption for data aggregation is calculated using the Equation 4 where E D A is the energy needed for Data Fusion or Aggregation of sensor data. b is the data packet size.

Update energy of each node and NN information table
The first order radio energy model of sensor node considered for this work is discussed in literature 12 is used to calculate the RE (Residual Energy) of a node i , when it transmits or receives the data packet as follows: where E T X (b, d) is the energy consumption for transmitting b bit of data in d distance. E R X (b) is the energy expenditure for receiving b bit of data. Later, all the nodes update its NN information table by exchanging the REQUEST/REPLY packets.

Simulation Results and Analysis
The proposed RFDMRP routing algorithm is developed and tested using the MATLAB (2012b). The algorithm is simulated using 100 sensor nodes were randomly deployed in 100 m × 100 m area along with BS. The BS was located in (50,50) position. The transmission range (T r ) of every sensor node in one hop was fixed at 20 m. The initial energy (E o ) for the sensor node was set as 0.5 J. The value of Electronic amplification (E elec ) for transmitting and receiving the data was set as 50 nJ/bit. The packet size of data was 4 KB. The energy consumption of a sensor node for transmitting data using free space model ( f s ) and multi-path model ( mp ) were set as 10 pJ/bit/m 2 , 0.0013 pJ/bit/m 4 respectively.

Result analysis
In this Section the performance of proposed algorithm RFDMRP is analyzed and compared with LEACH and MODLEACH protocols. For comparison important performance parameters are considered such as • The Numbers of nodes alive over simulation time (rounds) • The numbers of nodes dead over the simulation rounds • The Remaining Energy over simulation rounds • The data packets reached to the BS over simulation rounds. Figure 2(a) shows the graph plotted for the dead nodes over simulation rounds. The first node died earlier in RFDMRP than the other two approaches due to multi-hop transmission of data packets. However, the last node expired earlier in existing approaches than the RFDMRP. This shows the lifetime is extended in the proposed approach due to the dynamic selection of the next hop node. Similarly, the graph plotted for number of alive nodes over simulation rounds is shown in Fig. 2(b). Figure 3(a) shows the graph plotted for remaining energy of each round. RFDMRP consumed less energy compared to the existing algorithms. This is due to the nodes in the RFDMRP forward the data to the nearest (less distance) node with less energy. Figure 3(b) shows the graph plotted between data packets forwarded to base station and simulation rounds. More data packets are relayed to the Base station in RFDMRP when compared to the existing approaches. This is due to the nodes nearer to the BS in RFDMRP are more than the number of cluster heads in existing approaches.

Conclusion
In WSN, multi-hop routing is an effective mechanism for data collection. In multi-hop routing, the selection of forward node for relaying data plays a vital role. In this paper, one of the swarm intelligence mechanisms, RFD, is used to propose RFDMRP. RFDMRP, is an RFD based multi-hop routing protocol for data collection in WSN to conserve energy and expand the network lifetime. In RFDMRP, RFD considers the hop count value and residual energy as parameters for forward node selection. Finally, proposed work was compared with LEACH and MODLEACH by considering the performance metrics such as network lifetime and energy consumption. From the results, it is observed that RFDMRP performs better than the existing algorithms.