Resource aware and reliable data reporting algorithm for object tracking in WSNs

Abstract

Object tracking have become one of the major applications of Wireless Sensor Networks (WSNs) due to its wide real-life applications such as wildlife animal monitoring and military area intrusion detection. Many recent articles have been dedicated to localization of objects; however, few of these articles were concentrated on the reliability of network data reporting along with objects localization. In this work, an efficient data reporting method is proposed for object tracking in WSNs. Energy is considered as one of the most critical resources for WSN. Data transmission from the nodes to the sink along with the minimum energy path could be one of the solutions to minimize the overall network energy consumption. However, this might lead to unbalanced energy among sensor nodes resulting in, energy hole problem. Moreover, the reliable data transmission is an essential aspect that should be considered when designing a WSN for object tracking application, where the loss of data packets will affect the accuracy of the tracking and location estimation of a mobile object. Furthermore, due to the limited memory resources of sensor nodes, full utilization of such resources with less buffer overflow remains as a one of main consideration when a WSN application is designed. Consequently, this paper aims to achieve both minimum energy consumption in reporting operation and balanced energy consumption among sensor nodes for WSN lifetime extension. In addition, data reliability is considered in our model where, the sensed data can reach the sink node in a more reliable way. Finally, buffer space is considered in to reduce the packet loss and energy consumption due to the retransmission of the same packets. This work first formulates the problem as 0/1 Integer Linear Programming (ILP) problem, and proposes SWARM intelligence to solve the optimization problem. Through simulation, the performance of proposed method to report information about the detected objects to the sink is compared with the previous work such as LR-based object tracking algorithm, EBRP, ACO, TADR, SEB, and CLR-Routing.

Keywords

WSNs object tracking data reporting SWARM intelligence Ant Colony System (ACS)energy balancing reliability

1 Introduction

A Wireless sensor network (WSN) is a wireless network consisting of large number of small size, inexpensive, and battery operated sensor nodes. Such nodes are essential for monitoring physical or environmental conditions such as temperature and humidity, perform simple computation, and communicate via wireless multi-hop transmission technique to report the collected data to sink node [1]. However, the nodes in WSN have severe resource limitations such as energy, bandwidth, and storage resources. Energy is an extremely crucial resource because it not only determines the sensor nodes lifetime, but the network lifetime as well [2]. In WSNs, communication has been recognized as the major source of energy consumption and costs significantly more than computation [3]. Consequently, most of the existing routing techniques in WSN attempt to find the shortest path to the sink to minimize energy consumption. As a result, highly unbalanced energy consumption which causes energy holes around the sink and significant network lifetime reduction [4, 5]. Therefore, designing energy-balanced routing technique plays a crucial role in WSNs [4, 5].

The reliable data transmission is one of the most essential issues in WSNs [6 –8]. The loss of important information due to unexpected node failure or dynamic nature of wireless communication link [9] prevents the sensor network from achieving its primary purpose which is data transfer. Hence, routing techniques should give priority to reliable transmission. At the same time, it is critical to reduce packet loss in WSNs which will improve the network throughput and energy-efficiency.

Due to memory constraints on sensor nodes, buffering a large number of packets is impossible. Thus, such a buffer overflow problem may result in information loss and more energy consumption due to the retransmission of the same packets. Thus, such retransmission limits the network’s lifetime and efficiency. Consequently, it is a highly needed to consider buffer space when designing routing protocols in WSNs [10].

In the last two decades, optimization techniques inspired by swarm intelligence have gained much popularity [11]. They mimic the swarms’ behavior of social insects like ants and bees, the behavior of other animal societies such as birds flocks, or fish schools as well [11]. Swarm intelligent systems are robust, scalable, adaptable, and can efficiently solve complex problems through simple behavior [12] such as the shortest path finding. Ant Colony System (ACS) is considered one of the most important swarm intelligence techniques that can provide approximate solutions to optimization problems in a reasonable amount of computation time [11]. ACS [13] has been inspired from the food searching behavior of real ants which can be utilized to find the shortest path in WSNs. Unlike other routing approaches [14], the ant colony optimization meta-heuristic proposed in the literature for WSNs is based only on local information of sensor nodes [15].

Object tracking is considered one of the most demanding applications in WSNs due to its wide real-life applications such as wildlife animal monitoring [16, 17] and military intrusion detection [18]. The object tracking process consists of two critical operations. The first operation is monitoring, where the movement states of the mobile object is detected and tracked by the sensor nodes. The second operation is reporting, where nodes detecting the object report their observations to the sink node [19].

Many object tracking researches focus on how to track the location of objects accurately and do not consider many other parameters such as reliable data reporting [19 –23], nodes energy consumption, and nodes energy balancing. Therefore, in this paper, we take these parameters collectively into consideration. We believe that considering such parameters will enhance the overall performance of the WSNs as well as advance the object tracking operation. To do so, our contributions in this paper focus on: 1) formulating the object tracking problem into 0/1 integer programming with previously mentioned parameters, 2) reducing energy consumption in reporting operation for WSN lifetime extension, 3) balancing of energy consumption among sensor nodes to maintain and balance of residual energy on sensor nodes as well, 4) enhancing data reliability where the sensed data can reach the sink node in a more reliable way, 5) Taking into consideration buffer space on sensor nodes to reduce dropped packets, which in turn conserves energy, and 6) introducing a Swarm Intelligence as a heuristic solution based energy reduction and reliability as well as load balancing.

The rest of this paper is organized as follows: section 2 introduces a brief summary of the related work. Section 3 introduces the problem description. Then, section 4 describes the problem formulation. Section 5 describes the proposed approach. Section 6 provides the simulation results. Finally, Section 7 concludes the paper.

2 Related work

This section focuses only on the most related work to the proposal of this paper. It starts by explaining the work presented in [4 , 26–29] which are the more related work to our proposed approach followed by the differences from our proposal.

Line and Lee [24] proposed an energy-efficient object tracking algorithm in WSNs. It focuses on reducing the communication cost in object tracking. The network in [24] is assumed to have two types of nodes which are sensor and communication nodes. The movement states of mobile objects is detected and traced by the sensor nodes while, the information about the objects that was detected jointly by its pair of adjacent sensor nodes is stored and reported to the sink via communication nodes. The minimizing communication cost in [24] is formulated as a 0/1 integer programming problem for optimal solution. Then, a lagrangian relaxation-based (LR-based) heuristic algorithm was proposed to solve the optimization problem.

By studying LR-based algorithm [24], it is found out that some issues are not considered. First of all, the reliable data transmission which becomes one of the most essential issues in WSNs is not considered. Indeed, ignoring such issue might increase the packet loss as well as can cause more energy consumption due to packet retransmission as a result of unstable paths which inevitably affects the network efficiency. Secondly, finite buffer size of sensor nodes which is one of the major challenges in WSN was not also taken into consideration. This might increase the packet loss which in turn will cause retransmission of the same packets, thereby increasing energy consumption. Finally, the approach suffers from energy unbalancing. This might cause an energy hole problem, where the sensor nodes closer to the sink will drain their energy faster than others. Therefore, this uneven use of energy leads to a significant network lifetime reduction.

Additionally, the LR-based algorithm assumed that each communication node must have two adjacent sensor nodes in the way of the mobile object; it is a hard assumption which might not be the case in most of WSNs if not all of them. Finally, the use of lagrangian relaxation to solve an optimization problem may have some disadvantages such as solution oscillation which is a serious and inherent disadvantage of such method [25].

Ren et al. [4] proposed an Energy-Balanced Routing Protocol (EBRP). EBRP algorithm borrows the concept of potential in physics to construct a mixed virtual potential field in terms of depth, energy density, and residual energy. The depth field is used to route packets toward the sink node. The energy density field is essential to balance energy consumption where, the packets are driven through the dense energy area. Finally, the residual energy field protects nodes with relatively low residual energy from dying.

El Ghazi et al. [26] proposed an improved ant colony optimization routing (ACO) for WSN. In this algorithm, an enhanced ant colony is used to optimize the node power consumption and prolongs network lifetime. The ACO improved approach in [26] enhanced an approach based on ACO in which the probability of selecting next hop neighbor has been determined by using two heuristic functions. The first one is related to the quantity of the pheromone which inversely proportional to hop count, and the second depends on residual energy of neighbor nodes. However, the improvement in [26] is done by adding more accuracy to make a choice especially when probabilities are equal where, in such case the node chooses randomly the next hop. As a result, this might make wrong choice and data loss in uncovered area, or packets travel a long path to the sink. Therefore, many nodes lose power due to bad choice, delivery delay, and may leads to network lifetime reduction. The ACO improved approach adding new heuristic information to distinguish the best neighbor and avoiding the use of wrong nodes. The new heuristic information is related to the energy of the neighbor node which having sink in its collection field. Such neighbor node will have more chance to be chosen, because the packets will attain the sink node definitely. However, only energy and pheromone are considered in the probabilistic rule when the sink is not in the neighbor node field.

Meanwhile, the analysis of ACO improved algorithm [26], and EBRP [4] show that some issues are not considered which are reflected as drawbacks. Firstly, the network reliability, as discussed above, this might increase the packet loss and packet retransmissions which affects the network efficiency. The second is the queue buffer size in which it has directly impact on network throughput and lifetime. Finally, node load where, the nodes with heavy load and low residual energy should be prevented from being selected as a next hop to achieve energy balance of the whole network and relieve the energy hole problem. Consequently, taking residual energy only into consideration as in [4, 26] is not sufficient to achieve balanced energy usage in the network.

Ren et al. [27] proposed a traffic aware dynamic routing (TADR) algorithm to route the packets around the congestion areas and scatter excessive packets along multiple paths consisting of idle or unloaded nodes. In this algorithm, a hybrid potential field is constructed in terms of depth and the normalized queue length. The depth field creates a backbone to forward packets toward the sink. The queue length field is used to prevent the packet from going to the possible congestion area. However, TADR algorithm doesn’t consider two critical issues which regard as a drawback. The first is energy balancing, as described above; this might lead to unbalanced energy consumption in the network which causes energy holes around the sink and significant network lifetime reduction. The second issue is the network reliability which is one of the key issues in WSNs due to the high dynamics, limited resources, and unstable channel conditions. Thus, this might deteriorate the network performance as mentioned above.

Yaessad et al. [28] proposed a simple Cross-Layer Balancing Routing (CLB-Routing) that enhances the WSNs lifetime by balancing the energy consumption in the forwarding task. CLB-Routing protocol is a bottom up approach, where the network layer uses information given by the MAC layer in the choice of the next hop. The proposed algorithm in [28] operates in two phases. The first is initialization, where the sink node broadcasts a route request message containing a cost variable initialized to zero. Each node receiving this message, updates the cost field according to its residual energy and the energy required for communication between that node and the sender of the route request and, then broadcasts it. The second phase is data transmission, where the MAC layer informs the network layer about all the overheard communications of the neighboring nodes. With this information, a node can know how many times each forwarding node has routed data. According to this information, and to effectively balance sensor nodes energy consumption, a node chooses its next hop among the less-used ones. This choice is not random; it is according to a probability, which counts residual energy, energy of communication, and the number of times that each forwarding node has routed data. However, CLB-Routing had important issues to take into account, but it lacked some others like network reliability and buffer size. This eventually affect the network throughput and lifetime as described above.

Qian et al. [29] Proposed a Swarm intelligence based energy balance routing scheme (SEB). It utilizes swarm intelligence to maintain and balance residual energy on sensor nodes for WSN lifetime extension. SEB algorithm balancing residual energy on sensor nodes evenly according to their weights as much as possible. The node weight is related to the number of its neighbor nodes that may select it to relay their messages. The probability of selecting the next hop neighbor node is calculated according to residual energy, distance to the sink, weight of nodes, and the environment pheromone which is related to path quality.

Nevertheless, the previous study of SEB shows that it has a drawback since some issues are not considered. The first is the packet buffer capacity of sensor nodes. As described above, this might increase the packet loss and packet retransmission which inevitably affects the network efficiency. Secondly, the dynamic behavior of the wireless link quality over time and space where, the path quality is determined as a function of hop count. This can be easily lead to the use of low-quality links, and result in unreliable routs [30]. Finally, calculating the weight of nodes in such algorithm was based on the assumption that the environment events distributed uniformly. This might be inefficient when the environment events distributed non-uniformly.

Our approach firstly formulates the object tracking task as 0/1 integer programming problem. Then, it develops a heuristic algorithm to construct an efficient object tracking in WSNs. We propose a novel protocol based on energy reduction, reliability, and energy balance routing in WSNs for object tracking. SWARM intelligence is proposed as a heuristic solution for the optimization problem, since it presents feasible and efficient solution. The WSN in this proposed approach consisting of sensor nodes only that is not like the LR-based algorithm in [24]. The Sensor node could be used to sense the objects in the environment. At the same time, it could be used as a relay node, since WSNs are usually based on a multi-hop transmission. Furthermore, the proposed approach does not consider the frequency of object movement of each pair of sensor nodes in the calculation of total communication cost as in [24]. Instead, it considers the frequency of object movement at each sensor node which detects objects in the environment which is more realistic assumption.

The proposed algorithm considers the end-to-end reliability of a multi-hop route based on the Packet Reception Rate (PRR) which is one of the most commonly used reliability metrics [31]. In this model, the work analyzes the reliability of the whole path from the next hop node to the sink, and then chooses the relay node with the best PRR which improve the end-to-end reliability of a multi-hop route. Moreover, the proposed algorithm can balance energy consumption among sensor nodes evenly as much as possible through new effective function between nodes’ residual energy and weight. As well as, a new weight definition is proposed in this algorithm to achieve balanced energy consumption for both uniform and non-uniform event distribution in the environment. In addition, it can effectively alleviate buffer overflow by integrating the normalized buffer space into routing choice. Consequently, the local information in the proposed SWARM solution refers to each neighbor’s residual energy, weight, normalized buffer space, transmission distance, and pheromone. As well as, a new pheromone update operator is designed to integrate energy, path length, and path quality into routing choice.

3 Problem description

Consider a static multi-hop WSN deployed in the sensing field for the purpose of object tracking. Our objective is to propose a data reporting model for this kind of service. In this model, we aim to achieve reliable data reporting algorithm taking into consideration nodes’ energy consumption, energy balancing among sensor nodes, and nodes’ buffer space. The object tracking problem is modeled as a graph based on the nodes location in the monitored environment and their characteristics. The object tracking problem can be modelled as a random geometric graph, G (V, L), where V denotes the set of sensor nodes which distributed randomly in the square monitoring field and L represents a set of all communication links (i, j) where, i, j ∈ V. Link (i, j) exists if and only if nodes i, j are within radio range of each other. Assuming multi-objects object moving in the environment, they will be detected by some sensor nodes which are called source nodes. The frequency of object movement at each source node differs according to the number of objects that are within the sensing range of each source node. In addition, it is assumed that the MAC layer provides the link quality estimation service, e.g., the PRR information on each link [32], where each node is aware of the PRR values to its one-hop neighbors. The information regarding the presence of the detected objects at each source node should be reported to the sink node. Since WSNs are usually based on a multi-hop transmission, the source nodes send their data to the sink through intermediate sensor nodes which acts as a relay nodes. The chosen path from each source node to the sink should be the best path which satisfies some constraints including 1) low communication cost, 2) its reliability greater than or equal target value, 3) at the same time, sensor nodes on that path should have the maximum value resulting from a new proposed equation between the residual energy and weight compared with their neighbors to balance energy consumption among sensor nodes, and 4) as well, sensor nodes should have a buffer space greater than or equal to message size to reduce packet loss and energy consumption due to retransmission of the same packets as a result of bufferoverflow.

4 Problem formulation for optimal solution

Based on the previous modelling to the object tracking problem, the problem can be solved optimally. In this section, the problem is mathematically formulated using Integer Linear Programming (ILP); then solved by any of the selected solver [15]. This solution is used to guarantee the optimal solution, if any, to the previously described problem. However, due to the complexity of the problem and its constraints, it is expected and it is well known from the previous experiences in similar problems that no optimal solution could be found in some cases of the problem representation. Therefore, the mathematical formulation is used to solve small-scale problems as well as it is designed to fully understand the problem with its major constraints. In addition, the optimal solution for small-scale problems could be used to measure the quality of any given heuristic that might be used to solve the same problem. In fact, in the next section, the paper presents a SWARM based optimization solution to the problem. This solution is used for large-scale problems.

To simplify the description of the problem and its formulation, the notations used to model the problem are given in Table 1.

Due to the use of multi-hop routing technique, the information about the detected objects at each source node should be transmitted as messages to the sink node through intermediate nodes or relay nodes. In order to achieve energy balanced routing, the node with heavy weight and low residual energy should be prevented from being selected as a next hop. So, the proposed algorithm considers a model in which the sensor node residual energy and weight are used when choosing the relay node through a new proposed function.

Now, let’s start with the computation of the weight of a neighbor j at time t by Equation (1). ${we}_{j} (t) = {\begin{matrix} \sum_{i \in {NEB}_{j}} {Mes}_{i} (t) & if h c_{j} \leq {hc}_{i} \\ 0 & otherwise \end{matrix}$ (1) Because the objects detected in the monitored environment distribute non-uniformly, node weight can be defined as the total number of messages at its neighbor nodes which may choose it to relay their

messages. Equation (1) means that packets are not allowed to be transmitted backward to the neighbors with higher hop count. This strategy ensures that the packets are forwarded closer toward the sink and prevents forming a loop.

In addition, the new function that combines residual energy and weight for each node j at time t is defined by Equation (2) as follows:

${Ewr}_{j} (t) = {\begin{matrix} (({NRE}_{j} (t) - {we}_{j} (t)) + 1) \cdot (exp ({ENC}_{j} (t))) if {NRE}_{j} (t) \geq {we}_{j} (t) \\ (\frac{1}{{we}_{j} (t) - {NRE}_{j} (t)}) \cdot (exp ({ENC}_{j} (t))) if {NRE}_{j} (t) < {we}_{j} (t) \\ 0 if {we}_{j} (t) = 0 \end{matrix}$ (2)

Due to the use of multi-hop routing technique, the information about the sensed events at each source node should be transmitted as messages to the sink node through intermediate nodes or relay nodes. Therefore, the relay node needs to hold in a buffer the incoming data packets during the processing time required for the previous ones. The sensor nodes have limited memory, it is impossible to buffer a large number of packets. Consequently, the buffer of the relay node may start overflowing, resulting in loss of important packets and more energy consumption due to the retransmission of the same packets [33]. For efficient use of available buffer, we consider a model in which the probability of buffer overflow is minimized as much as possible by integrating the normalized buffer space into routing choice. The normalized buffer space is defined as the ratio between the buffer space and packet size. It is used to express the number of packets that can be received by every sensor node without it starting buffer overflowing at a certain time. The normalized buffer space of node j at time t can be defined as follows: ${bm}_{j} (t) = {\begin{matrix} \frac{{bs}_{j} (t)}{pz} & if {bs}_{j} (t) \geq pz \\ 0 & otherwise \end{matrix}$ (3)

To compute the shortest path from the source node to the sink node, the Dijkstra algorithm has been used. To fit Dijkstra into our formulation, the algorithm is represented mathematically as follows [34]:

The sensor nodes are being processed according to their order. The sensor nodes that are yet to be processed denoted by U, initially U ∈ S ∪ R. When a sensor node i is processed, the following task is performed:

$\begin{matrix} F (j) = min {F (j), D_{(i, j)} + F (j)}, for all \\ j \in {NEB}_{i}, {NEB}_{i} \in U \end{matrix}$ (4)

Where F (j) denotes the length of the shortest path from node i to node j which is initially equal to zero for the first processed node. When the sensor node i is processed, the {F (j)} values of its neighbors that have not yet been processed are updated in accordance with Equation (4).

To complete the informal description of the algorithm, it is only necessary to specify the order in which the nodes are processed. The next node to be processed is one whose F (j) value is the smallest over all the unprocessed nodes as follows: $i = arg min {F (j)}, j \in U$ (5)

Recalling that U denotes the set of unprocessed nodes, Thus after node i is processed it is immediately deleted from U. so, U = U - {i}

The total communication cost for a graph G and object tracking tree T is defined as the sum of the individual contributions of all source and relay nodes in G:

$\begin{matrix} Total communication cos t (G, T) \\ = \sum_{s \in S} \sum_{d \in D_{s}} \sum_{(i, j) \in L} t_{(i, j)}^{ds} C_{(i, j)} \end{matrix}$ (6)

Based on these computations the problem is formulated as follows:

The objective function: $Z_{IP} = min \sum_{s \in S} \sum_{d \in D_{s}} \sum_{(i, j) \in L} t_{(i, j)}^{ds} C_{(i, j)} (IP)$ $\begin{matrix} Subject to : \\ \sum_{p \in P_{s}} x_{p}^{sd} = 1 \forall s \in S, \forall d \in D_{s} \end{matrix}$ (7)

$\begin{matrix} \sum_{i \in S \cup R} U_{(i, j)}^{sd} = 1 \forall s \in S, \forall d \in D_{s}, j \in {NEB}_{i}, \\ {NEB}_{i} \in S \cup R \end{matrix}$ (8)

$\begin{matrix} \sum_{N \in {NEB}_{i} - {j}} z_{N} ({Ewr}_{j} (t) - {Ewr}_{N} (t)) < 0 \forall \\ j \in {NEB}_{i}, {NEB}_{i} \in S \cup R \end{matrix}$ (9)

$\begin{matrix} 2 - \sum_{N \in {NEB}_{i} - {j}} z_{N} = m_{j} + 1 \forall j \in {NEB}_{i}, \\ {NEB}_{i} \in S \cup R \end{matrix}$ (10) $\sum_{j \in {NEB}_{i} - {j}} z_{N} \leq 1 \forall j \in {NEB}_{i}, {NEB}_{i} \in S \cup R$ (11)

$\begin{matrix} \sum_{p \in P_{s}} k_{p}^{sd} {PRR}_{p} \geq Q \forall s \in S, \\ \forall d \in D_{s}, {PRR}_{p} \in {PRR}_{P_{s}} \end{matrix}$ (12) $k_{p}^{sd} + 1 \leq x_{p}^{sd} + 1 \forall p \in P_{s}, s \in S, d \in D_{s}$ (13) $\sum_{j \in {NEB}_{i}} b_{j} {bm}_{j} (t) > 0 {NEB}_{i} \in S \cup R$ (14)

$\begin{matrix} \sum_{p \in P_{s}} \sum_{j \in {NEB}_{i}} δ_{j}^{p} x_{p}^{sd} m_{j} b_{j} k_{p}^{sd} \leq U_{(i, j)}^{sd} \forall s \in S, \forall d \in D_{s}, \\ i \in S \cup R, {NEB}_{i} \in S \cup R \end{matrix}$ (15) $\sum_{j \in {NEB}_{i}} m_{j} \leq 1 {NEB}_{i} \in S \cup R$ (16) $\sum_{j \in {NEB}_{i}} b_{j} \leq 1 {NEB}_{i} \in S \cup R$ (17) $\sum_{(i, j) \in L} t_{(i, j)}^{sd} \geq 1 \forall s \in S, \forall d \in D_{s}$ (18) $x_{p}^{sd} = 0 or 1 \forall s \in S, \forall d \in D_{s}, p \in P_{s}$ (19)

$\begin{matrix} U_{(i, j)}^{sd} = 0 or 1 \forall s \in S, j \in {NEB}_{i}, \\ {NEB}_{i} \in S \cup R, \forall d \in D_{s} \end{matrix}$ (20) $m_{j} = 0 or 1 \forall j \in {NEB}_{i}, {NEB}_{i} \in S \cup R$ (21) $k_{p}^{sd} = 0 or 1 \forall p \in P_{s}, \forall s \in S, \forall d \in D_{s}$ (22) $t_{(i, j)}^{sd} = 0 or 1 \forall s \in S, \forall d \in D_{s}, (i, j) \in L$ (23) $b_{j} = 0 or 1 \forall j \in {NEB}_{i}, {NEB}_{i} \in S \cup R$ (24)

To simplify the description of the formulation the constraints are divided into sets and each set is recognized by its functionalities as follows:

1) Routing Constraints:

The routing constraints involve constraints 7,8,15, and 16.

Constraint (7): It is used to guarantee that any source node s must choose only one path to the sink node.

Constraint (8): To avoid cycles where, the use of any node j as a relay node for the same source node s and message d equal to 1.

Constraint (15): the decision variable $U_{(i, j)}^{sd}$ must be enforced equal to 1 when: 1) the path p is selected and the PRR of that path is greater than or equal the target value, 2) node j is on the path, 3) it has the maximum value of Ewr_j (t) compared with other neighbor nodes, and 4) the node j can receive the message without buffer overflow.

Constraint (16-17): they are used to guarantee that any node i must choose only one node j from its neighbors.

2) Energy Constraint:

The energy constraints contain constraints 9, 10, and 11.

Constraint (9–11): they are used to maintain higher and balance residual energy on nodes. Any node i must choose only one node j from its neighbors which has the highest value for Ewr_j compared with other neighbor nodes.

3) Reliability Constraint:

The reliability constraints contain constraints 12 and 13.

Constraint (12-13): It used to guarantee that the selected path p for the source node s and message d has a PRR greater than or equal the target value.

4) Buffer Constraint:

The buffer constraint contains constrain 14.

Constraint (14): It is used to prevent buffer overflow. Any node i must choose only one node j from its neighbors which has enough buffer size to store its message.

5) Decision variables Constraint:

The decision variable constraints are composed of constraints 19 through 24.

Constraint (19–24): $t_{(i, j)}^{sd}, x_{p}^{sd}, U_{(i, j)}^{sd}, m_{j}, b_{j}$ $, and k_{p}^{sd}$ equal 0 or 1.

6) Redundancy Constraint:

The redundancy constraints include only constraint number 18.

Constraint (18): For all $\sum_{(i, j) \in L} t_{(i, j)}^{sd}$ must be greater than or equal to 1.

5 SWARM based solution

This section describes the second solution approach for the object tracking problem which is Swarm Intelligence techniques. Using swarm intelligence to solve the hard problem has several advantages. Some of these advantages are [36]:

Fast route recovery

Fault tolerance

Scalability and adaptation

The proposed SWARM solution is composed of two phases. In the first phase, it starts with a set of forward ants placed in the source nodes and move through neighbor relay nodes until reach sink node. In this algorithm, for calculating the packet transfer probability to the next hop neighbor, residual energy, weight, normalized buffer space, transmission distance, and pheromone are considered. At each node i, a forward ant k selects the next hop node j, j ∈ NEB_i randomly with a probability $p_{r}^{k} (i, j)$ which determined as follows:

$\begin{matrix} p_{r}^{k} (i, j) \\ = \frac{[τ_{ij} (t)]^{α} [η_{ij} (t)]^{β} [ψ_{ij} (t)]^{γ} [ɛ_{ij} (t)]^{λ} [δ_{ij} (t)]^{φ}}{\sum_{l \in {NEB}_{i}} [τ_{il} (t)]^{α} [η_{il} (t)]^{β} [ψ_{il} (t)]^{γ} [ɛ_{il} (t)]^{λ} [δ_{il} (t)]^{φ}} \end{matrix}$ (25)

Where τ_ij (t) is the pheromone value on the link (i, j) at the time t, η_ij (t), ψ_ij (t), ε_ij (t), and δ_ij (t) are the heuristic information of link (i, j) for node j; α, β, γ, λ, and φ are the weight factors that control the pheromone value and the heuristic information parameters respectively.

When forward ant k reaches sink node, it is transformed into a backward ant and the second phase starts. The backward ant starts from the sink node and moves towards its source node along the same path in opposite direction, depositing an increment of pheromone on that.

5.1 Calculation of the heuristic information

In order to maintain higher and balance residual energy on sensor nodes, the proposed relation between residual energy and weight is used as a heuristic information when selecting the next hop neighbor node which denoted by η_ij. $η_{ij} (t) = \frac{{Ewr}_{j} (t)}{\sum_{l \in {NEB}_{i}} {Ewr}_{l} (t)}$ (26)

According to this rule, the node with the greater value of η_ij will have a higher residual energy compared to its weight and a much better opportunity to be chosen as a next hop.

Since energy conservation is an essential issue in WSN, selecting the nodes with minimum hop count is required to minimize energy consumption and conserve much more energy as possible. Therefore, the hop count from neighbor node j to the sink node is used as heuristic information which is denoted by ψ_ij. $ψ_{ij} (t) = \frac{({hc}_{i} - {hc}_{j}) + 1}{\sum_{l \in {NEB}_{i}} ({hc}_{i} - {hc}_{j}) + 1}$ (27)

A neighbor node that has a greater value of ψ_ij (t)is closer to the sink than the others and will be more likely to be chosen as next hop.

In order to avoid or reduce packet loss due to buffer overflow which in turn improve the overall network performance, it is critical to send packets to the sensor node with more buffer space or less traffic load. Therefore, bm_j (t) can be used as heuristic information which denoted by ɛ_ij (t) $ɛ_{ij} (t) = \frac{{bm}_{j} (t)}{1 + \sum_{l \in {NEB}_{i}} {bm}_{l} (t)}$ (28)

This rule enables decision making according to the buffer apace on the neighbor nodes, meaning that if a node has a greater value of ɛ_ijthen it has a much better opportunity to be chosen as next hop.

Due to the dynamic behaviour of the wireless link quality over time and space, it is essential to use the current packet reception ratio of link (i, j), PRR_ij as heuristic information to improve the network throughput. It is denoted by δ_ij (t) $δ_{ij} (t) = \frac{{PRR}_{ij}}{\sum_{l \in {NEB}_{i}} {PRR}_{lj}}$ (29)

Where, the greater value of δ_ij indicates that the link (i, j) more reliable than others. Thus the neighbor node j will have more chance to be chosen as next hop.

5.2 Pheromone calculation

In this algorithm, pheromone concentration is affected by the combination between energy, path length, and path quality in a new effective form. This may improve network reliability, reduce energy consumption, and achieve more balanced transmission among the nodes.

Let us begin with the calculation of the path quality, q_p, which related to the PRR by Equation (30). $q_{p} = {PRR}_{p}$ (30)

Where, PRR_p, represents the packet reception ratio of the path p. Due to the use of multi-hop routing, the PRR_p can be computed by the PRR of each hop on the path p as follow: ${PRR}_{p} = \prod_{(i, j) \in n_{p}} {PRR}_{ij}$ (31)

Where, n_p is the set of edges on the path p (hop count). In this model, all nodes have the same fixed transmission range. So, the number of hops in the path p is considered as the path length, L_p as follow: $L_{p} = n_{p}$ (32)

By estimating the length of each possible path for the same source node, the best path length L_pbest is recorded at the sink. Then, the relative length of path p can be determined as follows: ${Rl}_{p} = L_{p_{best}} / L_{p} = n_{p_{best}} / n_{p}$ (33)

The increasing density of pheromone on the path p is defined as follows: $Δ τ_{ij} = {({Rl}_{p} \times {PRR}^{w_{1}})}^{w_{2}} \cdot {(E_{min}^{p})}^{w_{3}} / n_{p}^{2}$ (34)

Where $E_{min}^{p}$ is the minimum residual energy of nodes visited by ant k and the parameters w₁, w₂, and w₃ determine the relative influence of the energy, path length, and path quality.

The sink node constructs the value of pheromone update operator, Δτ_ij, and sent it back as a backward ant to its source node along the reverse path. Whenever a node i receives a backward ant k coming from neighboring node j, it updates its pheromone concentration according to the following rule: $τ_{ij} (t) = (1 - ρ) τ_{ij} (t - 1) + ρ Δ τ_{ij}$ (35)

Where, ρ ∈ (0, 1) is the evaporation constant that determines the evaporation rate of the pheromone [29].

6 Performance evaluations

In this section, different experiments are conducted to evaluate the performance and validate the effectiveness of our proposal. The section starts by describing the performance metrics followed by simulation environment and finally simulation results.

6.1 Performance metric

For a comprehensive performance evaluation, several quantitative metrics considered are defined below.

Network Lifetime [4]. It is defined as the time duration from the begging of the network operation until the first node exhausts its battery.

Energy Imbalance Factor (EIF) [4]. It is defined to quantify the routing protocol energy balance characteristic which defined formally as the standard variance of the residual energy of all nodes.

EIF = \frac{1}{n} \sqrt{\sum_{i = 1}^{n} ({RE}_{i} - {RE}_{avg})^{2}}

Where n is the total number of sensor nodes, RE_i is the residual energy on node i, and RE_avg is the average residual energy of all nodes.

Throughput Ratio (TR) [28]. This metric is defined as:

TR = \frac{Number of packets received by the sin k}{Number of packets sent by source nodes}

Average End-to-End Delay (Seconds) [37]: It is defined as the average time a packet takes to travel from source node to the sink node. This includes propagation, transmission, queuing, and processing delay. The processing delay can be ignored as a result of fast processing speed [38].

6.2 Simulation environment

In this paper, the simulation environment consists of 80 sensor nodes deployed randomly in a field of 1000 m×1000 m. The sink node, and sensor nodes are stationary after being deployed in the field. Furthermore, the sink node is located at (1000, 500) m. All the later experiments are done for both homogeneous and heterogeneous node energy distributions on a custom Matlab simulator. Data traffic is generated according to a passion process with mean parameter σ. In addition, we choose a harsh wireless channel model, which includes shadowing and deep fading effects, as well as the noise [39]. In this simulation, the case of Chipcon CC2420 radio transceiver is taken into consideration [39]. The simulation parameters are listed in Table 2.

In the later experiments, we use the combination (α = 2, β = 2, γ = 1, λ = 1, and φ = 12), the evaluation result shows this combination is the best for all experiments.

6.3 Simulation results

To verify the feasibility and effectiveness of our proposal, its performance is compared in terms of Network Lifetime, Energy Imbalance Factor, and Throughput Ratio, with the proposed protocols in [4 , 26–29] for homogenous and heterogeneous networks. In addition, we compare our method of how to report information about the detected objects from each source node to the sink with the previous work stated in [24].

6.3.1 Reporting method evaluation

In this experiment, the performance of proposed method of how to report information about the detected objects from each source node to the sink is compared to the LR-based algorithm [24] at target reliability equal to 0.9. Assuming that multi-objects are moving in the environment and detected by four sensor nodes S1, S2, S3, and S4 as shown in Fig. 1. The scenario of the objects movement is as follows:

Five objects move from S₁ to S₂.

Three objects move from S₂ to S₃.

Two objects move from S₂ to S₄.

Two objects move from S₃ to S₄.

As can be seen in Fig. 1a, due to the hard assumption in the LR-based algorithm [24], only information about objects movement from S₃ to S₄ are reported by S₄ to the sink node. Information about other objects movement is not reported to the sink node. As can be seen in Fig. 1b, in our approach, information about all detected objects is reported to the sink node. Therefore, the object tracking method in our work is more efficient than the LR-based algorithm [24]. As described above, the object tracking method in LR-based algorithm [24] is not efficient. Therefore, in all later experiments to compare the performance of our approach with the LR-based algorithm [24], it is considered that the network consisting of sensor nodes only and each node that detects an object will send its information to the sink node.

6.3.2 Network lifetime evaluation for homogenous and heterogeneous networks

In this experiment, the performance of the proposed SWARM approach is evaluated in terms of network lifetime for both homogenous and heterogeneous networks compared to the LR-based algorithm [24], EBRP [4], ACO proposed in [26], TADR [27], CLR-Routing [28], and SEB [29] under different traffic rate σ. The initial energy on each sensor node is 125 mJ for homogenous network while it is between 100 and 125 mJ randomly for heterogeneous network. Figures 2 and 3 show the variation of network lifetime with respect to different traffic rate σ for homogeneous and heterogeneous networks respectively. From the figures it can be found that as the value of σ increases, the network lifetime decreases. Since the network traffic increases with the increment of σ, the relay load of nodes increases linearly which is the main reason behind decrease of lifetime. However, the figures show clearly that our SWARM algorithm enhances significantly the network lifetime comparing with the others for both homogeneous and heterogeneous network. This means that our SWARM algorithm balances the network energy consumption more effectively than the others.

6.3.3 Network reliability evaluation for homogenous and heterogeneous network

In this experiment, the performance of the proposed SWARM approach is evaluated in terms of TR for both homogenous and heterogeneous networks compared to the LR-based algorithm [24], EBRP [4], ACO proposed in [26], TADR [27], CLR-Routing [28], and SEB [29] for homogeneous and heterogeneous network under different traffic rate σ. The initial energy on each sensor node is 125 mJ for homogenous network while it is between 100 and 125 mJ randomly for heterogeneous network. The TR against different traffic rate σ for both homogeneous and heterogeneous networks is depicted in Figs. 4 and 5 respectively. Clearly, our SWARM algorithm achieves the highest TR compared to the others. This is because it forwards the data packets toward the sink in a more reliable way and alleviates the possible buffer overflow.

6.3.4 Energy balancing evaluation for homogenous and heterogeneous networks

In this experiment, the performance of the proposed SWARM approach is evaluated in terms of energy balance for both homogenous and heterogeneous networks compared to the LR-based algorithm [24], EBRP [4], ACO proposed in [26], TADR [27], CLR-Routing [28], and SEB [29]. The initial energy on each sensor node is 125 mJ for homogenous network while it is between 100 and 125 mJ randomly for heterogeneous network. In this set of experiments, it is assumed that the traffic rate σ equal 5. The EIF was calculated during running time to find the network’s balance efficiency. Figures. 6 and 7 present the variation of EIF over simulation time for homogeneous and heterogeneous networks respectively. As shown in the figures, EIF increases with more running time. The augmentation of the EIF is due to the high use of the sink node neighbors comparing to the others, which reduce the average residual energy. However, according to the results in Figs. 6 and 7, it is obvious that the EIF of our SWARM algorithm is the minimum among those of all the others. It means that in our SWARM algorithm, the energy of the entire nodes in the network is close to the average energy in contrast to the others. That’s to say, our SWARM algorithm can balance residual energy among sensor nodes efficiently.

6.3.5 Average end-to-end delay evaluation for homogenous and heterogeneous networks

In this experiment, the performance of the proposed SWARM approach is evaluated in terms of end-to-end delay for both homogenous and heterogeneous networks compared to the LR-based algorithm [24], EBRP [4], ACO proposed in [26], TADR [27], CLR-Routing [28], and SEB [29] under different traffic rate σ. The initial energy on each sensor node is 125 mJ for homogenous network while it is between 100 and 125 mJ randomly for heterogeneous network. Figures. 8 and 9 show the average end-to-end delay under different traffic rate σ for homogeneous and heterogeneous networks respectively. From the results, it is observed that the end-end-delay increases, as the traffic rate increases. A higher traffic rate causes more queuing delay, which raises the end-to-end delay. However, it is clear that our SWARM approach giving the lowest end-to-end delay compared with the others. This is because, our SWARM approach forwards the data packets toward the sink in a more reliable way and alleviates the possible buffer overflow, which decreases the packet loss and retransmissions and hence the end-to-end delay.

7 Conclusions

In this work, an efficient data reporting method for object tracking in WSNs is proposed. In data reporting phase, the proposed approach not only reduces the energy consumption but also balanced it among sensor nodes to extend WSN lifetime. At the same time, the sensed data delivered to the sink with the highest possible reliability and minimum buffer overflow. This work first formulates the problem as 0/1 integer programming problem, and then SWARM intelligence is proposed to solve the optimization problem. The performance of proposed method compared with the previous works which are related to our topic such as LR-based object tracking algorithm, EBRP, ACO, TADR, SEB, and CLR-Routing are evaluated and analyzed through simulation. Simulation results demonstrated that the method of how to report information about the detected objects from each source node to the sink in proposed approach outperformed the LR-based object tracking algorithm. Finally, simulation results showed that our approach is robust; achieve longer lifetime, and giving lower end-to-end delay compared to the previous works for both homogenous and heterogeneous networks.

References

Ilyas

and Mahgoub

, Handbook of Sensor Networks, CRC Press, London, 2005, pp. 117–140.

Ammari

H.M.

, Challenges and Opportunities of Connected k Covered Wireless Sensor Networks-From Sensor Deployment to Data Gatherings, Springer, 2009.

Pottie

G.J.

and Kaiser

W.J.

, Wireless integrated network sensors, Communications of ACM43(5) (2000), 51–58.

Ren

, Zhang

, He

, Lin

and Das

S.K.

, EBRP: Energy-balanced routing protocol for data gathering in wireless sensor networks, Trans on Parallel and Distributed Systems22(12) (2011), 2108–2125.

Liu

, A transmission scheme for wireless sensor networks using ant colony optimization with unconventional characteristics, IEEE Communications Letters18(7) (2014), 1214–1217.

Campobello

, Leonardi

and Palazzo

, Improving energy saving and reliability in wireless sensor networks using a simple CRT-based packet-forwarding solution, IEEE/ACM Transactions on Networking20(1) (2012), 191–205.

Zonouz

, Xing

, Vokkarane

and Sun

, Reliability-oriented single-path routing protocols in wireless sensor networks, IEEE Sensors Journal14(11) (2014), 4059–4068.

Niu

, Cheng

, Gu

, Shu

and Das

, R3E: Reliable reactive routing enhancement for wireless sensor networks, IEEE Transactions on Industrial Informatics10(1) (2014), 784–794.

Kamal

A.M.

, Bleakley

C.J.

and Dobson

, Failure detection in wireless sensor networks: A sequence-based dynamic approach, ACM Transaction on Sensor Networks (TOSN)10 (2014), 35:1–35:29.

10.

Viani

, Rocca

, Benedetti

, Oliveri

and Massa

, Electromagnetic passive localization and tracking of moving targets in a WSN-infrastructured environment, Inverse Problems26(074003) (2010), 1–15.

11.

Blum

Ch.

and Merkle

, Natural Computing Series, Swarm Intelligence Introduction and Applications, Springer, Berline, 2008.

12.

McCune

R.R.

and Madey

G.R.

, Control of Artifial Swarms with DDDAS, Proc 14th Int Conf On Computational Science (ICCS), Elsevier, Vol. 29, 2014, 2014, pp. 1171–1181.

13.

Sardar

A.R.

, Singh

, Sahoo

R.R.

, Majumder

, Sing

J.K.

and Sarkar

S.K.

, An Efficient Ant Colony Based Routing Algorithm for Better Quality of Services in MANET, Springer LNCS, ICT and Critical Infrastructure: Pro, Of the 48th Annual Convention of Computer Society of India-Vol I, Advances in Intelligent Systems and Computing, Vol. 248, 2014, pp. 233–240.

14.

Rocca

, Benedetti

, Donelli

, Franceschini

and Massa

, Evolutionary optimization as applied to inverse problems, Vol. 25, pp, Inverse Problems - 25th Year Special Issue of Inverse Problems, Invited Topical Review, Vol. 25, 2009, pp. 1–41.

15.

Gunes

, Sorges

and Bouazzi

, ARA-the ant-colony based routing algorithm for manets, Int Workshop on Ad Hoc Networking, 2002, pp. 79–85.

16.

Viani

, Robol

, Giarola

, Benedetti

, De Vigili

, and Massa

, Advances in wildlife road-crossing early-alert system: New architecture and experimental validation, 2014 European Conference on Antennas and Propagation (EUCAP), The Hague, The Netherlands, 2014, pp. 6–11.

17.

Viani

, Rocca

, Lizzi

, Rocca

, Benedetti

and Massa

, WSN-based early alert system for preventing wildlife-vehicle collisions in Alps regions, pp, International Conference on Electromagnetics and Advanced Applications (ICEAA 2011), Torino, Italy, 2011, pp. 106–109.

18.

Eswari

and Vanitha

, A novel rule based intrusion detection framework for wireless sensor networks, Proc of IEEE Int Conf Information Communication and Embedded Systems (ICICES) (2013), pp. 1019–1022.

19.

Chen

Y.-L.

, Lin

Y.-C.

and Sun

T.-C.

, A Prediction Scheme for Object Tracking in Grid Wireless Sensor Networks, Proc of IEEE 7th Int Conf Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS)2013, pp. 360–364.

20.

Mahboubi

, Momeni

, Aghdam

A.G

,, Sayrafian-Pour

and Marbukh

, An efficient target monitoring scheme with controlled node mobility for sensor networks, IEEE Trans Control Systems Technology20(6) (2012), 1522–1532.

21.

Chen

C.-C.

and Liao

C.-H.

, Model-based object tracking in wireless sensor networks, Wireless Networks (WINET)17(2) (2011), 549–565.

22.

Liu

, Zhang

and Ma

, Optimal node selection for target localization in wireless camera sensor networks, IEEE Trans, Veh Technol59(7) (2010), 3562–3576.

23.

Liu

, Liu

, Cui

, Xu

and Qian

, MOLTS: Mobile object localization and tracking system based on wireless sensor networks, In Proc IEEE 7th Int Conf on Networking, Architecture and Storage (NAS)2012, pp. 245–251.

24.

Line

F.Y.S.

and Lee

C.T.

, An energy-efficient lagrangean relaxation based object tracking algorithm in wireless sensor networks, sensors, 2010, pp. 8101–8118.

25.

Guan

X.H.

, Zhai

Q.Z.

and Lai

, New lagrangian relaxation based algorithm for resource scheduling with homogeneous subproblems, Journal of Optimization theory and Applications, Springer113 (2002), 65–82.

26.

El Ghazi

, Ahiod

and Ouaarab

, Improved Ant Colony Optimization Routing Protocol for Wireless Sensor Networks, in Noubir

P.G.

and Raynal

, (Eds.): NETYS, Springer, Heidelberg, 2014, pp. 246–256.

27.

Ren

, Das

S.K.

and Lin

, Traffic-aware dynamic routing to alleviate congestion in wireless sensor networks, IEEE Transactions on Parallel and Distributed Systems22(9) (2011), 1585–1599.

28.

Yaessad

, Bouallouche

and Aissani

, A cross-layer routing protocol for balancing energy consumption in wireless sensor networks wireless pers, Commun, 81 (2014), 1303–1320, Springer.

29.

Qian

, Chen

, Wu

and Cheng

, Swarm Intelligence Based Energy Balance Routing For Wireless Sensor Networks, Proc of the 2nd Int Symposium on Intelligent Information Technology Application, vol. 22008, pp. 811–815.

30.

Baoshu

and Hui

, A reliability transmission routing metric algorithm for wireless sensor network, Proc IEEE Int Conf E-Health Networking, Digital Ecosystems and Technologies (EDT), vol. 1 (2010), pp. 454–457.

31.

Kootkar

S.B.

, Reliable sensor networks, M.S. thesis, Dept Comp Eng, TU Delft Univ, Delft, Netherlands, 2008.

32.

Cheng

, Nia

, Cao

, Das

S.K.

and Gu

, QoS aware geographic opportunistic routing in wireless sensor networks, IEEE Trans On Parallel and Distributed Systems, 2014.

33.

Fdili

, Fakhri

and Aboutajdine

, Impact of queue buffer size awareness on single and multi service real-time routing protocols for WSNs, International Journal of Communication Networks and Information Security4 (2012), 104–111.

34.

http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/

35.

Sharvani

G.S.

, Cauvery

N.K.

and Rangaswamy

T.M.

, Different types of Swarm Intelligence algorithm for routing, In Proc of IEEE Int Conf on Recent Technologies in Communication and Computing (ARTCOM), Kottyam, Kerala, India, pp 2009, 604–609.

36.

Zuniga

and Krishnamachari

, An analysis of unreliability and asymmetry in low-power wireless links, ACM Trans Sensor Networks3(2) (2007), 63–81.

37.

Verma

V.K.

, Singh

and Pathak

N.P.

, Analysis of scalability for AODV routing protocol in wireless sensor networks, Optik—International Journal for Light and Electron Optics125(2) (2014), 748–750.

38.

Jian

, Cloud Model and Ant Colony Optimization Based QoS Routing Algorithm for Wireless Sensor Networks, Wu

, (Ed.):, International Conference on WTCS 2009, AISC 116Springer, Heidelberg, 2012, pp. 179–187.

39.

MicaZ wireless module. [Online]. Available: http://www.xbow.com/Products/Productpdffiles/Wirelesspdf/MICAzDatasheet.pdf.