Operation Research Based Techniques in Wireless Sensors Networks ()

Ahmed Redha Mahlous^{}, Mohamed Tounsi^{}

Department of Computer Science, Prince Sultan University, Riyadh, KSA.

**DOI: **10.4236/cn.2017.91003
PDF HTML XML
1,724
Downloads
3,718
Views
Citations

Department of Computer Science, Prince Sultan University, Riyadh, KSA.

In recent years, we have seen an increasing interest in developing and designing Wireless Sensor Networks (WSNs). WSNs consist of large number of nodes, with wireless communications and computation abilities that can be used in variety of domains. It has been used in areas that have direct contact with monitoring and gathering data, to name few, health monitoring, military surveillance, geological monitoring (Earthquakes, Volcanoes, Tsunami), agriculture control and many more. However, the design and implementation of WSNs face many challenges, due to the power limitation of sensor nodes, deployment and localization, data routing and data aggregation, data security, limited bandwidth, storage capacity and network management. It is known that Operation Research (OR) has been widely used in different areas to solve optimization problems; such as improving network performance and maximizing lifetime of system. In this survey, we present the most recent OR based techniques applied to solve different WSNs problems: the node scheduling problem, energy management problems, nodes allocating issues and other WSNs related complex problems. Different Operational Research techniques are presented and discussed in details here, including graph theory based techniques, linear programing and mixed integer programming related approaches.

Keywords

Wireless Sensor Network, Operation Research, Routing Protocols, Energy Saving, Mixed Integer Programming

Share and Cite:

Redha Mahlous, A. and Tounsi, M. (2017) Operation Research Based Techniques in Wireless Sensors Networks. *Communications and Network*, **9**, 54-70. doi: 10.4236/cn.2017.91003.

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:

$\underset{j\in {N}_{i}}{{\displaystyle \sum}}{x}_{ij}\left(t\right)=\underset{j\in {N}_{i}}{{\displaystyle \sum}}{x}_{ij}\left(t\right)+{y}_{i}\left(t\right)\text{}\forall i\in N,\forall i\in {N}_{i}\in T$ (1)

$\underset{t\in T}{{\displaystyle \sum}}\underset{j\in {N}_{i}}{{\displaystyle \sum}}{x}_{ij}\left(T\right)\ast {e}_{ij}\le {E}_{i}\text{}\forall i\in N,\forall j\in {N}_{i}$ (2)

where t (respectively T) is a time instance (respectively the network lifetime), N the set of sensors, N_{i} the set of neighboring nodes of i, x_{ij} the flow over the edge ij (that is to say the data transmitted over this link), y_{i} the data generated by node i, e_{ij} the energy consumed in transmitting a unit flow and E_{i} 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 $\left|f\right|$

Subject to:

$\begin{array}{l}{{\displaystyle \sum}}^{\text{}}{f}_{ij}-{{\displaystyle \sum}}^{\text{}}{f}_{ji}=\{\begin{array}{l}\left|f\right|\text{}i=s\hfill \\ 0\text{}\forall i\in V-\left\{s,t\right\}\hfill \\ -\left|f\right|\text{}i=t\hfill \end{array}\\ 0\le {f}_{ij}\le {c}_{ij}\text{forall}\left(i,j\right)\in E\left(\text{Capacityconstra}\mathrm{int}\right)\end{array}$ (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 $N=\left\{1,2,3,\cdots ,n\right\}$ and three nxn matrices $F=\left({f}_{ij}\right)$ , $D=\left({d}_{ij}\right)$ and $C=\left({c}_{ij}\right)$ the quadratic assignment problem with coefficient matrices F, D and C shortly denoted by QAP can be stated as follows:

${\mathrm{min}}_{x\in X}\underset{i=1}{\overset{n}{{\displaystyle \sum}}}\underset{j=1}{\overset{n}{{\displaystyle \sum}}}\underset{k=1}{\overset{n}{{\displaystyle \sum}}}\underset{l=1}{\overset{n}{{\displaystyle \sum}}}{f}_{ik}{d}_{jl}{x}_{ij}{x}_{kl}+\underset{i=1}{\overset{n}{{\displaystyle \sum}}}\underset{j=1}{\overset{n}{{\displaystyle \sum}}}{c}_{ij}{x}_{ij}$ (4)

Subject to

$\underset{i=1}{\overset{n}{{\displaystyle \sum}}}{x}_{ij}=1,\text{}i\in N$ (5)

$\underset{j=1}{\overset{n}{{\displaystyle \sum}}}{x}_{ij}=1,\text{}j\in N$ (6)

${x}_{ij}\in \{o,1\},\text{}i,j\in N$

where f_{ik} denotes the amount of flow between facilities i and k, d_{jl} denotes the distance between location j, l and C_{ij} denotes the cost of locating facility i at location j. In this paper authors used flow distance products f_{ik} d_{jl} 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 S_{id} and sink or destination identification denoted D_{id}. 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 S_{id} 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 D_{id} 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 S_{id} and D_{id} 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:

$\begin{array}{l}\text{}\mathrm{min}{C}^{\text{T}}x\\ \text{subjectto}:\underset{i\in S\left(i\right)}{{\displaystyle \sum}}{x}_{i}\ge k\end{array}$ (7)

$\begin{array}{l}\underset{l}{{\displaystyle \sum}}{x}_{i,l}\le 1\\ {x}_{i}\in {Z}_{+}\end{array}$ (8)

in which, the objective function is to minimize the total cost of activating sensors, where
${C}^{\text{T}}$ represents the cost vector of using sensor, the x_{i} represents the sensor i. Also
$S\left(i\right)=\left\{x:\text{targetregion}i\text{iscoveredbysensor}x\right\}$ , k sensors could cover one region i. The Sensor i working at energy level l is represented by variable
${x}_{i,l}$ . 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:

$\begin{array}{l}\text{}\mathrm{min}{C}^{\text{T}}x\hfill \\ \begin{array}{c}\text{subjectto}:\underset{i\in S\left(i\right)}{{\displaystyle \sum}}{x}_{i}\ge k\end{array}\hfill \\ \text{}{x}_{i}\in {Z}_{+}\hfill \end{array}$ (9)

In which, the objective function would be to minimize the total cost of activating sensors, where ${C}^{\text{T}}$ represents the cost of using sensors, ${x}_{i}$ represents the sensor I, $S\left(i\right)=\left\{x:\text{targetregion}i\text{iscoveredbysensor}x\right\}$ 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 $S\left(i\right)$ 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 $G=\left(V,E\right)$ , and a sink node $s\in V$ , 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 $A:V\to Z+$ of time slots to the nodes of the graph such that:

1) $v\in \text{children}\left(u\right)\Rightarrow A\left(u\right)>A(v)$

2) $\left(u,v\right)\in T\text{and}\left(w,v\right)\in G\Rightarrow A\left(u\right)\ne A(w)$

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 $L\left(G,A\right)={\mathrm{max}}_{v\in V}\left\{A\left(v\right)\right\}$ . So MLAS problem can be formulated as follows: Given a graph $G=\left(V,E\right)$ , 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 T_{p} subject to:

${f}_{ij}\ge 0,\text{}\forall \left(i,j\right)\in N,\text{}i\ne j$ (10)

$\underset{j=1}{\overset{N}{{\displaystyle \sum}}}{L}_{j1}{f}_{j1}=\left(N-1\right)r{T}_{p}$ (11)

$\underset{j=1}{\overset{N}{{\displaystyle \sum}}}{L}_{ij}{f}_{ij}-\underset{j=2}{\overset{N}{{\displaystyle \sum}}}{L}_{ij}{f}_{ji}=r{T}_{p}$ (12)

$\forall i\in N,\text{}i\ne 1,i\ne j$

${E}_{tx}\underset{j=1}{\overset{N}{{\displaystyle \sum}}}{L}_{ij}{f}_{ij}+{E}_{rx}\underset{j=2}{\overset{N}{{\displaystyle \sum}}}{L}_{ji}{f}_{ji}+{E}_{c}{T}_{p}\le {E}_{i}+M{I}_{i},\text{}{\forall}_{i}\in N,i\ne 1,i\ne j$ (13)

$\underset{i=2}{\overset{N}{{\displaystyle \sum}}}{I}_{i}\le P$ (14)

where:

T_{P}: WSNs maximum lifetime for P primary nodes,

N: Number of nodes of the WSNs,

P: Number of primary nodes of the WSNs,

L_{ij} If L_{ij} = 1,
$\exists \text{link}\left(i,j\right)$ , otherwise L_{ij} = 0 and L_{ij} = L_{ji},

D_{ij}: Physical distance between node i and node j,

F_{i}: Data flow from i to j,
${f}_{ij}\ge 0,$

I_{i}: A binary variable; if I_{i} = 1, node i is a primary one,

R: Node transmission data rate,

M: a large number,

E_{rx}: Energy consumption to receive a packet,

E_{tx}: Energy consumption to transmit a packet,

E_{c}: Activity energy consumption (per time unit),

E_{i}: 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:

$\underset{i=2}{\overset{n}{{\displaystyle \sum}}}\underset{j=1}{\overset{n}{{\displaystyle \sum}}}{L}_{ij}{D}_{ij}{f}_{ij}$ (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).

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | Rawat, P., Singh, K.D., Chaouchi, H. and Bonnin, M. (2013) Wireless Sensor Networks: A Survey on Recent Developments and Potential Synergies. Journal of Supercomputing, 68, 1-48. |

[2] |
Baronti, P., Pillai, P., Chook, V., Chessa, S., Gotta, A. and Hu, Y.F. (2006) Wireless Sensor Networks: A Survey on the State of the Art and the 802.15.4 and ZigBee Standards. Computer Communications, 30, 1655-1695.
https://doi.org/10.1016/j.comcom.2006.12.020 |

[3] |
Akyildiz, I.F., Wang, X. and Wang, W. (2005) Wireless Mesh Networks: A Survey. Computer Networks, 47, 445-487. https://doi.org/10.1016/j.comnet.2004.12.001 |

[4] |
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422.
https://doi.org/10.1016/s1389-1286(01)00302-4 |

[5] | Akkaya, K. and Younis, M. (2005) A Survey on Routing Protocols for Wireless Sensor Networks. Ad Hoc Networks, 3, 325-349. |

[6] | Tounsi, M. and Mahlous, A.R. (2016) A Multi-Objective Model for Optimizing Network lifetime in Wireless Sensor Network. International Journal of Computer Science and Information Security (IJCSIS), 14, 562-569. |

[7] | Homayounnejad, S. and Bagheri, A. (2015) An Efficient Distributed Max-Flow Algorithm for Wireless Sensor Networks. Journal of Network and Computer Applications, 54, 20-32. |

[8] | Goldberg, A.V. and Tarjan, R.E. (1988) A New Approach to the Maximum-Flow Problem. JACM, 35, 921-940. |

[9] | Pham, T.L., Lavallee, I., Bui, M. and Do, S.H. (2005) A Distributed Algorithm for the Maximum Flow Problem. Proceedings of the 4th International Symposium on Parallel and Distributed Computing, ISPDC, 131-138. |

[10] | Vinoba, V. and Indhumathi (2015) A Detection of Optimal Path Using Quadratic Assigment Technique in Wireless Sensor Networks. International Journal of Application or Innovation in Engineering & Management (IJAIEM), 4. |

[11] |
Lawler, E.L. (1963) The Quadratic Assignment Problem. Management Science, 9, 586-599. https://doi.org/10.1287/mnsc.9.4.586 |

[12] | Mishra, N. and Kumar, A. (2014) Comparative Analysis: Energy Efficient Multipath Routing in Wireless Sensor Network. International Journal of Computer Science and Mobile Computing, 3, 627-632. |

[13] |
Ye, Z., Krishnamurthy, S.V. and Tripathi, S.K. (2003) A Framework for Reliable Routing in Mobile Ad Hoc Networks. Proceedings of the IEEE INFOCOM, Vol. 1, San Francisco, 30 March-3 April 2003, 270-280.
https://doi.org/10.1109/infcom.2003.1208679 |

[14] | Maimour, M. (2008) Maximally Radio-Disjoint Multipath Routing for Wireless Multimedia Sensor Networks. Proceedings of the 4th ACM Workshop on Wireless Multimedia Networking and Performance Modeling, Vancouver, 27-31 October 2008, 26-31. |

[15] |
Radi, M., Dezfouli, B. and Razak, S.A. (2010) LIEMRO: A Low Interference Energy Efficient Multipath Routing Protocol for Improving QoS in Event-Based Wireless Sensor Networks. Proceedings of 4th International Conference on Sensor Technologies and Applications, Venice, 18-25 July 2010, 551-557.
https://doi.org/10.1109/sensorcomm.2010.89 |

[16] | Wang, Z., Bulut, E. and Szymanski, B.K. (2009) Energy Efficient Collision Aware Multipath Routing for Wireless Sensor Networks. Proceedings of IEEE International Conference on Communications, Dresden, 14-18 June 2009, 1-5. |

[17] | Arora, Y. and Pande, H. (2013) Energy Saving Multipath Routing Protocol for Wireless Sensor Networks. International Journal of Engineering Research and Applications, 3, 152-156. |

[18] |
Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J. and Silva, F. (2002) Directed Diffusion for Wireless Sensor Networking. ACM/IEEE Transactions on Networking, 11, 2-16. https://doi.org/10.1109/TNET.2002.808417 |

[19] |
Yahya, B. and Ben-Othman, J. (2009) REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks. Proceedings of IEEE Global Telecommunications Conference, Honolulu, 30 November-4 December 2009, 1-7.
https://doi.org/10.1109/glocom.2009.5425587 |

[20] |
Agre, J. and Clare, L. (2000) An Integrated Architecture for Cooperative Sensing Networks. Computer, 33, 106-108. https://doi.org/10.1109/2.841788 |

[21] |
Heinzelman, W.R., Chandrakasa, A. and Balakrishnan, H. (2000) Energy Efficient Communication Protocol for Wireless Micro Sensor Networks. Proceedings of the 33th Annual Hawaii International Conference on System Sciences, Hawaii, 4-7 January 2000, 10. https://doi.org/10.1109/HICSS.2000.926982 |

[22] |
Gandham, S.R., Dawande, M., Prakash, R. and Venkatesan, S. (2003) Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations. IEEE Global Telecommunications Conference, Vol. 1, San Francisco, 1-5 December 2003, 377-381. https://doi.org/10.1109/glocom.2003.1258265 |

[23] |
Cardei, M., Wu, J., Lu, M. and Pervaiz, M.O. (2005) Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, Vol. 3, Montreal, 24-22 August 2005, 438-445.
https://doi.org/10.1109/wimob.2005.1512935 |

[24] | Jantarasorn, C. and Prommak, C. (2012) Minimizing Energy Consumption in Wireless Sensor Networks Using Binary Integer Linear Programming. International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering, 6, 124-128. |

[25] | Cheng, X., Narahari, B., Simha, R., Cheng, M.X. and Liu, D. (2003) Strong Minimum Energy Topology in WSNs: NP-Completeness and Heuristics. IEEE Transactions on Mobile Computing, 2, 248-256. |

[26] | Wan, P.X.L. and Wang, Y. (2001) Power Efficient and Sparse Spanner for Wireless Ad Hoc Networks. 10th International Conference on Computer Communications and Networks, Scottsdale, 15-17 October 2001, 564-567. |

[27] |
Avril, F., Bernard, T., Bui, A. and Sohier, D. (2014) Clustering and Communications Scheduling in WSNs Using Mixed Integer Linear Programming. Journal of Communications and Networks, 16, 421-429. https://doi.org/10.1109/JCN.2014.000072 |

[28] |
Chang, J.H. and Tassiulas, L. (2004) Maximum Lifetime Routing in Wireless Sensor Networks. IEEE/ACM Transactions on Networking, 12, 609-619.
https://doi.org/10.1109/TNET.2004.833122 |

[29] |
Ben-Othman, J., Bessaoud, K.K., Bui, A. and Pilard, L. (2013) Self-Stabilizing Algorithm for Efficient Topology Control in Wireless Sensor Networks. Journal of Computational Sciences, 4, 199-208. https://doi.org/10.1016/j.jocs.2012.01.003 |

[30] |
Gogu, N.D., Dilo, A. And Mertnia, N. (2011) Optimization Problems in Wireless Sensor Networks. International Conference on Complex, Intelligent and Software Intensive Systems, Seoul, 30 June-2 July 2011, 302-309.
https://doi.org/10.1109/cisis.2011.50 |

[31] | Efrat, A., Peled, S. and Mitchel, J. (2005) Approximation Algorithms for Two Optimal Location Problems in Sensor Networks. Broadband Networks, 1, 714-723. |

[32] |
Cavalier, T.M., Conner, W., Castillo, E. and Brown, S. (2007) A Heuristic Algorithm for Minimax Sensor Location in the Plane. European Journal of Operational Research, 183, 42-55. https://doi.org/10.1016/j.ejor.2006.10.055 |

[33] | Meguerdichian, S., Koushanfar, F., Potkonjak, M. and Srivastava, M.B. (2001) Coverage Problems in Wireless Ad Hoc Sensor Networks. 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, 22-26 April 2001, 1380-1387. |

[34] |
Purohit, G.N. and Sharma, U. (2010) Constructing Minimum Connected Dominating Set: Algorithmic Approach. International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, 2, 59-66.
https://doi.org/10.5121/jgraphoc.2010.2305 |

[35] |
Clark, B.N., Colbourn, C.J. and Johnson, D.S. (1990) Unit Disk Graphs. Discrete Math, 86, 165-177. https://doi.org/10.1016/0012-365X(90)90358-O |

[36] |
Guha, S. and Khuller, S. (1998) Approximation Algorithms for Connected Dominating Sets. Algorithmica, 20, 374-387. https://doi.org/10.1007/pl00009201 |

[37] | Wu, Y., Stankovic, J.A., He, T., Lu, J. and Lin, S. (2008) Realistic and Efficient Multi-Channel Communications in Wireless Sensor Networks. Proceedings of IEEE INFOCOM, 12, 1193-1201. |

[38] |
Vincze, Z., Vida, R. and Vidacs, A. (2007) Deploying Multiple Sinks in Multi-Hop Wireless Sensor Networks. Proceedings of IEEE International Conference on Pervasive Services, Istanbul, 15-20 July 2007, 55-63.
https://doi.org/10.1109/PERSER.2007.4283889 |

[39] | Wang, Z.M., Basagni, S., Melachrinoudis, E. and Petrioli, C. (2005) Exploiting Sink Mobility for Maximizing Sensor Networks Lifetime. Proceedings of the 38th Hawaii International Conference on System Sciences, Hawaii, 3-6 January 2005, 1-9. |

[40] |
Gagnon, J. and Narayanan, L. (2015) Efficient Scheduling for Minimum Latency Aggregation in Wireless Sensor Networks. Proceedings of IEEE Wireless Communications and Networking Conference, New Orleans, 9-12 March 2015, 1024-1029.
https://doi.org/10.1109/wcnc.2015.7127610 |

[41] |
Wan, P.-J., Huang, S.C.-H., Wang, L., Wan, Z. and Jia, X. (2009) Minimum-Latency Aggregation Scheduling in Multihop Wireless Networks. Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, New Orleans, 18-21 May 2009, 185-194. https://doi.org/10.1145/1530748.1530773 |

[42] |
Malhotra, B., Nikolaidis, I. and Nascimento, M.A. (2011) Aggregation Convergecast Scheduling in Wireless Sensor Networks. Wireless Networks, 17, 319-335.
https://doi.org/10.1007/s11276-010-0282-y |

[43] |
Zonouz, A.E. and Vokkarane, V.M. (2014) Reliability-Oriented Single-Path Routing Protocols in Wireless Sensor Networks. IEEE Sensors Journal, 14, 4059-4068.
https://doi.org/10.1109/JSEN.2014.2332296 |

[44] | Asorey-Cacheda, R., García-Sánchez, A.J., García-Sánchez, F., García-Haro, J. and González-Castano, F.J. (2013) On Maximizing the Lifetime of Wireless Sensor Networks by Optimally Assigning Energy Supplies. Sensors, 13, 10219-10244. |

[45] | Hou, Y.T., Shi, Y. and Sherali, H.D. (2005) On Energy Provisioning and Relay Node Placement for Wireless Sensor Networks. IEEE Transactions on Wireless Communications, 4, 2579-2590. |

[46] |
Chang, J. and Tassiulas, L. (2004) Maximum Lifetime Routing in Wireless Sensor Networks. IEEE/ACM Transaction on Networking, 12, 609-619.
https://doi.org/10.1109/TNET.2004.833122 |

[47] |
Luz, Y.M. and Wong, V. (2007) An Energy-Efficient Multipath Routing Protocol for Wireless Sensor Networks. International Journal of Communication Systems, 20, 747-766. https://doi.org/10.1002/dac.843 |

[48] |
Guney, E., Aras, N., Altinel, K. and Ersoy, C. (2010) Efficient Integer Programming Formulations for Optimum Sink Location and Routing in Heterogeneous WSN. Computer Networks, 54, 1805-1822. https://doi.org/10.1016/j.comnet.2010.02.009 |

[49] | Nivas, T. and Zaruba, G. (2007) Upper Bound of Sensor Network Lifetime: A Flow Optimization Approach. Proceedings of the ACM GHCCWC. |

[50] | Rossi, A., Singh, A. and Sevaux, M. (2010) Generation de colonnes dans le reseaux de capteurs sans fil. Proceedings of ROADEF. |

[51] | Attarde, S.A., Ragha, L.L. and Dhamal, S.K. (2010) An Enhanced Spanning Tree Topology for Wireless Sensor Networks. International Journal of Computer Applications, 1, 46-51. |

[52] |
Ergen, S. and Varaiya, P. (2010) TDMA Scheduling Algorithms for WSN. Wireless Networks, 16, 985-997. https://doi.org/10.1007/s11276-009-0183-0 |

[53] | Jayalakshmi, R., Baranidharan, B. and Santhi, B. (2014) Attribute Based Spanning Tree Construction for Data Aggregation in Heterogeneous Wireless Sensor Networks. Indian Journal of Science and Technology, 7, 76-79. |

[54] |
Lachowski, R., Pellenz, M.E., Penna, M.C., Jamhour, E. and Souza, R.D. (2015) An Efficient Distributed Algorithm for Constructing Spanning Trees in Wireless Sensor Networks. Sensors, 15, 1518-1536. https://doi.org/10.3390/s150101518 |

[55] | Khan, G., Bathla, G. and Ali, W. (2011) Minimum Spanning Tree based Routing Strategy for Homogeneous WSN. International Journal on Cloud Computing: Services and Architecture, 1, 22-29. |

[56] | Vashist, R. and Dutt, S. (2014) Minimum Spanning Tree based Improved Routing Protocol for Heterogeneous Wireless Sensor Network. International Journal of Computer Applications, 103, 29-33. |

[57] | Saha, S. and McLauchlan, L. (2015) An Approach to Construct Weighted Minimum Spanning Tree in Wireless Sensor Networks. In: Lee, R., Ed., Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, Vol. 569, Springer International Publishing, Cham, 69-84. |

[58] | Vijay, U. and Gupta, N. (2013) Clustering in WSN Based on Minimum Spanning Tree Using Divide and Conquer Approach. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 7, 926-930. |

[59] |
Saravanan, M. and Madheswaran, M. (2014) A Hybrid Optimized Weighted Minimum Spanning Tree for the Shortest Intrapath Selection in Wireless Sensor Network. Mathematical Problems in Engineering, 2014, Article ID: 713427.
https://doi.org/10.1155/2014/713427 |

[60] |
Suto, K., Nishiyama, H., Kato, N. and Huang, C.W. (2015) An Energy-Efficient and Delay-Aware Wireless Computing System for Industrial Wireless Sensor Networks. IEEE Access, 3, 1026-1035. https://doi.org/10.1109/ACCESS.2015.2443171 |

[61] | Yu, Y., Krishnamachari, B. and Prasanna, V.K. (2004) Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks. Proceedings IEEE International Conference on Computer Communications, Hong Kong, 7-11 March 2004, 244-255. |

[62] |
Dong, M., Ota, K., Liu, A. and Guo, M. (2016) Joint Optimization of Lifetime and Transport Delay under Reliability Constraint Wireless Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 27, 225-236.
https://doi.org/10.1109/TPDS.2015.2388482 |

[63] | Choi, W. and Das, S. (2005) A Novel Framework for Energy-Conserving Data Gathering in Wireless Sensor Networks. Proceedings IEEE International Conference on Computer Communications, Miami, 13-17 March 2005, 1985-1996. |

[64] |
Cheng, C.T., Tse, C.K. and Lau, F.C.M. (2010) A Delay-Aware Data Collection Network Structure for Wireless Sensor Networks. IEEE Sensors Journal, 11, 699-710. https://doi.org/10.1109/JSEN.2010.2063020 |

[65] |
Ammari, H.M. and Das, S.K. (2005) Trade-Off between Energy Savings and Source-to-Sink Delay in Data Dissemination for Wireless Sensor Networks. Proceedings of 8th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal, 10-13 October 2005, 126-133.
https://doi.org/10.1145/1089444.1089467 |

Journals Menu

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.