Operation Research Based Techniques in Wireless Sensors Networks ()
1. Introduction
Developments in wireless communication and electronics miniaturization made it possible to develop wireless sensor networks (WSNs), which consisted of network of several small collaborative electronics devices, with the capacity of collecting and routing information. These sensing devices are named nodes and comprise small memory capacity and processing as well as tiny energy storage. Currently, wireless sensor networks are largely used in different areas of industry and military applications. The usage of WSNs is increasing and escalates with it the different energy harvesting problems, routing issues and sensors localization problems. In fact, due sensors limited energy capacity, the development of WSNs faces several constraints: how to increase network lifetime with such limited capacity? How to continuously route information/data effectively? How to ensure maximum network coverage and reliable communications? The Wireless Sensor Networks (WSNs) may consist of hundreds or thousands of sensors. These nodes have the sensing ability and transmit data to other nodes or base stations. Every node has specific task and small power storage capacity as per its miniaturization. Different nodes are located in different area to ensure maximum coverage/sensing. The nodes have possibility to collect and route/transfer the data and take “small” decision. Base-station(s) are special nodes which can be stationary or mobile. It connects WSNs to specific network domain through the internet. Many recent researches proposed approaches to preserve energy and power consumptions in a WSNs as well as routing protocols to accommodate WSNs constraints. Several survey articles have been suggested in the past to present different techniques which address WSNs problems: nodes, scheduling, and energy harvesting, routing protocols and nodes localization [1] [2] [3] [4] , and [5] . None of these surveys have emphasis on the Operation Research approaches in the WSNs. It is known that Operation Research (OR) has been widely used in different areas to solve optimization problems [6] ; such as improving network performance and maximizing lifetime of system as shown in details in Table 1.
Indeed, the operation research field is suggesting extremely sophisticated approaches and techniques to solve huge networks problems; in which WSNs can be seen as a special case of problem than can be tackled by graph theory. The node scheduling problem in WSNs also is a scheduling problem in operation research perspective, which can be solved using mixed integer programming techniques. Actually, this survey suggests the most research techniques in operation research areas, which have been proven to be efficient in solving the WSNs problems. In this article, we present operation research techniques used to solve WSNs problems into four categories: routing protocols, energy saving techniques, network nodes allocation and network reliability. Different Operational Research techniques are presented and discussed in details here, including graph theory based techniques, linear programing and mixed integer programming related approaches. The percentage usage of each OR technique in the surveyed papers is shown in Figure 1.
In order to validate the proposed methods in the surveyed papers, authors have used two approaches: Simulation and Theoretical analysis. Table 2 and Figure 2 show the number of surveyed paper with the used corresponding validation approach.
![]()
Table 1. OR techniques and their area of application.
2. Operations Research Techniques in Routing
Routing in wireless sensor network (WSNs) is a challenging task because of its many different characteristics over traditional wireless network. Whereas this later uses an addressing scheme, WSNs cannot use classical IP based routing due to the huge number of sensors nodes deployment. Other issues with WSNs
![]()
Figure 1. Percentage usage of OR techniques.
![]()
Figure 2. Number of references using the corresponding validation methods.
![]()
Table 2. References using validation approach.
consist of data redundancy and limited power resource. Due to such differences many routing protocols for WSNs using Operation Research tools have been proposed. Some protocols are based on single shortest path, multipath and spanning tree models, while others use flow models with its range of different minimum cost/ maximum multicommodity flow models.
In general, the flow problem in WSNs is modelled as follows:
(1)
(2)
where t (respectively T) is a time instance (respectively the network lifetime), N the set of sensors, Ni the set of neighboring nodes of i, xij the flow over the edge ij (that is to say the data transmitted over this link), yi the data generated by node i, eij the energy consumed in transmitting a unit flow and Ei the initial energy of the sensor.
The flow conservation constraint Equation (1), shows that the total amount of flow that a sensor receives plus the amount of data that it generates is equal to the amount of information that it transmits. The second constraint given in Equation (2) is the capacity constraint, which is related to energy. This constraint implies that the energy consumed by a sensor for transmitting the flow through- out the lifetime of the network must be less than its initial energy. In standard network flow problems this constraint is usually related to link capacity. In this context, authors in [7] proposed push-relabel method of Max-Flow technique to reduce message complexity and satisfy real-time requirements. They modeled WSNs as a network G= (V, E) whose nodes V are sensors and E is the set of the full-duplex directed communication edge. So, the solution for solving Max Flow problem is to find the max-flow from source node s to the sink node t that satisfies some constraints, which can be formulated as follows;
Maximize
Subject to:
(3)
However, authors modified the objective function of Max-flow problem to add some other objectives such as, reducing message and time overheads and being adaptive to network changes. To achieve these objectives, they proposed a new algorithm that consists of several heuristics and based on push-relabel method (GPR) [8] and two-phase push-relabel (2PPR) [9] . Through extensive simulation they showed that the new proposed algorithm achieves near optimality with little fraction of messages needed for the other existing algorithms, whereas near optimal flow is almost same as the optimal max flow.
Another technique of OR that is related to combinatorial optimization problem has been used in [10] . Authors used quadratic assignment problem (QAP) [11] to find an optimal path in WSNs between sensor nodes and sink in order to minimize the energy consumption during transmission and reception. The QAP has been modelled as follows: Let the set of nodes are
and three nxn matrices
,
and
the quadratic assignment problem with coefficient matrices F, D and C shortly denoted by QAP can be stated as follows:
(4)
Subject to
(5)
(6)
where fik denotes the amount of flow between facilities i and k, djl denotes the distance between location j, l and Cij denotes the cost of locating facility i at location j. In this paper authors used flow distance products fik djl instead of considering dimensional array. Each sensor node in the proposed algorithm sends its ID named (Ids) by flooding it to its neighbor nodes; consequently, an identification table is constructed at each node. Two entries exist in this table, sensor identification denoted Sid and sink or destination identification denoted Did. Based on the data in the table, a node can have many behaviors. In case of no data in the table, it means a dead node or out of range node with no neighbor. If only Sid data exists in the table, it means that the node is a passing path for all nodes and it is not an interface node. However, if only Did data is available, this means that the node can only send the data to sink and is not able to route every nodes or network. The last case is, if both Sid and Did data exist in the table, it means that the node is able to communicate with network and it is near a sink. Moreover, it can play a role of an interface node. When a node needs to send data, it searches its table entry and try to locate a sink ID, if no such information exists, it floods data to neighbors until it reaches interfaced sensor who will take the task to forward data to the sink, and the scenarios is repeated until an optimal path is found.
In terms of routing techniques a number of routing protocols have been suggested. In [12] , authors presented different type of multipath energy efficient protocol in WSNs. They highlighted the benefits of multipath routing to name: reliability and fault-tolerance, load balancing, QoS Improvement, reduced delay and bandwidth aggregation. Then, they discussed the main aspects of multipath routing including path discovery, traffic distribution routing and path maintenance.
A number of multipath protocols for WSNs are reviewed including AODVM [13] , MR2 [14] , LIEMRO [15] , and EECA [16] where a comparison between single path and multipath routing protocols is presented.
Another multipath routing protocol named ESMRP is proposed in [17] . It uses a load balancing protocol to transfer data from source to destination (sink). During primary route discovery and with use of HELLO packets, ESMRP choses the best next hope based on the node strength which can be calculated based on three factors: residual energy, available buffer size and signal to noise ratio.
A diffusion algorithm [18] is used to ensure that multiple disjoint paths are calculated. To calculate alternate route, sink sends an RREQ back to the source, then a load balancing algorithm is used to benefit from multiple paths. Using simulation, the performance of ESMRP is compared to Robust and Energy Efficient Multipath Routing Protocol (REER) [19] . Authors showed that ESMRP leads REER in terms of average delivery ratio, delay and average energy consumption.
3. Operations Research Techniques in Energy Saving
The energy saving is one of the main focus in WSNs research. By nature, the nodes have small power capacity; where a drained node will cause network failure. Saving energy could consists of turning off the sensor or make it idle for certain amount of time while keeping the network connectivity. Researches in WSNs focus on reducing the power consumption and optimizing energy harvesting. A general model for the energy saving for the WSNs could be a coverage problem:
(7)
(8)
in which, the objective function is to minimize the total cost of activating sensors, where
represents the cost vector of using sensor, the xi represents the sensor i. Also
, k sensors could cover one region i. The Sensor i working at energy level l is represented by variable
. Thus, this problem is also named k-coverage problem. The different WSNs layout suggests having one or many base station(s) that receive(s) messages from nodes. In fact, many of the research work addressed single static base station [20] ; thus the sensor nodes which are one-hop away from a base station consume their energy faster than other nodes in the network; because those nodes play roles of rely, and thus forward messages originating from many other nodes. The energy is then quickly consumed and the network maybe inactive or disconnected [21] . Therefore, in [22] , researchers suggested using multiple mobile base stations to increase the lifetime of the sensor network. In fact, using more base stations rather than one will reduce the number of hop count of each sensor node in the network. It actually decreases the energy consumption per delivered message. Authors used a linear programming model to successfully find the locations of the base stations. They showed a significant increase in a network lifetime for medium size networks.
To increase the network lifetime, authors in [23] addressed the coverage problem in wireless sensor networks with adjustable sensing range. The sensor has an adjustable sensing range, which will cover a limited area. The problem was formulated as the adjustable range set covers problem, which is NP-com- plete problem and suggested heuristics, which looks for the maximum number of set covers and the ranges related with each sensor, such that each sensor set covers all the targets. They used integer programming modeling and greedy approaches, and showed that adjustable sensing ranges have vast effect on network lifetime. In WSNs relay stations plays an important role in receiving and forwarding message from node to base station, which help the sensors to reduce energy consumption. Because the relay stations could have high-energy autonomy (solar or storage), WSNs lifetime could be increased by having an adequate number of relay stations. Authors in [24] suggested using different relay stations, in which they proposed an integer binary linear programming model and find optimally the minimum energy relay placement problem, in view to reduce energy drainage and preserving signal quality and reduce noise rate. In other research works, the general model for the energy-preserving problem in WSNs is stated as a strong minimum energy topology (SMET), with the objective to reduce the energy consumption while preserving network connectivity. The problem has been proven to be NP-Hard by [25] . Authors in [25] suggested using the minimum spanning tree algorithm as well as a greedy heuristic to assign energy to nodes. The minimum spanning tree (MST) is expanded by the node with highest power, which avoids energy wasting for the others nodes, in which power is assigned to nodes that can reach the farthest children in the MST. Nodes consume energy while transmitting data. To reduce energy consumption, some techniques select the best node from which should data transit. Many graph- based techniques have been suggested to find the “Best” node neighborhood, such as Voronoi Diagram or Relative Neighbor Graph by [26] . In such approaches, the node can reduce its energy so as to be able to reach only its best neighbors. In [27] , authors suggested a mixed integer-programming model to solve the problem of scheduling communications in wireless sensor networks to ensure battery preservation through the use of the sleeping mode of sensors. Authors proposed to save battery power by scheduling communications so that sensors spend as much time as possible in their sleep state. They proposed to make sensors of a cluster communicate in a token ring so that only one sensor sends data at a time, and only one other sensor receives them; while all other nodes are in the sleep mode by finding the maximal clique: all nodes in the same cluster are adjacent, and no other sensor is adjacent to all sensors in the cluster. In [28] , authors suggested maximizing the lifetime of static WSNs through routing procedures. They modelled the routing problem as a linear programming problem, with the objective function to maximize the network lifetime. Their algorithm focuses on finding the shortest paths for routing. They save energy by considering the information flow exchanged between sensors. Similarly, in [29] , authors suggested to reduce the energy consumed by reducing the transmission power of each sensor. Their algorithm finds the connected minimal weighted dominated set, and used it as a support over sensors to route the data, and then idle the remaining nodes. In [30] , authors presented a survey on optimization techniques to address several problems in WSNs, such as coverage, topology control, mobility, scheduling and routing. In particular, authors noted that in several investigations, the time-slot allocation problem (scheduling) is formulated as a graph-coloring problem, to model the fact that two edges adjacent to the same sensor cannot use the same time slot.
4. Operations Research Techniques in Network Design
The WSNs localization or deployment problem is concerned with minimizing the number of installed sensor nodes to cover/satisfy all the area. The localization problem could be seen as the museum problem [31] which is known to be NP-hard. Authors in [31] suggested an approximate geometry algorithm to solve this problem. The layout problem in WSNs has close integer linear model as the energy model:
(9)
In which, the objective function would be to minimize the total cost of activating sensors, where
represents the cost of using sensors,
represents the sensor I,
is the set of nodes than can cover target region and k sensors could cover one region i. The constraints shows that many elements of
will cover region i.
In [32] authors modelled the layout problem in WSNs as Sensor Location Problem (SLP). The SLP problem is defined as follow: Given a planar region, a given number of sensor nodes need to be positioned so that the probability of detecting an event in this region is maximized. The objective function aims to minimize the maximum of this product and used Voronoi based heuristic to find disconnected regions. Authors in [33] suggested constructing the Voronoi diagram for the set of nodes in order to compute the maximal breach path, which is the path that minimizes the maximum distance between every point on the path and its nearest sensor node. In [34] authors suggested Unit Disk Graph (UD) [35] to model WSNs by using a variant of connected dominant set. A minimum connected dominating set of a graph G is a connected dominating set with the smallest possible size among all connected dominating sets of G, and the connected domination number of G is the number of vertices in the minimum connected dominating set (MCDS). Thus, sensors are represented as vertices and a unit disk centered at the sensor represents the sensing covering area of a sensor. Two nodes are connected with an edge if a node is within the coverage area of the other node. The MCDS problem is NP hard [36] for UD graph. Authors suggested a quadratic algorithm to determine MCDS. The technique is based on computing convex hulls of sensors nodes. Authors in [37] proposed a distributed algorithm for this problem with pseudo quadratic time complexity.
Finding the best location of the base station or the sink was also studied, since it affects greatly the energy consumption of the related nodes in data transmission and routing. In [38] , the authors provide a mathematical programming model to minimize the distance of the sinks in order to find the optimal location of the sink. In [39] , authors studied the moving sink location and network efficiency by formulating the problem into an efficient linear programming model.
5. Operations Research Techniques in Reliability
Reliability is defined as the ability of WSNs to ensure energy efficiency and reliable communication between nodes in resource constrained environment. Many OR techniques have been proposed in this context. In [40] , two problems have been discussed to save energy. The first one is the collection of data and the second one is how to transmit that data in an interference-free manner. More technically, it is the problem of finding a minimum latency aggregation tree and transmission schedule in WSNs. In WSNs terminology, it is known as Minimum Latency Aggregation Scheduling (MLAS) problem [41] which has been proven to be NP-Complete. In WSNs data is collected by sensor nodes and is sent towards a selected node called the sink along tree’s edges of a spanning tree (called convergecast). Authors presented an algorithm that deals with the problem of Time division multiple access (TDMA) scheduling for convergecast with aggregation.
Problem Formulation:
Given a wireless network represented by a graph
, and a sink node
, a valid schedule for G to be a spanning tree T of G rooted at and directed towards the sink node s, and an assignment
of time slots to the nodes of the graph such that:
1)
2)
The first condition guarantee the aggregation of data, and the second one ensures that transmissions are free of interference.
The latency of a valid schedule A for a graph G is denoted by
. So MLAS problem can be formulated as follows: Given a graph
, find a valid schedule of minimum latency for G. Authors proposed a new algorithm for building an aggregation tree named Degree-Constrained Aggregation Tree (DCAT) and also presented two new scheduling algorithms, named WIRES-G (where G stands for Greedy) and DCAT- Greedy. To ensure free interference, authors imposed that a node transmits exactly once, after all its children have transmitted. To determine a potential parent of a node, the one with smallest degree in the graph is chosen. To do so, the proposed algorithm uses Breath-First-Search (BFS) technique to traverse the graph and the nodes that are one-hop closer to the sink are chosen as potential parents. Two other scheduling algorithms have been proposed. The first one is called WIRES-G, which is an improvement version of WIRES algorithm given in [42] . WIRES-G, allows more nodes to be scheduled per time slot. To find those nodes, the algorithm traverses all the eligible nodes that were not scheduled to transmit and try to find parents for them with the lowest degree in the graph, which will result in the construction of a new aggregation tree. The second scheduling algorithm is called DCAT-Greedy. It combines the DCAT algorithm with the greedy-scheduling procedure to try to achieve lower latency. To evaluate the performance of the DCAT tree building and the scheduling algorithms, a comparison study with BSPT-WIRES [17] using simulation is presented. It showed that the proposed algorithms have significant lower latencies compared to BSPT-WIRES. Furthermore a model of reliability of two different types of sensor nodes is presented in [43] . The first one is the Energy harvesting sensor and the second one is a battery-powered sensor node. Authors discussed a wireless link reliability models for each type of sensor nodes, where effects of different parameters, such as battery lifetime, shadowing, noise, and location uncertainty, are considered for analyzing the wireless link reliability. A performance comparison of different type of routing algorithm using end-to-end path reliability and number of hops has also been covered in this study. The extension of the network lifetime of WSNs issue has been addressed in [44] . Two categories of sensor nodes are used in this study, one equipped with renewable energy sources (called primary nodes) and the other equipped with conventional chemical batteries (called secondary nodes). Authors attempted to construct hierarchical network architecture. Then a framework of network optimization is proposed. The target of this framework is to, maximize lifetime and minimize the average number of packet hops for WSNs networks. Authors used Linear Programming (LP) techniques to optimize the flow assignment (traffic load balancing) between a node and its neighbors within its range of coverage, while maximizing the node lifetime and minimizing the averages number of hops from source to the sink. Authors stated that the problem of primary node assignment is equivalent to that of maximizing network lifetime. They formulated the following linear programming problem: for primary node assignment problem constraints:
Maximize Tp subject to:
(10)
(11)
(12)
(13)
(14)
where:
TP: WSNs maximum lifetime for P primary nodes,
N: Number of nodes of the WSNs,
P: Number of primary nodes of the WSNs,
Lij If Lij = 1,
, otherwise Lij = 0 and Lij = Lji,
Dij: Physical distance between node i and node j,
Fi: Data flow from i to j,
Ii: A binary variable; if Ii = 1, node i is a primary one,
R: Node transmission data rate,
M: a large number,
Erx: Energy consumption to receive a packet,
Etx: Energy consumption to transmit a packet,
Ec: Activity energy consumption (per time unit),
Ei: Initial node i energy.
For the network flow assignment problem, the constraints are the same as primary node assignment problem however; the objective function is changed to:
(15)
After going through primary node and flow assignment optimization, both lifetime and number of packet hops in the WSNs are optimal. To validate the results of the optimization techniques, authors conducted simulation with different scenarios, and a close similarity results are seen between simulation and using mathematical expression calculation.
6. Conclusion
In this paper, we presented a survey of some current works involved in routing, reliability, energy saving and node localization issues in WSNs along with their corresponding Operation Research optimization techniques solutions. A concise distribution of OR techniques along their application has been provided. Also, methods of validating the suggested techniques using whether, simulation or theoretical analysis alone, or both have been highlighted.
7. Open Issues
Like in many topics, there are always issues that have not been addressed totally or sufficiently, and WSNs is one of them. The uncertainty about environment and system itself is considered as one of the most noticeable properties of WSNs and one of the challenging issues in WSNs. It comprises data delivery, nodes location and event detection. Despite that some models have been suggested to address this issue; they are mainly based in probabilities of these events. The reason for not including such issue is due to the nature of WSNs where the measurement of the distribution of events is considered as a difficult task. The analysis of network traffic is considered as a feasible technique for WSNs anomaly detection, more emphasis should be given to study sensor node failure and malicious attacks. Because of the low probability events of malicious attacks, high false alarm rates are not accepted in WSNs. So, designing an extremely low false alarm anomaly detection system is a challenging task. In case of network anomaly detection, dealing with it physically by sending someone to identify problem or taking some measures to recover from the possible damage is another challenging task. In terms of security, we found that most of the previous work was assuming a safe environment where sensors communicate with base station without any consideration of attacks of this later. However, this assumption is not always true especially where base station contains a critical data such as healthcare or security data. Thus, a study of WSNs under a compromised base station should be given interest. Also, it is highly needed to study routing protocol security with mobile WSNs. Scalability is considered, as an important criterion for WSNs. Nodes may die overtime and new ones are added, which result in changes of the node density and topology, so any design of WSNs should adapt quickly to these changes, work that is lacking in theoretical studies. With respect to the combination of QoS with scalability, energy saving, security and coverage problems, there are several prospective that have not been explored such as deployment problem in case of presence of obstacles, link reliability and sink security.
Another important issue in WSNs is the gap that exists between theoretical studies and practical implementation and fusing the two is not a straightforward task, thus a lot of work needs to done in this direction. In fact, WSNs represents an attractive research area with a wide range of challenges that still need to be addressed.
Acknowledgements
This research was supported by Prince Sultan University-RTC (Grant No. GP- CCIS-2013-11-17).