Sage Journals: Discover world-class research

Abstract

The target tracking issue has always been the hotspot in wireless sensor network, and with the emergence of new application in multimedia and real-time transmission, new requirements are proposed for transmission performance of target tracking routing; therefore, a software-defined network–based hierarchical adaptive routing algorithm of wireless sensor network is proposed in this article. The algorithm takes into account both network energy and throughput, uses Hopfield neural network algorithm to calculate the optimal path among adjacent clusters as a local routing (LR), and builds the Multi-choice Knapsack Problem model based on local paths to realize end-to-end global routing, in order to realize the routing of tracking target information under multi-objective conditions. The test bed includes physical and simulation tests. Experimental results show that the proposed algorithm is superior to low energy adaptive clustering hierarchy (LEACH) and Sequential Assignment Routing under different test scenarios.

Keywords

Adaptive routing algorithm wireless sensor network software-defined network target tracking

Introduction

Wireless sensor network (WSN) refers to a group of spatially dispersed and dedicated sensors for monitoring and recording the physical conditions of the environment and organizing the collected data at a central location. Meanwhile, WSN can also be used for target object tracking and identification due to its sensory capabilities in spatially dispersed region. With the increase of requirements on various new applications, such as the new requirement proposed by multimedia information acquisition and high-speed information transmission to transmission technology during target tracking, the traditional methods fail to meet performance requirements, and therefore, it is necessary to study new routing protocols so as to meet the application needs.

In recent years, many scholars study object identification algorithm and positioning algorithm. Vasuhi and Vaidehi¹ propose the WSN target tracking method based on Interactive Multiple Model, due to the fact that traditional methods fail to accurately identify targets. Lu et al.² consider the constraint of electric energy and transmission in WSN; they study collaborative target tracking triggered by event-based information filtering. Oracevic et al.³ propose a safe and reliable target tracking protocol and consider safety when targets are tracked. Su et al.⁴ put forward estimation and control strategies of bi-target tracking mobile sensor network. Shi et al.⁵ propose a probability-based dynamic but non-complete k-covering method for both tracking quality and network lifetime goals. In order to maintain and balance the remaining capacity of the sensor, Lersteau et al.⁶ design a two-step exact method and allocate time to the sensor by processing the input data. Lersteau et al.⁷ mention a pseudo-polynomial two-step algorithm to eliminate the influence on detection due to sensor scheduling. Sleep et al.⁸ also study target tracking issue in heterogeneous sensor environment and propose a sensor-independent tracking framework. Aiming at the issue of sensor scheduling in target tracking, Yan⁹ put forward a prediction algorithm based on sensor node. Guo et al.¹⁰ tend to propose a sensor selection method based on maximum fuzzy cluster to solve target tracking issue in large-scale sensor networks. The studies above mainly aim at solving issues like target tracking and positioning, and identifying a variety of methods, but fail to pay particular attention to information transmission during target tracking, especially in the application where transmission rate is demanded.

Routing has always been a hotspot in WSN. Considering the importance of energy to WSNs, Rahman et al.¹¹ study various energy efficient routing (EER) protocols, classify them, and discuss their advantages and disadvantages. Keskin et al.¹² provide a mathematical model that integrates WSN design decisions, activity schedules, data routing, and trajectory of mobile receiver at the sensor location, and then present two heuristic methods for solving the model. Anitha and Kamalakkannan¹³ propose an improved enhanced cluster based multipath routing protocol in mobile wireless sensor network (ECBR-MWSN) algorithm based on low-energy adaptive clustering. The protocol uses parameters such as maximum dump energy, minimum mobility, and the minimum distance from the base station, and selects new clusters by periodically running algorithms proposed so as to prolong the life of sensor network through balancing node energy consumption. Based on the analysis of low energy adaptive clustering hierarchy (LEACH) protocol characteristics, Zhang et al.¹⁴ propose WSN based on simulated annealing (SA) and genetic algorithm (GA) to balance clustering routing protocol; meanwhile, they prolong lifetime of WSN by switching cluster head balance load. Han et al.¹⁵ propose a general self-organizing energy balance routing protocol based on tree, which constructs a routing tree, reports the information about root node by broadcasting, and allows each node and its neighbors’ information to select node relation, thus transmitting information. Besides, Karaboga et al.¹⁶ propose a clustering mechanism based on artificial bee colony algorithm, which applies the intelligent foraging behavior of simulated bee colony into clustering technology so as to prolong the network lifetime. The energy constraint of the network is mainly considered in above routing protocols, and they design different data transmission models from the perspective of energy consumption so as to help the network realize data exchange in different modes, but they fail to study transmission of target tracking applications, and corresponding routing protocols are lacked.

The proposal of software-defined network (SDN) provides a new research perspective for the application of WSN as well as a new framework for resource scheduling of WSN. Considering characteristics like invariance and difficult management of WSN policy, Luo et al.¹⁷ put forward a software-defined WSN architecture, which solves key technologies of core components. Besides proposing solutions for SDN-based WSN, Galluccio et al.¹⁸ also carefully describe implementation details of software defined networking for wireless sensor networks (SDN-WISE), which is outstanding in making network programming flexible and concise. Jagadeesan and Krishnamachari¹⁹ summarize the application of wireless network SDN technology, introduce relevant technologies, and also outline its development trend. Analyzing the software-defined sensor networks combining WSNs and SDN, Zeng et al.²⁰ introduce the concept of software-defined sensor networks (SDSNs) and summarize the related innovations, which provide technical support for SDSNs implementation. In view of the issues faced by wireless network virtualization like signals control, Liang and Yu²¹ propose issues and challenges in implementing wireless network virtualization. Moreover, Jacobsson and Orfanidis²² also propose a software-defined WSN architecture and discuss how SDN can be applied in wide WSN to deploy hardware and custom software so as to meet the needs of specific deployments and applications. Wang et al.²³ propose a software-defined algorithm and manage network energy through the algorithm executed in controller. Proposing an SDN concept with a structured and hierarchical management of WSN, Olivier et al.²⁴ aim at addressing some inherent problems in WSN management through SDN’s structured and hierarchical ways. SDN opens new ways for WSN to deploy resources. At this stage, the application of SDN in WSN is still under development, and is mainly limited to aspects like architecture, basic protocols, and deployment applications, and fails to involve in specific issues such as target tracking; therefore, there is a large space for the research of this issue.

According to research and analysis above, this article proposes a Hierarchical Adaptive Routing algorithm based on SDN (HAR-SDN), which uses multi-objective scheduling strategies combining energy and throughput after considering factors in transmission speed and energy consumption. This article designs resource scheduling scheme on the basis of SDN framework with two results.

It carries out decision making, scheduling, and deployment through SDN controller.

It adopts hierarchical scheduling method combining local path planning with global scheduling to route detecting information of the target.

Description of routing selection

Combination of SDN and WSN

WSN achieves connectivity by means of self-organizing through sensor nodes; although this network is widely applied, there are many shortcomings in structural features, for example, scheduling strategy of sensor nodes cannot be reconfigured and uniform management is lacked in self-organizing method. With the introduction of SDN framework, great changes occur to resource scheduling methods. By separating the controlling plane and data plane, SDN realizes decoupling of the program management function and the data scheduling function, shields the differences of devices, and achieves reconstruction of hardware resource; besides, it completes virtual mapping of the physical resources through SDN controller and the OpenFlow protocol. Recently, OpenFlow has been applied in WSN.¹⁷ Related technologies^20,25 improve structure of OpenFlow and design corresponding matching rules. As shown in Figure 1, the controller, according to control strategies, will pass parameters to WSN through the OpenFlow extension protocol to reconfigure resources; at the same time, the state information in network will be sent to the controller for decision making. In the process of network resource management, the sensor is only responsible for the perception and transmission of information, while the controller is responsible for the decision making and scheduling.

Figure 1.

Software-defined wireless sensor networks.

High requirements are proposed by routing of moving target information to WSN: first, it needs to provide higher transmission rate to ensure real-time and efficient transmission of information; second, energy consumption factors must be taken into account by the network; and finally, corresponding scheduling strategies are needed to track mobile target. Considering above factors, we design an SDN-based hierarchical scheduling algorithm by viewing throughput and energy as indicators.

Hierarchical scheduling algorithm

Hierarchical routing includes local path planning and global path optimization. We can obtain optimal routing of nodes among adjacent clusters through local path planning, and the purpose of the global path optimization is to construct a full path for information transmission from target to sink node by selecting optimal routing among adjacent clusters. The description of hierarchical routing is as shown in Figure 2. In the process of target tracking, all sensors are divided into clusters; the line between adjacent clusters represents the optimal routing from the current node to adjacent cluster. Based on the routing, the full path can be achieved to transmit the target information. In terms of scheduling indicators, energy and throughput are taken into account, and energy computing aims at extending lifetime; Figure 3 can be referred to for selection of high-speed transmission node. Due to physical characteristics of wireless transmission, different distances of communication are corresponding to different transmission rates, and therefore, neighbor node of communication distance with more throughput can be used to transmit data for the purpose of improving the transmission speed of links.

Figure 2.

Schematic diagram of hierarchy routing.

Figure 3.

Schematic diagram of high-speed node selection.

SDN controller is responsible for running and scheduling hierarchical scheduling algorithm, which reduces the operational load of WSN itself. Besides, the global path optimization will adjust local nodes timely by means of on-demand service, reducing the running cost of routing algorithm.

Target tracking model

Particle filter is an algorithm developed based on Kalman filter, which is mainly used for target tracking and has been applied in various fields, including WSNs.^26,27

Like Kalman filter, particle filter²⁸ is also based on system state equation and system observation equation to estimate the system. As shown in formulas (1) and (2)

$x_{k} = f (x_{0 | k - 1}, v_{k - 1})$ (1)

$z_{k} = h (x_{k}, n_{k})$ (2)

The state of target at time k is represented by the state vector x_k; z_k represents the observation vector at time k; f(•) and h(•) represent the state transition function and observation function, respectively; x_0|k−1 represents all the state vectors by time k – 1; and v and n, respectively, represent the process noise and measurement noise.

In particle filter, the sampling information of the sensors correspond to particles, so the set of particles at time k can be shown in formula (3)

$S_{k} = {(x_{k}^{i}, w_{k}^{i}) | i = 1, \dots, N}$ (3)

where $w_{k}^{i}$ represents the weight of the ith particle, $x_{k}^{i}$ represents the state of the ith particle, and N represents the total number of particles.

A posterior probability density p(x_k|z_1:k) based on sampling is obtained by particle filter through recursive estimation. Therefore, the posterior probability density at time k can be approximately expressed as formula (4)

$p (x_{k} | z_{1 : k}) \approx \sum_{i = 1}^{N} w_{k}^{i} δ (x_{k} - x_{k}^{i})$ (4)

In fact, the target tracking is the estimation of the target state, that is, the prior knowledge is used to predict the future state through the system state equation, and the system is corrected by updating the posterior probability density in the process.

Assuming that the set of particles at time t – 1 is $(x_{t - 1}^{i}, w_{t - 1}^{i})$ , the process of particle filter can be described as follows:

Initialization of particles: t = 0. For $i = 1, 2, \dots, N$ . The state of particles is initialized to ${x_{0}^{i}}_{i = 1}^{N}$ according to prior information p(x₀).

For $t = 1, 2, \dots, N$ , perform the following steps:

Importance sampling: For $i = 1, 2, \dots, N$ , new particles ${{\tilde{x}}_{t}^{i}}_{i = 1}^{N}$ are generated according to the importance density function, and the weight of particles ${\tilde{w}}_{t}^{i}$ is calculated.

Resampling: The effective number of particles N_eff is calculated, and the judgment criteria are used to determine whether the particles need resampling. If yes, resample again or execute the next step.

Put the particle into the state transition function to obtain the new estimated state. As shown in formula (5)

${\hat{x}}_{t} = \sum_{i = 1}^{N} {\tilde{x}}_{t}^{i} {\tilde{w}}_{t}^{i}$ (5)

The prediction of the target movement can not only realize continuous tracking of the target but also provide the scheduling goal for global routing so as to establish the corresponding routing.

SDN-based hierarchical routing algorithm of target tracking

In the process of target tracking, according to different application requirements, we need to obtain different kinds of information of the target in real time, including position, velocity, size, sound and image information, and so on. Meanwhile, we also need to consider the energy consumption of the sensor network itself. Therefore, we design a hierarchical routing algorithm for both throughput and network energy consumption to ensure the efficient and real-time transmission of the information.

First, definition of throughput: In terms of energy consumption and transmission rate, many studies^29,30 show that routing between nearest nodes is not optimal by means of multi-hop manner, and therefore, it is necessary to select proper distance between nodes for transmission. For more details, refer to literature.³¹

Assuming that the transmission distance between node 0 and node Y is y and the rate is r_c, then the probability of successful transmission can be expressed as formula (6), wherein γ means SINR (Signal to Interference plus Noise Ratio) corresponding to the rate r_c, and P_idle(Y) represents idle probability of node Y, while all nodes follow Poisson distribution

$P_{s | y} = P_{idle} (Y) \cdot \Pr {SIN R at nod e Y \geq γ}$ (6)

According to loss model of power law path, formula (6) can be expressed as below

$\begin{matrix} P_{s | y} = \frac{1}{1 + λ T} e^{- λ T} \cdot \\ \exp [- π v (1 - \frac{1}{1 + λ T} e^{- λ T}) \\ {({(y^{- α} / γ - N / P)}^{+})}^{- 2 / α}] \end{matrix}$ (7)

The transmission rate is represented as G and S_|y under load density and distance y, and they are shown as formulas (8) and (9)

$\begin{matrix} G = b \cdot \Pr {idle} \cdot \\ {packet generation intensity | idle} \\ \begin{matrix} = b \cdot \frac{1}{1 + λ T} \end{matrix} \cdot λ υ [\frac{bits}{s \cdot m^{2}}] \end{matrix}$ (8)

$S_{| y} = G \cdot P_{s | y} [\frac{bits}{s \cdot m^{2}}]$ (9)

The formula (10) can be obtained after arrangement

$\begin{matrix} S = υ b λ {(1 + λ T)}^{- 2} e^{- λ T} \cdot \\ \exp [- π υ (1 - \frac{1}{1 + λ T} e^{- λ T}) \cdot \\ {(y^{- α} / γ - N / P)}^{- 2 / α}] \cdot y \cdot \\ \cos (arh (Y)) \end{matrix}$ (10)

Through derivation of above formula, we can get the optimal transmission distance y* and maximum throughput S*, as shown in formula (11)

$\begin{matrix} y^{*} = {(2 π υ (1 - \frac{1}{1 + λ T} e^{- λ T}))}^{- 1 / 2} γ^{- 1 / α} \\ S^{*} = b {(2 π υ (1 - \frac{1}{1 + λ T} e^{- λ T}))}^{- 1 / 2} . \\ γ^{- 1 / α} {(1 + λ T)}^{- 1} e^{- λ T - 1 / 2} \end{matrix}$ (11)

Second, definition of lifetime: Lifetime is an important index to evaluate energy consumption of wireless sensor. Formula (12) refers to energy consumption when nodes send and receive K bits

$\begin{matrix} E_{r} (k, d) = k E_{elec} + k E_{amp} d^{2} \\ \begin{matrix} E_{r} \end{matrix} (k) = k E_{elec} \end{matrix}$ (12)

wherein E_elec is the energy consumption of the circuit when data are received and sent, E_amp is the energy consumption of signal amplifier circuit, and d is the distance between sending node and receiving node.

Thus, we can get time-to-live of node i as shown in formula (13)

$T = \frac{E_{i}}{(E_{r} (k) + E_{r} (k, d)) \sum_{j \in S_{i}} f_{ij}}$ (13)

wherein E_i is the existing energy of node i; $F_{i} = \sum_{j \in S_{i}} f_{ij}$ means data flow of node i and all neighbor nodes j.

Local path planning

Objective function of local optimization

Because WSN adopts multi-hop routing method, it is necessary to construct local routing (LR) between adjacent clusters for the purpose of effectively transmitting information among multiple clusters. The starting node of local routing is node N_s in current cluster C_s, since the local routing algorithm transmits data through neighboring nodes, the end point N_t of the local routing can be defined as the node adjacent to C_s in C_t. The local routing set LR (C_s, C_t) from cluster C_s to adjacent cluster C_t is defined as all optimal paths from any node in C_s to all nodes in C_t that are adjacent to C_s. Local routing finds the optimal routing for nodes between adjacent clusters. Therefore, the local routing function can be described as formula (14), where n_a is the starting point and n_b is the end of adjacent cluster

$\begin{matrix} \begin{matrix} obj : & L (r) = \max {route (r)} \end{matrix} \\ \begin{matrix} \begin{matrix} \end{matrix} & = \max {route (n_{a}, \dots, n_{b})} \end{matrix} \end{matrix}$ (14)

In order to meet the transmission requirements, this article defines a multi-objective function with purpose of seeking for greater throughput and longer network lifetime. Moreover, the article carries out normalization processing by adopting Z-score method, and indexes like S and T become $S'$ and $T'$ after normalization.

Local path planning aim to maximize minimum transmission rate between nodes and lifetime of nodes with the least lifetime. Therefore, the objective function is defined as shown in formula (15)

$\begin{matrix} obj : L (r) = \max {α \cdot \min S' (n_{i}, \dots, n_{m}) \\ + (1 - α) \cdot \min T' (n_{i}, \dots, n_{m})} \\ s . t . {n_{a}, \dots, n_{b}} \subset {C_{1} \cup C_{2}} \\ {n_{a}, \dots, n_{b}} \cap C_{1} \neq \emptyset & \\ {n_{a}, \dots, n_{b}} \cap C_{2} \neq \emptyset \end{matrix}$ (15)

where C₁ and C₂ represent adjacent clusters.

Selection of optimal path among clusters

In recent years, neural networks are widely applied in WSN because of similarity of node perception in neural networks and rules-based information transmission methods with WSNs as well as strong parallel computing and potential hardware implementation capabilities.^32,33 The Hopfield³⁴ network is a feedback system composed of non-linear components, and it is famous for successfully solving Traveling Salesman Problem; Continuous Hopfield Neural Network (CHNN) is designed according to circuit model structure, as shown in Figure 4.

Figure 4.

CHNN circuit model.

CHNN is continuous in time, which means neurons in the network are working in a synchronous manner. As for a neuron, that is neuron j, its internal potential state is represented by u_j, input capacitance is C_j, transfer resistance is R_j, output voltage is V_j, external input current is represented by I_j, and N means the number of neuron.

According to Kirchhoff laws,³⁵ the node equation corresponding to the j neuron is shown in formula (16), wherein v_j(t) is the output potential, U_j(t) means input potential, and g_i(·) means transfer function

${\begin{matrix} C_{j} \frac{d U_{i} (t)}{dt} = \sum_{i = 1}^{n} W_{ij} V_{i} (t) - \frac{U_{i} (t)}{R_{j}} + I_{j} \\ V_{i} (t) = g_{i} (U_{i} (t)) j = 1, 2, \dots, n \end{matrix}$ (16)

Stability is an important indicator for Hopfield to evaluate state of network operation, and therefore, the Lyapunov function is introduced in the Hopfield network for analysis, which is called the energy function E, as shown in formula (17). The problem-solving process for Hopfield network is the evolution process from the initial state to stable one, wherein the energy function E is regarded as objective function; with system changes, the network state always moves toward the energy reduction and stabilizes ultimately. Specifically, it means to transform objective function into energy function of the network, and the optimal solution is obtained by converging minimum value of the energy function. Therefore, the key to solve issues is to define energy function

$\begin{matrix} E (t) = - \frac{1}{2} \sum_{j = 1}^{n} \sum_{i = 1}^{n} W_{ij} V_{i} (t) V_{j} (t) - \sum_{j = 1}^{n} V_{j} (t) I_{j} \\ + \sum_{j = 1}^{n} \frac{1}{R_{i}} \int_{0}^{V_{j} (t)} g^{- 1} (V) dV \end{matrix}$ (17)

The next step is to convert the local routing into a form that the Hopfield can handle, as shown in Figure 5.

Figure 5.

Node selection of local routing.

In this figure, $N_{1}, \dots, N_{i}$ means all nodes in C_s, and N_t is the ending node. Each row represents a data sending node, while column means data receiving node. The value of V_ij is 0 or 1, and there is only one value in each row or column; V_ij = 1 indicates that there is a routing relationship between nodes i and j. The node in first row represents the route starting node, while node in last column means the end of the route. As for all relay nodes in addition to the starting and ending nodes, in order to guarantee path efficiency, if they are receiving nodes, they must be the sending nodes.

Then, the constraints can be integrated to construct energy function.

Constraint of starting node: The first line is the starting node, therefore $\sum_{j = 1}^{n + 1} V_{1 j} = 1$ . Thus, we can get the starting node constraint as shown in formula (18)

$E_{1} = \sum_{j = 1}^{n + 1} V_{1 j} - 1$ (18)

Constraint of end node: The last column is the ending node, therefore $\sum_{i = 1}^{n} V_{i, n + 1} = 1$ . Thus, we can get the ending node constraint as shown in formula (19)

$E_{2} = \sum_{i = 1}^{n} V_{i, n + 1} - 1$ (19)

Constraint of relay node: The relay node not only receives data but also sends data, and the constraint condition can be expressed in formula (20)

$E_{3} = \sum_{j = 1}^{n + 1} \sum_{i = 1}^{n} V_{ij} - \sum_{k = 1}^{n + 1} \sum_{j = 1}^{n} V_{jk}$ (20)

Formula (21) can be obtained through local optimization objective function

$E_{4} = \sum_{j = 1}^{n + 1} \sum_{i = 1}^{n} L (r (i)) V_{ij}$ (21)

The energy function is as shown in formula (22)

$\begin{matrix} E = \frac{A}{2} E_{1} + \frac{B}{2} E_{2} + \frac{C}{2} E_{3} + \frac{D}{2} E_{4} \\ = \frac{A}{2} (\sum_{j = 1}^{n + 1} V_{1 j} - 1) + \frac{B}{2} (\sum_{i = 1}^{n} V_{i, n + 1} - 1) + \\ \frac{C}{2} (\sum_{j = 1}^{n + 1} \sum_{i = 1}^{n} V_{ij} - \sum_{k = 1}^{n + 1} \sum_{j = 1}^{n} V_{jk}) + \\ \frac{D}{2} (\sum_{j = 1}^{n + 1} \sum_{i = 1}^{n} (\frac{1}{L (r (i))}) V_{ij}) \end{matrix}$ (22)

wherein A, B, C, and D are integer parameters, with values of A = 500, B = 500, C = 600, and D = 400.

Complexity analysis

The number of neuron is N, and the constraints of row and column can be regarded as constrained breadth-first search, which has the same computational complexity as the general breadth-first search, O(N); therefore, the computational complexity of each path planning cycle is O(N).

Global path optimization

The introduction of SDN makes scheduling management of WSN more flexible in ways. The mapping relationship between strategies and resources through control plane and the data plane allows resources’ allocation and implementation from global scheduling to the sensor node, thus realizing global path planning of WSN. Based on the local routing, global routing carries out end-to-end routing optimization by means of on-demand service. The coarse-grained scheduling is adopted in global routing, which can not only improve scheduling efficiency but also avoid unnecessary resources waste.

Hierarchical algorithm of sub-path

What the global path constructs is a sub-path sequence, and therefore it is necessary to be clear about relationships among sub-paths. The routing process involves in several clusters; it shows from definition of local path planning that there is a correspondence between adjacent clusters, which means there is hierarchical relationship in all sub-paths from target to sink nodes; therefore, it is necessary to classify sub-paths.

Step 1. Take the cluster where tracked target lie, or its nearest cluster as root cluster, represented as C₀;

Step 2. The set of clusters adjacent to C₀ becomes the first-level cluster, represented as C₁. The first-level path set P₁ is composed of all local paths between C₀ and C₁, represented as P₁ = {P(C₀, C₁)};

Step 3. In addition to C₀ and C₁, the set of other clusters adjacent to C₁ is called the second-level cluster, represented as C₂. The second-level path set P₂ is composed of all local paths between C₁ and C₂. as well as C₁ and C₁, expressed as P₂ = {P(C₁, C₂)∪P(C₁, C₁)};

Step 4. By analogy, P_i, the ith path set is expressed as P_i ={P(C_i₋₁, C_i)∪P(C_i₋₁, C_i₋₁)};

Step 5. We can obtain k sets of paths in turn $P_{1}, \dots, P_{k}$ .

Global optimization objective function

All local paths are divided into $P_{1}, \dots, P_{k}$ sets. When the constraints are satisfied, a path is selected from each set in order to form a path that maximizes the scheduling goal. Therefore, the problem of global routing selection can be transformed into Multi-choice Knapsack Problem (MCKP). The global optimization objective function is as shown in formula (23)

$\begin{matrix} obj : \max \sum_{p = 1}^{k} \sum_{q = 1}^{q_{p}} V_{pq} X_{pq} \\ \max \sum_{p = 1}^{k} \sum_{q = 1}^{q_{p}} \max {rout e_{p} (q)} X_{pq} \\ s . t . \sum_{q = 1}^{q_{p}} X_{pq} = 1, p \in {1, \dots, k} \\ \begin{matrix} \begin{matrix} X_{pq} \in {0, 1}, p \in {1, \dots, k} \\ q \in {1, \dots, q_{p}} \end{matrix} \end{matrix} \\ \begin{matrix} \begin{matrix} {n_{x} | n_{x} \in rout e_{p} (\cdot)} \cap \\ {n_{y} \in rout e_{p + 1} (\cdot)} \neq \emptyset \end{matrix} \end{matrix} \end{matrix}$ (23)

wherein K is the number of path sets, q_p is the number of paths in the pth set, and V_pq is the function value of q path in the p set. The global optimization aims at finding a path that maximizes objective function. In the formula, the first two constraints indicate that a local path is selected from each path set, while the last constraint requires that local paths of selected adjacent sets must be intersecting so as to ensure whether the path is consistent.

The objective function is characterized by the following points:

Quantization of multiple indexes. The global routing scheduling adopts the same indexes as the local routing, and the method of normalization is used to quantify the multi-objective. Moreover, the multi-objective function is transformed into single objective function by linear integration, avoiding the problem of single objective optimization for multi-objective.

The performance of the algorithm is adjusted by weight. The normalized function only needs adjusting the weight for objective according to experimental effect and experience, which improves the optimization efficiency of the algorithm.

Coarse-grained scheduling. The scheduling unit changes from each node to a local path, which can further improve the scheduling efficiency for the global path.

Convenient comparison with similar algorithms. At present, most of the algorithms in this field are based on single objective. The function forms defined in this article can be compared with similar algorithms more intuitively and effectively.

Solutions to global optimal path

The main characteristic of global routing is to build MCKP model, and MCKP belongs to non-deterministic polynomial complete (NP-C) problem; therefore, how to choose an appropriate method to solve the problem is the key issue. In general, classical algorithms solving knapsack problem are GA, SA, binary particle swarm optimization (BPSO), and so on. Among them, GA adopts natural genetic mechanism and has strong global searching capability. However, the algorithm tends to appear premature phenomenon in the process of searching; SA adopts the temperature change model of thermodynamic system and avoids falling into the local optimal solution by introducing Metropolis rules in iterative process. But the convergence speed is getting slower when the problem size is getting bigger. The particle swarm optimization (PSO), which appears later than the first two, has been a popular evolutionary algorithm for many years. Different from other evolutionary algorithms, PSO does not use evolutionary operators for individuals. Instead, each individual is viewed as a particle in N-dimensional search space, and the optimal solution is found based on the direction of movement of the optimal particle. PSO has been widely applied to many fields, and many versions have been proposed. BPSO is one of them and mainly used to solve the constraint problem in discrete space. The performance of BPSO is improved by binary hybrid topology particle swarm optimization (BHTPSO),³⁶ in which the convergence speed is accelerated while avoiding the local optimal solution achieved, and the tests of knapsack problem show that the algorithm has good performance. Therefore, BHTPSO is adopted to solve the global path optimization model.

BHTPSO improves the convergence speed of BPSO and searching method of global optimal solution, which improves the efficiency of solution. There is a correlation between BHTPSO and hybrid topology particle swarm optimization (HTPSO), and each particle in the HTPSO updates particle velocity by using the optimal position ${\vec{p}}_{lbes t_{i}}$ found by the neighbor, as shown in formulas (24) and (25)

${\vec{p}}_{lbes t_{i}} = (p_{lbes t_{i}}^{1}, p_{lbes t_{i}}^{2}, \dots, p_{lbes t_{i}}^{d}, \dots, p_{lbes t_{i}}^{n})$ (24)

$\begin{matrix} v_{i}^{d} (t + 1) = w (t) \times v_{i}^{d} (t) + c_{1} (t) \times ran d_{1} \\ \times (p_{bes t_{i}}^{d} (t) - x_{i}^{d} (t)) + c_{2} (t) \\ \times ran d_{2} \times (p_{lbes t_{i}}^{d} (t) - x_{i}^{d} (t)) \end{matrix}$ (25)

The next position of each particle can be calculated according to current position $x_{i}^{d} (t)$ , next velocity $v_{i}^{d} (t + 1)$ , and the optimal position founded by group, as shown in formulas (26) and (27)

${\vec{p}}_{gbest} = (p_{gbes t}^{1}, p_{gbes t}^{2}, \dots, p_{gbes t}^{d}, \dots, p_{gbes t}^{n})$ (26)

$\begin{matrix} x_{i}^{d} (t + 1) = x_{i}^{d} (t) + v_{i}^{d} (t + 1) + c_{3} (t) \times \\ ran d_{3} \times (p_{gbes t}^{d} (t) - x_{i}^{d} (t)) \end{matrix}$ (27)

In formula (25), w means inertia weight, which can be calculated in formula (28)

$w (t) = w_{\max} - \frac{t \times (w_{\max} - w_{\min})}{T}$ (28)

wherein t and T mean the number of current iteration and the total number of iteration, respectively. Moreover, c₁, c₂, and c₃ are acceleration factors and can be updated according to formula (29)

$c_{j} (t) = c_{j \min} + \frac{(c_{j \max} - c_{j \min})}{T} \times t, j = 1, 2, 3$ (29)

The best position for each particle in HTPSO can be calculated through its best individual experience ${\vec{p}}_{bes t_{i}}$ , its best neighbor experience, and the group’s ${\vec{p}}_{gbest}$ .

In BHTPSO, the velocity of a particle can be calculated from formula (30), and the velocity is related to varied probability between 0 and 1. The “0” value of velocity indicates that the particle position is good and does not change; the probability function is shown in Figure 6

$S (a) = | \tanh (a) |$ (30)

Figure 6.

Probability function.

In BHTPSO, if there is no change for optimal position in many iterations found by multi-particle, we can add a value to formula (30) to accelerate convergence rate and jump out of the local optimum, and then the value can be defined in formula (31)

$E = \erf (\frac{NF}{T^{'}}) = \frac{2}{\sqrt{π}} \int_{0}^{\frac{NF}{T^{'}}} e^{- t^{2}} dt$ (31)

Therefore, the next position of each particle can be calculated by formula (32). The global optimization path can be obtained through calculation above

$\begin{matrix} a_{i}^{d} (t + 1) = v_{i}^{d} (t + 1) + c_{3} (t) \times ran d_{3} \times \\ (p_{gbest}^{d} (t) - x_{i}^{d} (t)) \\ S (a_{i}^{d} (t + 1)) = E + (1 - E) \times | \tanh (a_{i}^{d} (t + 1)) | \\ \begin{matrix} if & ran d_{4} \end{matrix} < S (a_{i}^{d} (t + 1)) \\ \begin{matrix} \begin{matrix} then & x_{i}^{d} (t + 1) \end{matrix} \end{matrix} = complement (x_{i}^{d} (t)) \\ \begin{matrix} else & x_{i}^{d} (t + 1) = x_{i}^{d} (t), & for i = 1, 2, \dots, N \end{matrix} \end{matrix}$ (32)

Complexity analysis

Complexity of BHTPSO, including one is problem size, which depends on the number of particles N₁, maximum iterations N₂, and dimension N₃. The other is computation steps, including calculation of parameters such as position and velocity. So complexity is O(N₁×N₂×N₃+N₂+N₁×N₂); the time complexity is a function of solution for problem size, and therefore, complexity of BHTPSO is O(N₁×N₂×N₃).

Description of process of HAR-SDN

The process of HAR-SDN can be described, as shown in Figure 7.

Figure 7.

Description of HAR-SDN.

Experiments and analysis

We design a test bed in view of structural characteristics of the model, and the schematic diagram shown in Figure 8 is composed of two computers, program development board and a number of sensors. The development board is the dedicated network development platform for the wireless sensor, with Processor cc2480, as shown in Figure 9. Moreover, development tool IAR Embedded Workbench is also adopted; each development board can be matched with several wireless sensors, as shown in Figure 10. Computer 1 runs SDN controller with CPU Intel i7, 8G DDR4 memory, Windows 7, and 64 bit, and controller is developed by Java program and using expended OpenFlow protocol; network topology information is stored in a JGraphT’s Graph object. Computer 2 runs the OMNeT++ simulator. Because the number of sensors is limited in physical testing, this article adopts the way combining physical testing and simulation experiments to test performance of algorithms proposed under different scenarios. In this experiment, we used up to 500 sensor nodes for testing. If we want to test a large-scale sensor network, such as thousands of nodes, method of multi-controller cooperation³⁷ can be adopted to improve network scalability and ensure the scheduling performance of the algorithm.

Figure 8.

Schematic diagram of test bed.

Figure 9.

WSN development board.

Figure 10.

Wireless sensor.

This article compares two routing algorithms LEACH and SAR (Sequential Assignment Routing) with HAR-SDN. LEACH is responsible for prolonging lifetime of network through scheduling of the cluster head; SAR is the first routing protocol with Quality of Service (QoS) awareness.

Physical test

Two scenarios are adopted in physical test and the parameters are shown in Table 1. Due to the limitation of the number of sensors, meanwhile, in order to ensure the validity of local routing as well as test the effect of global routing under different number of clusters, we set three sensor nodes for each cluster, and the number of clusters changes with the total number of sensors. Sensor nodes are deployed in a preset manner, and test indexes include network lifetime and throughput.

Lifetime

Table 1.

Parameters of physical test.

	Scenario 1	Scenario 2
Number of nodes	9	30
Number of clusters	3	10
Number of nodes in the cluster	3	3
Movement speed oftarget node	0.1 m/s	0.1 m/s
Sampling frequency	1 time/3 s	1 time/3 s
Communication radiusof node	10 m	10 m
Initial energy of node	5100 J	5100 J
Test rate	50 kb/s	50 kb/s
Coordinate of sink node	(0, 0)	(0, 0)
Initial coordinate of thetarget node	(50, 50)	(50, 50)
Coverage of WSN	50 m × 50 m	50 m × 50 m

WSN: wireless sensor network.

Lifetime is an important index to assess network energy consumption. Figures 11 and 12 show the proportions of ineffective nodes accounted for in total nodes due to energy exhaustion in the case of 9 nodes and 30 nodes, respectively. In the case of nine nodes, SAR has the shortest lifetime, followed by HAR-SDN and LEACH (the longest one). Due to the small number of sensor nodes, there is no significant difference in transmission path of all algorithms, and the main difference comes from the complexity of algorithm operation. LEACH realizes load sharing by rotation of cluster head. SAR is an algorithm with high complexity; all nodes need to exchange information so as to construct a tree rooted at nodes within communication radius of sink, and at the same time, they calculate energy consumption and QoS of nodes along the route. In terms of HAR-SDN, the calculation cost is borne by SDN controller, and the network needs to upload the operation information and distribute scheduling strategies ultimately.

Figure 11.

Lifetime results of physical test in nine nodes scenario.

Figure 12.

Lifetime results of physical test in 30 nodes scenario.

In 30 nodes scenario, due to simple, LEACH is not easy to get more nodes to balance energy consumption through the scheduling of cluster heads, therefore, compared with other two algorithms, the lifetime of LEACH is the shortest. SAR is a multi-path routing protocol, and despite of its higher complexity than others, its lifetime is longer than LEACH because the nodes are selected for energy in routing process and optimize energy of nodes around the sink. The cost of HAR-SDN mainly consists of communication and calculation. The computational cost of the algorithm is reduced thanks to the adoption of SDN controller; compared with SAR, there is no significant increase of communication cost of node. For SAR, which is designed according to fixed routing, it is difficult to adapt to the requirements of changing routing, by contrast, the HAR-SDN can routing on demand.

2. Throughput

Throughput is an index to evaluate network communication performance. As shown in Figure 13, when test rate is 50 kb/s, there are so many transmission paths for selection in the case of fewer transmission nodes, and therefore, the throughput is not significantly differentiated. As shown in Figure 14, with increase in nodes, the throughput is low because LEACH fails to consider other factors other than energy consumption. The SAR satisfies QoS by using priority of data, but improvement to throughput is limited. Considering communication characteristics of WSN, HAR-SDN selects transmission nodes with high throughput to transmit data so as to construct high-speed transmission route. When the number of network nodes is large, the performance is more obvious. In a word, the throughput of HAR-SDN algorithm in three algorithms is the highest.

Figure 13.

Throughput in nine nodes scenario.

Figure 14.

Throughput in 30 nodes scenario.

Simulation test

In order to further verify performance of the algorithm, we also conduct a simulation experiment on the basis of physical test. The experimental parameters are shown in Table 2. Considering the distribution of sensor nodes, we distribute sensor nodes to each cluster as evenly as possible, so that the number of sensors in each cluster is as close as possible. Meanwhile, the specific distribution ratio of allocation scheme is as shown in formula (33)

$\frac{N_{a}}{N_{c}} = α, α \in [4, 5]$ (33)

Table 2.

Parameters of simulation test.

	Scenario 3	Scenario 4
Number of nodes	200	500
Number of clusters	7	10
Number of nodes inthe cluster	28–29	50
Movement speed oftarget node	0.3 m/1 s	0.3 m/1 s
Sampling frequency	1 time/2 s	1 time/2 s
Communication radiusof node	5 m	5 m
Initial energy of node	100 J	100 J
Test rate	200 kb/s	200 kb/s
Coordinate of sink node	(5, 5)	(5, 5)
Initial coordinate ofthe target node	(280, 280)	(280, 280)
Coverage of WSN	300 m × 300 m	300 m × 300 m

WSN: wireless sensor network.

where N_a represents the average number of sensor nodes in a cluster, N_c represents the number of clusters, and α is the threshold within [4,5].

Lifetime

Respectively, we have tested 200 and 500 node scenarios, as shown in Figures 15 and 16, and wherein the proportion of ineffective nodes is limited to 35%. Experimental results show that with increase of nodes, the lifetime of various algorithms is prolonged. In contrast, the lifetime of LEACH is the shortest, followed by SAR and HAR-SDN (the longest one), which is consistent with the results of physical test. Due to the design of the algorithm, it is difficult for LEACH to schedule more nodes to participate in routing process, consuming a plenty of energy for partial nodes, and therefore, the lifetime for network is short. SAR considers both QoS and energy, and carries out multi-path routing. The initial cost for algorithm is high, but the cost shall be lower as for fixed routing network; besides, it is hard to guarantee cost for ever-changing routing. The experimental results show that HAR-SDN is superior to SAR, which can be explained by following reasons: (1) Initialization: initialization stage of algorithm plans all local paths without frequent modifying routing; (2) On-demand routing: global optimization, based on local paths, makes decisions according to target location, reducing the cost of route planning; (3) Controller is responsible for calculation: the controller components are responsible for main computing load, reducing the cost of WSN, and all nodes only need to transmit basic state information; and (4) Routing scheduling algorithm involves in calculation by viewing node energy as an important indicator.

2. Throughput

Figure 15.

Lifetime simulation for 200 nodes.

Figure 16.

Lifetime simulation for 500 nodes.

As shown in Figures 17 and 18, the test results in three algorithms are consistent with that of physical test. LEACH fails to consider the transmission rate factor, so its throughput is the lowest. SAR adopts multi-route QoS strategy but cannot guarantee the high-speed data transmission during target tracking. The throughput of HAR-SDN is the largest in three algorithms. Adopting the ways combining local path and global optimization and viewing throughput and energy consumption as scheduling objectives, HAR-SDN covers all optimal paths among clusters through local optimization path, and global routing is achieved orienting to the target, improving route efficiency and flexibility. The performance of HAR-SDN is obvious with the increase of network node density.

Figure 17.

Throughput simulation for 200 nodes.

Figure 18.

Throughput simulation for 500 nodes.

Conclusion

With the increase of application demand of WSN, the acquisition of multimedia information and real-time information transmission in the process of target tracking requires the network to provide higher throughput, so this article proposes a hierarchical multi-objective adaptive routing algorithm based on SDN. The algorithm uses dual index of energy and throughput to achieve higher transmission rate under effective energy consumption, and adopts a way of combining the local routing and global routing under SDN. Based on the optimal path set between clusters, the global route can be constructed on-demand according to the movement of target. The test bed has two parts: physical test and simulation test. In physical test, the network lifetime and the throughput of HAR-SDN are better than that of LEACH and SAR. The results of the simulation test are consistent with the physical test and achieve the expected design performance. In future work, a deep learning approach will be used to provide WSN with more intelligent self-configuration capabilities to cope with changes in the environment.

Footnotes

Handling Editor: Chase Wu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This work is supported by the National Natural Science Foundation of China (61403109),the Specialized Research Fund for the Doctoral Program of Higher Education of China (20112303120007),and the Scientific Research Fund of Heilongjiang Provincial Education Department (12541169).

References

Vasuhi

Vaidehi

. Target tracking using interactive multiple model for wireless sensor network. Inform Fusion 2016; 27: 41–53.

Zhou

Hoa

. Event-triggered cooperative target tracking in wireless sensor networks. Chin J Aeronaut 2016; 29(5): 1326–1334.

Oracevic

Akbas

Ozdemir

. Secure and reliable object tracking in wireless sensor networks. Comput Secur 2017; 70: 307–318.

Chen

MZQ

. Distributed estimation and control for two-target tracking mobile sensor networks. J Franklin Inst 2017; 354(7): 2994–3007.

Shi

Chen

Lin

. Probabilistic coverage based sensor scheduling for target tracking sensor networks. Inform Sciences 2015; 292: 95–110.

Lersteau

Rossi

Sevaux

. Minimum energy target tracking with coverage guarantee in wireless sensor networks. Eur J Oper Res 2017; 265(3): 882–894.

Lersteau

Rossi

Sevaux

. Robust scheduling of wireless sensor networks for target tracking under uncertainty. Eur J Oper Res 2016; 252(2): 407–417.

Sleep

Dadej

Lee

. Representing arbitrary sensor observations for target tracking in wireless sensor networks. Comput Electr Eng 2016; 64: 354–364.

Yan

. Sensor scheduling in target tracking. Lect Notes Contr Inf 2015; 2015: 2023–2025.

10.

Guo

Yuan

Han

. Sensor selection based on maximum entropy fuzzy clustering for target tracking in large-scale sensor networks. IET Signal Process 2017; 11(5): 613–621.

11.

Rahman

Anwar

Pramanik

et al . A survey on energy efficient routing techniques in wireless sensor network. In: Proceedings of the 15th international conference on advanced communication technology, PyeongChang, South Korea, 27–30 January 2013, pp.200–205. New York: IEEE.

12.

Keskin

Altınel

İK

Aras

et al . Wireless sensor network lifetime maximization by optimal sensor deployment, activity scheduling, data routing and sink mobility. Ad Hoc Netw 2014; 17(3): 18–36.

13.

Anitha

Kamalakkannan

. Enhanced cluster based routing protocol for mobile nodes in wireless sensor network. In: Proceedings of the international conference on pattern recognition, informatics and mobile engineering, Salem, India, 21–22 February 2013, pp.187–193. New York: IEEE.

14.

Zhang

. A clustering routing protocol for energy balance of wireless sensor network based on simulated annealing and genetic algorithm. Int J Hybrid Inform Technol 2014; 7: 71–82.

15.

Han

Zhang

et al . A general self-organized tree-based energy-balance routing protocol for wireless sensor network. IEEE T Nucl Sci 2014; 61(2): 732–740.

16.

Karaboga

Okdem

Ozturk

. Cluster based wireless sensor network routing using artificial bee colony algorithm. Wirel Netw 2012; 18(7): 847–860.

17.

Luo

Tan

Quek

TQS

. Sensor OpenFlow: enabling software-defined wireless sensor networks. IEEE Comm Lett 2012; 16(11): 1896–1899.

18.

Galluccio

Milardo

Morabito

et al . SDN-WISE: design, prototyping and experimentation of a stateful SDN solution for WIreless SEnsor networks. Comput Commun 2015; 22(4): 513–521.

19.

Jagadeesan

Krishnamachari

. Software-defined networking paradigms in wireless networks: a survey. ACM Comput Surv 2014; 47(2): 1–11.

20.

Zeng

Miyazaki

Guo

et al . Evolution of software-defined sensor networks. In: Proceedings of the 9th international conference on mobile ad-hoc and sensor networks, Dalian, China, 11–13 December 2013, pp.410–413. New York: IEEE.

21.

Liang

. Wireless network virtualization: a survey, some research issues and challenges. IEEE Commun Surv Tut 2015; 17(1): 358–380.

22.

Jacobsson

Orfanidis

. Using software-defined networking principles for wireless sensor networks. In: Proceedings of the 11th Swedish national computer networking workshop, Karlstad, 28–29 May 2015. Digitala Vetenskapliga Arkivet (DiVA).

23.

Wang

Chen

et al . An energy-efficient SDN based sleep scheduling algorithm for WSNs. J Netw Comput Appl 2016; 59: 39–45.

24.

Olivier

Carlos

Florent

. SDN based architecture for clustered WSN. In: Proceedings of the 9th international conference on innovative mobile and internet services in ubiquitous computing, Blumenau, Brazil, 8–10 July 2015, pp.342–347. New York: IEEE.

25.

Costanzo

Galluccio

Morabito

et al . Software defined wireless networks: unbridling SDNs. In: Proceedings of the European workshop on software defined networking, Darmstadt, 25–26 October 2012, pp.1–6. New York: IEEE.

26.

Wang

Gao

Zhang

et al . Particle filter based device free localisation and tracking for large scale wireless sensor networks. Int J Sens Netw 2015; 19(3): 194–203.

27.

Pak

Ahn

Shmaliy

et al . Improving reliability of particle filter-based localization in wireless sensor networks via hybrid particle/FIR filtering. IEEE T Ind Inform 2015; 11(5): 1089–1098.

28.

Zhu

Zhao

Liu

et al . A new improved filter for target tracking: compressed iterative particle filter. Nat Sci 2011; 3(4): 301–306.

29.

Haenggi

. On routing in random Rayleigh fading networks. IEEE T Wirel Commun 2005; 4: 1553–1562.

30.

Hsu

Rubin

. On routing and rate control strategies in wireless multi-hop random access networks. In: Proceedings of the international conference on communications, Glasgow, 24–28 June 2007, pp.3395–3400. New York: IEEE.

31.

Hsu

Rubin

Cross-layer multi-rate routing strategies in wireless multi-hop random access networks. In: Proceedings of the global telecommunications conference, Washington, DC, 26–30 November 2007, pp.609–613. New York: IEEE.

32.

Chen

Wang

et al . BP neural network based continuous objects distribution detection in WSNs. Wirel Netw 2016; 22(6): 1917–1929.

33.

Mehmood

Umar

. ELDC: an artificial neural network based energy-efficient and robust routing scheme for pollution monitoring in WSNs. IEEE T Emerg Top Comput 2017; PP(99): 1.

34.

Jolai

Ghanbari

. Integrating data transformation techniques with Hopfield neural networks for solving travelling salesman problem. Expert Syst Appl 2010; 37(7): 5331–5335.

35.

Toumpis

Gitzenis

Load balancing in wireless sensor networks using Kirchhoff’s voltage law. In: Proceedings of the INFOCOM, Rio de Janeiro, Brazil, 19–25 April 2009, pp.1656–1664. New York: IEEE.

36.

Beheshti

Shamsuddin

Hasan

. Memetic binary particle swarm optimization for discrete optimization problems. Inform Sciences 2015; 299: 58–84.

37.

Kobo

Hancke

Abu-Mahfouz

. Towards a distributed control system for software defined wireless sensor networks. In: Proceedings of the 43rd annual conference of the IEEE industrial electronics society, Beijing, China, 29 October–1 November 2017. New York: IEEE.