Open AccessArticle

Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities

Esteban Inga

^1,*

Juan Inga

and

Andres Ortega

Postgraduate Department, Smart Grid Research Group (GIREI), Universidad Politécnica Salesiana, Quito 170525, Ecuador

Telecommunications Engineering, Telecommunications Research Group (GITEL), Universidad Politécnica Salesiana, Quito 010102, Ecuador

Telecommunications Engineering, Center for Studies and Sustainable Development (CEDS), Universidad Tecnológica Ecotec, Guayaquil 092301, Ecuador

Author to whom correspondence should be addressed.

Sensors 2021, 21(14), 4692; https://doi.org/10.3390/s21144692

Submission received: 7 June 2021 / Revised: 30 June 2021 / Accepted: 3 July 2021 / Published: 9 July 2021

(This article belongs to the Section Sensor Networks)

Download

Browse Figures

Versions Notes

Abstract

Citizens are expected to require the growth of multiple Internet of Things (IoT) -based applications to improve public and private services. According to their concept, smart cities seek to improve the efficiency, reliability, and resilience of these services. Consequently, this paper searches for a new vision for resolving problems related to the quick deployment of a wireless sensor network (WSN) by using a sizing model and considering the capacity and coverage of the concentrators. Additionally, three different routing models of these technology resources are presented as alternatives for each WSN deployment to ensure connectivity between smart meters and hubs required for smart metering. On the other hand, these solutions must reduce costs when this type of wireless communication network is deployed. The present work proposes various optimization models that consider the physical and network layers in order to integrate different wireless communication technologies, thus reducing costs in terms of the minimum number of data aggregation points. Using a heterogeneous wireless network can reduce resource costs and energy consumption in comparison to a single cellular technology, as proposed in previous works. This work proposes a sizing model and three different models for routing wireless networks. In each case, constraints are evaluated and can be associated with different real-world scenarios. This document provides an optimization model that encompasses all of the proposed constraints; due to the combinatorial nature of the problem, this would require a heuristic technique.

Keywords:

smart metering; internet of things; MST; optimization; routing; smart cities; sizing; wireless sensor networks

1. Introduction

This paper outlines the need for rapid deployment of wireless sensors for applications of the Internet of Things (IoT), which are particularly required in smart cities where, in each case, rapid deployment, low costs, and the possibility of using a variety of technological solutions are required [1,2].

IoT applications for smart cities have critical importance; among these applications, some examples include medical assistance for patients with contagious viruses (COVID-19), smart metering of electricity, home delivery of parcels (medicines, food), and “education 4.0”. Consequently, there are areas of opportunity for advanced technologies and techniques that support innovative services with adequate performance to ensure the control and operations of devices with the possibility of wireless communication [3,4]. Furthermore, telecommunication technologies require rapid deployment in order to cover the demand for smart city applications, such as those mentioned above.

Thus, the central offices of local governments require the monitoring and surveillance of sensors placed in previously defined areas or strata of cities to make the operation of services effective, such as traffic management systems, health management (telemedicine), rubbish collection systems, and image recognition systems, among others [5,6].

Therefore, the deployment and routing of a wireless sensor network (WSN) that is responsible for sending and receiving information to the central office must ensure interconnection with each sensor because the information often goes through several sensors before it reaches the central office. This situation indicates that it is necessary to optimize the number of hops in order to reduce energy consumption in the routing process [7].

Most research in this area is related to IoT in the frame of prototypes and various applications with sensors as emerging technologies, but when it is required to scale to services for smart cities, the context changes because it involves the interconnection of multiple sensors installed for various services. Furthermore, information from multiple sensors must be shared with a central office; therefore, the need to determine the size of a wireless sensor network is justified.

Recent research presented possible technologies for specific uses of IoT in smart cities, such as a low-power wide-area network (LPWAN) known as LoRa, which is the type of LPWAN technology that is most often suggested due to its low power consumption and the ease of performing multiple hops. This is a trendy aspect, and it marks the possibility of heterogeneous wireless sensor networks. The present work provides the possibility of promptly using several wireless sensors for IoT applications in smart city services with management from the central offices of a public or private company through optimal sizing and routing [8,9,10].

Thus, in this work, we present a sizing model that minimizes the number of concentrators or data aggregation points (DAPs) in the set of candidate sites where these DAPs can be installed. The poles or peaks of the electrical distribution network that have an approximate height of 10–15 m are assumed as candidate sites. Furthermore, the DAP capacity considers the maximum number of sensors simultaneously connected in each wireless technology’s coverage radius for each DAP. Therefore, this constraint is incorporated into the optimization model.

Previous research showed the routing stage of the resources to be interconnected with the central office of a public or private company can incorporate a heterogeneous wireless sensor network that accommodates multi-hops [11,12].

The proposed scenario considers a series of sensors that can be deployed in an urban area and used in various innovative city applications, such as in fixed rubbish collectors, electric energy meters, drinking water meters, charging centers for electric vehicles, electric energy micro-grids, CO₂ emission sensors, and vibration sensors in footbridges, among others. Therefore, the principal idea will be to transmit the information from these sensors to the central offices of public or private companies [13,14].

The main contribution of this paper is a novel idea that enables the routing of several IoT sensors in an authentic and geo-referenced scenario in which a heterogeneous wireless sensor network can be deployed for multiple smart city services. This paper describes the scenario and the problem with a mathematical approach. It illustrates simulation results to demonstrate the evaluation of the system with respect to variations in input variables, such as the numbers of DAPs and sensors, DAP capacity, DAP coverage, and capacity of the links in comparison with related work [15].

This article is organized as follows. Section 2 describes the related work. Section 3 describes the problem’s formulation. In Section 4, an analysis of the simulation results is carried out. Finally, we conclude this paper in Section 5.

2. Related Work

The present work proposes models based on the optimization of the sizing and routing of telecommunications resources in order to achieve connectivity between wireless sensors, concentrators, and the central offices of public or private companies. Figure 1 emphasizes the complete process required for the deployment of a WSN.

Earlier work presented classical wireless sensor network routing solutions, including the novelties of reducing energy consumption with short-range wireless technologies. In addition, hardware prototypes concerned with the interoperability of communication protocols among wireless sensors were presented [4,16].

However, routing can create various logical topologies according to the need for scalability and the use of multi-layers depending on the number of nodes and the physical complexity of the network [17].

There have been contributions to sensor fault location and applications for the reconstruction of a sampled signal with a percentage of measured data through compressed sensing techniques, as presented by [18]. Other contributions sought to improve the quality of service in packet forwarding by using multi-hop delays, and other work addressed the types of wireless sensor networks employed in the IoT. In addition, it is essential to remember that all applications must be scalable, as noted in [19]. There were also contributions to the dimensioning of wireless sensor networks, as presented in [20]. Furthermore, when deploying a wireless network for smart cities, for more sensors to be incorporated daily to generate new services, the WSN must be flexible, and the proposed algorithms must converge to the optimal solution on time for fast management.

The authors note the possibility of using RFID-enabled sensors in an unlicensed band, which can reduce the costs for such applications; however, the interoperability between devices from various manufacturers is not open, and this type of technology was first proposed for electricity metering and for rubbish collection in smart cities.

Other work related to IEEE 802.15.4 (Zigbee) offered alternatives for the achievement of the rapid deployment of a wireless communications network and presented the possibility of implementing network topologies that support various types of topologies, such as star, extended star, or mesh topologies. In addition, other work proposed heterogeneous solutions that sought to ensure that investment in communications infrastructure was minimal. The proposals were hybrid networks based on fiber-optic and wireless networks—called FiWi—or networks based on WiFi and Zigbee [21].

Regarding the technologies for WSNs, data concentrators are gateways, and are also used in LPWAN technologies; therefore, the process of optimal network sizing can also be modeled to adequately locate these concentrators with the same rigor as that in the technologies discussed in the previous paragraph [22]. A routing analysis will determine the technology used in order to interconnect the DAPs required in the WSN’s deployment while considering a star topology among the sensor nodes and gateways.

There are works where the optimization problems were relaxed with clustering, and these were presented in [23,24,25,26,27,28,29].

The optimization problem is of the combinatorial type due to its complexity, and it is called an NP-complete problem. Consequently, some authors proposed heuristic algorithms to explore local optimization solutions that are close to the global solution. On the other hand, there was risk in different works that presented the use of clusters. There were sensors without connectivity in their proposed solutions, even though they previously managed to minimize the cost of energy consumption [23,24]. Methods such as k-means or Kmedoids are not balanced or give multiple answers.

Consequently, other works, such as that of [30], showed the integration of a network from a cross-layer between the access control layer and the routing protocol used to reduce the load of information flow in wireless links. This type of work presents a significant achievement in reducing congested links and, thus, allowing the redirection of data flows in the less saturated network. In this sense, we could consider a multi-layer solution in which the physical layer and the network layer interconnect with each other when sizing and routing the DAPs while taking the wireless link capacity and its coverage radius into consideration.

The need to connect sensors for various applications should not be subject only to the deployment of a unique wireless communication network because using existing technologies reduces the investment cost. Seeking a heterogeneous wireless network solution incorporates the possibility of integrating technologies that facilitate data transmission between sensors and the central office, as is the case of applications linked to the smart metering of electricity, water, or gas.

Graph theory provides an exciting alternative for achieving novel solutions, but above all; it develops solutions with a low computational cost, also facilitates scalability when increasing the number of sensors.

Table 1 refers to the scientific articles related to the relaxation of an NP-complete problem. In addition, the differences between the present work and other proposals are presented.

3. Problem Formulation

This work is divided into two sections that offer novel contributions to the rapid implementation of WSNs required for various services in smart cities. This section divides the model into (a) WSN sizing and (b) WSN routing.

3.1. Wireless Sensor Network Sizing

For WSN sizing, a square area of L by L m in an open space is assumed. The data aggregation points (DAPs) will be located in this area to achieve the connectivity of wireless IoT sensors. The DAPs are assumed to enable the connectivity of the sensors within a coverage radius of R m; consequently, the wireless sensors can be at any position within the bounded region.

The DAPs can be located at any position within the region and installed on street lighting poles or elevated areas. In this way, the mathematical model minimizes the cost in terms of the lowest number of DAPs. Moreover, the variables used to cover the wireless sensors are described below. A set of N sensors is installed in different areas of the region; additionally, we consider a set of M possible locations or candidate sites where the are DAPs deployed.

The possible location that was previously described is a candidate for a place where a DAP could be installed or sited; therefore, it will not be mandatory for a DAP to be installed at that location unless it covers a percentage of the sensors. The model defines that a wireless sensor is covered if it is within a distance R from at least one DAP; the Haversine distance (

d i s t_{h a v e r s i n e}

) is used to consider the Earth’s curvature for geo-referenced points [31].

A candidate site is considered an active site if a DAP is enabled or installed on the candidate site. Each DAP has a limited capacity in terms of the sensors. From the above details, an optimization problem is defined that aims to find the minimum number of active sites such that at least a percentage P of the sensors are covered.

It is necessary to define a set

S = {s_{1}, s_{2}, s_{3}, \dots, s_{M}}

of candidate sites, where the j-th position is given by

(x s_{j}, y s_{j})

. A set of

D = {d_{1}, d_{2}, \dots, d_{N}}

sensors or wireless devices is also defined. The position of the i-th sensor is given by

(x d_{i}, y d_{i})

We define the quantity

α_{j, i} \in {0, 1}

, which implies that if sensor i is covered by DAP j, then the value is 1; otherwise, the value is 0. Thus, for each candidate site, the quantity

Z_{j} \in {0, 1}

is defined, which implies that the value is 1 when candidate site j is an active site.

In the same way, for each sensor

d_{i}

, the quantity

Y_{i} \in {0, 1}

is defined when the value is one, which indicates that the sensor is covered by at least one candidate site. C is defined as the capacity of the DAPs to accommodate sensors. The optimization model for the sizing is presented below:

Objective function:

\begin{matrix} min \sum_{j = 1}^{M} Z_{j}, \end{matrix}

(1)

which is subject to:

\begin{matrix} Y_{i} = \sum_{j = 1}^{M} X_{j, i}; & \forall i \in D; \end{matrix}

(2)

\begin{matrix} \sum_{i = 1}^{N} X_{j, i} \leq C \cdot Z_{j}; & \forall j \in S; \end{matrix}

(3)

\begin{matrix} \sum_{i = 1}^{N} Y_{i} \geq N \cdot P; & \forall i \in D; \end{matrix}

(4)

\begin{matrix} X_{j, i} \leq α_{j, i} \cdot Z_{j}; & \forall j \in S; \forall i \in D; \end{matrix}

(5)

where

-: The percentage P of sensors are covered in a delimited area or region.
-: The term N defines the number of sensors in a delimited area or region.
-: The term M defines the number of candidate sites in a delimited zone or region.
-: The number of covered DAPs is $α_{j, i} \in {0, 1}$ . If a sensor i is covered by a DAP j, $α_{j, i}$ is 1 and 0 otherwise.
-: For each $s_{j}$ candidate site, $Z_{j} \in {0, 1}$ is defined, where $Z_{j}$ is 1 if the candidate site is active and 0 otherwise.
-: $X_{j, i}$ indicates if sensor i is connected to DAP j. $X_{j, i}$ is 1 if the connection exists, and 0 otherwise.

Before applying the optimization model that aims to minimize the number of candidate sites for the DAPs, it is necessary to make an on-site visit to verify the availability of the candidate sites for use as inputs for the optimization model.

3.2. Wireless Sensor Network Routing

This work suggests three sub-models for the routing of wireless sensor networks with variations that are important to note when planning the deployment of a communication network.

3.2.1. Routing Based on Graph Theory

A set of sensors is defined and connected using one-way wireless communication links. Then, if a link exists between sensor A and sensor B, it is denoted as

e_{A, B}

; in this way, A can send data directly to B. The link

e_{A, B}

has a weight or distance (Haversine for geo-referencing) that is associated and denoted as

d_{A, B}

Here, the concept of graph theory becomes essential, and we define V as the set of sensors and E as the set of existing links (partial or complete mesh topology). Therefore, graph theory describes

G = (V, E)

as a directed graph that represents a network topology. Below, a data stream must be transmitted from a source sensor named S to a destination sensor called T. This flow is transmitted through the intermediate sensors using existing links. The flow between a pair of sensors

(s, t)

belonging to V represents the information’s source and destination.

Then, if we define a path P of the set of sensors, we will have that

P = {P_{1}, P_{2}, \dots, P_{M}}

such that the links

e_{P k, P k + 1} \in E

. Thus, we define the path length P as

d_{P}

, which is given by

d_{P} = \sum_{k = 1}^{M - 1} d_{P k, P k + 1}

, and define a path for the flow

(s, t)

as a path

P_{s, t}

such that

P_{1} = s

and

P_{M} = t

In addition, the path with the minimum distance is defined as the path

P_{s, t^{*}}

such that

d_{P s, t^{*}} < = d_{P s, t}

for any other possible path

P_{s, t}

. The optimization problem posed in this paper then requires one to find the path with the minimum distance for the flow

(s, t)

To write this optimization problem, it is required to define the variable

X_{i, j}

, where the link

e_{i, j}

is assumed to exist and

X_{i, j}

has a value of 1 if the link

(i, j)

belongs to the path

P_{s, t^{*}}

; otherwise, the value is 0. Similarly, for a sensor

i \in V

, we define

E_{i, o u t}

as the set of outgoing links of i. We define

E_{i, i n}

as the set of incoming links of i.

Objective function:

\begin{matrix} min \sum_{(i, j) \in E} d_{i, j} X_{i, j}, \end{matrix}

(6)

which is subject to:

\begin{matrix} \sum_{j | e_{i, j} \in E_{i, o u t}} X_{i, j} - \sum_{j | e_{i, j} \in E_{i, i n}} X_{i, j} = α_{i}; & \forall i \in V; \end{matrix}

(7)

α_{i} = \{\begin{matrix} 1, si i = s \\ - 1, si i = t \\ 0, si i \neq s, i \neq t \end{matrix}

(8)

3.2.2. Multicast Routing

This second model proposed for the routing of the wireless sensor network considers a set of sensors connected by bi-directional communication links. For example, if between sensor A and sensor B, there is a link denoted as

e_{A, B}

, then A can send data directly to B and B can send information directly to A. Furthermore, the link

e_{A, B}

will have a cost, weight, or distance associated with it and is given by

d_{A, B}

It is important to note that the link

e_{A, B}

is arbitrary in the ordering of a and b; that is,

e_{A, B}

represents the same as

e_{B, A}

; therefore, the link can be named as

e_{i}

, where i is the index of the link.

Now, we define V as the set of sensors, E as the set of existing links, and

G = (V, E)

as an undirected graph; additionally, this represents a set of unordered pairs of elements of V and, thus, the network topology. An undirected graph indicates that the links are all bidirectional. For this stage, the optimization model seeks to find a minimum-cost spanning tree, which is defined as an undirected graph in which a single path connects any two vertices; that is, a tree is a connected graph with no loops.

Hence, for this problem, we define the set

V = {V_{1}, V_{2}, \dots, V_{N}}

as the set of wireless sensors and we define a tree as a set of links

A = {e_{1}, e_{2}, \dots, e_{N - 1}}

such that the links

e_{i}

∈ E. According to this, the cost of tree A can be defined as

d_{A}

and is represented by

d_{A} = \sum_{i = 1}^{N - 1} d_{i}

Thus, the minimum-cost tree is defined as tree

A^{*}

such that “

d_{A^{*}} < = d_{A}

” for any other possible tree. The problem started as the need to find a minimum-cost tree, which requires the definition of certain variables, such as

X_{i, j}

, and the establishment of the link

e_{i, j}

that exists and where

X_{i, j}

has a value of 1 when the link

(i, j)

belongs to the solution tree A. Otherwise, the value is 0; furthermore, a subset B of any sensors belonging to the same set A is defined within the group of sensors V.

Thus, the problem is defined as the cost minimization of the chosen links and is subject to the constraint that the sensors are connected with

N - 1

links, where N is the number of sensors belonging to V.

Objective function:

\begin{matrix} min \sum_{(i, j) \in E} d_{i, j} X_{i, j}, \end{matrix}

(9)

which is subject to:

\begin{matrix} \sum_{e_{i, j} \in E} X_{i, j} = N - 1; \end{matrix}

(10)

\begin{matrix} \sum_{e_{i, j} \in E, i \in B, j \in B} X_{i, j} \geq 1; \forall B \subset V \end{matrix}

(11)

3.2.3. Multiple Flow Routing

For the third routing case of the wireless sensor network, a set of sensors is assumed to be connected via unidirectional wireless links. If a link exists between node A and node B, denoted as

e_{A, B}

, then A can send data directly to B. The link

e_{A, B}

has an associated weight or distance and is given by

d_{A, B}

; additionally, the capacity of the link

e_{A, B}

is given by

C_{A, B}

. Thus, V is defined as the set of sensors, E as the set of existing links, and

G = (V, E)

as a directed graph that represents the network topology.

On the other hand, we assume a set of data flows

F = {f_{1}, f_{2}, \dots, f_{k}}

that require the transmission of data from a source node

S_{k}

to a destination sensor

T_{k}

; this requirement refers to the link capacity in terms of the flow

F_{k}

and is determined by

R_{k}

. The flow is transmitted through the intermediate sensors by using existing links. A flow between a pair of sensors

f_{k} = (S_{k}, T_{k})

belonging to V represents the source and destination sensors.

To define the optimization model, it is necessary to define a path P as a set of sensors

P = {P_{1}, P 2, \dots, P_{M}}

such that the sensors

e_{P k, P k + 1}

∈ E; in addition, we define the length of the path P as

d_{P}

, which is given by

d_{P} = \sum_{k = 1}^{M - 1} d_{P k, P k + 1}

. We then define the path for the flow

(s, t)

as a path

P_{s, t}

such that

P_{1} = s

and

P_{M} = t

The minimum-distance path is defined as the path

P_{s, t^{*}}

such that

d_{P s, t^{*}} < = d_{P s, t}

for any other possible path

P_{s, t}

. A possible route is defined as a route that contains links that exist within the topology and that can transmit the flows passing through them.

In this way, the optimization problem that seeks to find the minimum-distance path is defined by considering the flows belonging to F.

To determine the problem in the field of optimization, it is required to define the variable

X_{i, j, k}

; for this, it is assumed that the link

e_{i, j}

exists and that

X_{i, j, k}

has a value of 1 if the link

(i, j)

belongs to the path

P_{s k, t k}

; that is, the k-th flow uses the link

e_{i, j}

; otherwise, the value is 0.

Similarly, for a sensor

i \in V

E_{i, o u t}

is defined as the set of outgoing links of i and

E_{i, i n}

is defined as the set of incoming links of i.

Overall, the model supporting the above is as follows:

Objective function:

\begin{matrix} min \sum_{(i, j) \in E} \sum_{k \in F} d_{i, j} X_{i, j, k}, \end{matrix}

(12)

which is subject to:

\begin{matrix} \begin{matrix} \sum_{j |e_{i, j} \in E_{i, o u t}} X_{i, j, k} - \sum_{j |e_{i, j} \in E_{i, i n}} X_{i, j, k} = α_{i, k} \\ \forall i \in V; \forall k \in F \end{matrix} \end{matrix}

(13)

\begin{matrix} \sum_{k \in F} R_{k} \cdot X_{i, j, k} \leq C_{i, j}; \forall (i, j) \in E \end{matrix}

(14)

α_{i, k} = \{\begin{matrix} 1, si i = s_{k} \\ - 1, si i = t_{k} \\ 0, si i \neq s_{k}, i \neq t_{k} \end{matrix}

(15)

In this way, as with multicast routing, one can seek to determine the tree with the minimum cost allowed by the downstream Dijkstra algorithm; however, in this case, it is necessary to subtract the capacity of the links of the current network from the transmission rate of the current flow over the links affected by the same link [32,33].

The pseudocode for the optimal sizing of the wireless sensor network is presented in the

O D R S I

Algorithm 1, and the pseudocode with the optimal routing according to the sizing results is presented in the

O E R S I

Algorithm 2; furthermore, Table 2 summarizes the variables used in Algorithms 1 and 2.

Algorithm 1

O S W S N

: Sizing of Wireless Sensor Networks

Paso: 1

Definitions

Inputs:

$G e o - r e f e r e n c e d C o o r d i n a t e s f o r D A P s a n d s e n s o r s :$

$c o o r d S = \{(x s_{1}, y s_{1}), (x s_{2}, y s_{2}), \dots, (x s_{j}, y s_{j}), \dots, (x s_{M}, y s_{M})\}$ ;
$c o o r d D = \{(x d_{1}, y d_{1}), (x d_{2}, y d_{2}), \dots, (x d_{i}, y d_{i}), \dots, (x d_{N}, y d_{N})\}$ ;
$C_{j}$ , $D A P c a p a c i t y$ ;
R, $r a d i u s o f D A P c o v e r a g e$ ;
P, $c o v e r a g e p e r c e n t a g e$ ;

Output: min

Z_{j}

;

Paso: 2

Set

c o o r d = c o o r d D \cup c o o r d S

;

Paso: 3

Set

d i s t \in

R^{N \times M}; d i s t =

forall j=1 to M

forall i=1 to N

d i s t [i, j] = d i s t_{h a v e r s i n e} (c o o r d (i), c o o r d (j))

;

endforall

Paso: 4

Apply the optimization model for sizing (Equations (1) to (5));

Paso: 5

Return min:

Z_{j}

;

Algorithm 2

O R W S N

: Routing of Wireless Sensor Networks

Paso: 1: Definitions
Inputs: $d m i n = R,$
$G e o - r e f e r e n c e d c o o r d i n a t e s f o r D A P s a n d s e n s o r s :$
$c o o r d S = \{(x s_{1}, y s_{1}), (x s_{2}, y s_{2}), \dots, (x s_{j}, y s_{j}), \dots, (x s_{M}, y s_{M})\}$ ;
$c o o r d D = \{(x d_{1}, y d_{1}), (x d_{2}, y d_{2}), \dots, (x d_{i}, y d_{i}), \dots, (x d_{N}, y d_{N})\}$ ;
Output: $m i n i m a l t r e e c o s t$
Paso: 2: Set $c o o r d = c o o r d D \cup c o o r d S$ ;
Paso: 3: Set $G \in R^{(N + M) \times (N + M)}; G =$ 0;
forall j=1 to M+N
forall i=1 to M+N
$G [i, j] = d i s t_{h a v e r s i n e} (c o o r d (i), c o o r d (j))$
if $G [i, j] = = 0;$ then $G [i, j] = \infty;$ endif
if $G [i, j] > d m i n;$ then $G [i, j] = \infty;$ endif
if $G [i, j] \leq d m i n;$ then $G [i, j] = 1;$ endif
endforall
endforall
Paso: 4: $[d p, p r e d] = d i j k s t r a (G, N + M);$
Paso: 5: Set $p a t h = \emptyset$
forall $i = 1 : N + M$
$n o d e = i;$
$p a t h = p a t h \cup \{n o d e\}$ ;
while $p r e d (n o d e) < N + M + 1 & p r e d (n o d e) > 0$
$p r e d (n o d e);$
$p a t h = p a t h \cup \{p r e d (n o d e)\}$ ;
$t o t a l C o s t = t o t a l C o s t + ∣ d i s t_{h a v e r s i n e} (n o d e, p r e d (n o d e)) ∣$ ;
$n o d e = p r e d (n o d e);$
endwhile
endforall
Paso: 6: Return $m i n$ : $r o u t i n g - t r e e - p a t h$ ;

4. Analysis of Results

The models for solving the sizing and routing of wireless sensor networks required for different smart city applications are presented according to the stages outlined above. The simulation process was performed in Matlab R2020b, which was interfaced with the LPSolve optimizer (developed by MIT) on a computer with an E3-1535M v5 CPU, Intel Xeon 2.90 GHz, and 64 GB of RAM.

4.1. Wireless Sensor Network Sizing

The scenario included

N = 40

sensors located in an approximately L × L defined area of 300 m

^{2}

. A total of

M = 25

candidate sites were established for the placement of a DAP. The optimization model sought to minimize the cost per number of DAPs subject to the capacity constraint of

C = 20

, a coverage radius of

R = 60

m, and a percentage of

P = 100 %

Figure 2a represents the original scenario before solving the mixed-integer linear programming problem (MILP).

Figure 2b shows that the optimal result was reduced from

M = 25

M = 9

, which would be the sites where the DAPs would be actively placed.

Figure 3 indicates the variations in power consumption among the wireless technologies. It is remarkable to see that when opting for a single technology, such as a cellular network, energy consumption is higher than for technologies that have lower coverage but have a multi-hop option and lower energy consumption.

4.1.1. Routing Based on Graph Theory

After solving the sizing problem, a change in the scenario was generated, and we then had

N = 40

sensors and

M = 9

DAPs with which we proceeded to apply the routing model based on graph theory. For this stage, a connectivity matrix was generated among all resources (sensors and DAPs) based on the calculation of distances between two geographical points using the Haversine distance; then, the connectivity matrix G was generated based on the passing weight, which was the coverage radius of the DAPs:

R = 60

Therefore, to find the minimum cost of the tree, Dijkstra’s algorithm was used. The model presented two minimum-cost trees from two Dijkstra variations. Figure 4a shows the solution generated in the shortest time (

0.4219

s) by starting the routing from the DAPs to the sensors (down-link).

Figure 4b presents the routing from the sensors to the DAPs (up-link) in a longer time (

1.6094

s). This variation in time and computational performance is important when generating a planning model with a larger number of resources to explore.

4.1.2. Multi-Cast Routing

A variation of the routing presented in this work allowed us to make a minimum spanning tree (MST) to link the resources to be placed (sensors and DAPs). This offered the possibility of achieving an MST that generated resilience when interconnecting the resources. This solution is less expensive than a partial or total mesh topology in smart cities depending on the type of application. If it is necessary to ensure the real-time collection of information, this type of routing can contribute. Figure 5 presents a feasible mesh from the distance restriction represented by the coverage radius (

R = 60

m); it depends on this variable. The MST was determined to generate a multi-cast routing.

4.1.3. Multiple-Flow Routing

In general, this model presents a routing that considers the capacity of the links as a constraint. In addition, it calculates the number of data flows that can pass through each wireless link; in the case of finding a congested route, the model shows resilience and evaluates another route through which it can send the data. Figure 6a shows the MST achieved in the previous stage, which was acted upon by defining links with an origin and destination; the cost and link capacity were previously use to make a flow matrix with its source and destination, as well as a requirement in terms of the number of packets to be sent. Figure 6b presents the best route that was constructed by the algorithm, which connected the link from

D A P 9

D A P 2

In Figure 7, we can see that the most significant amount of flow per wireless link was from

D A P 2

due to the number of DAPs around it. It was solved as an MILP.

This model allowed us to dimension the amount of traffic that could circulate from the beginning to the end in order to optimize the resources and ensure the correct quality of service in the wireless links. Table 3 shows the results generated by LPSolve.

The capacity of each DAP has a direct impact on the search for optimal candidate sites and the problem graph because the selected DAPs may be different. Therefore, there is a direct impact on the total path cost when varying the capacity of a DAP. However, when the capacity of each DAP is low, the total path cost is higher and may remain somewhat higher in contrast to medium or higher capacities. Figure 8 also shows that there is a trend of linear growth as the the radius of coverage becomes more significant. Depending on the arrangement of the resulting networks, scenarios with higher total path costs can occur. Finally, Figure 8 shows that after 200 m of coverage, the total path cost remains constant.

Table 4 identifies the innovations of this research in contrast to those of other proposals that address the problem of the sizing and routing of wireless sensors. The present work focuses on scenarios such as the smart metering of electrical energy; in fact, it focuses on relaxing the complexity of the sizing and routing problem by independently and consecutively solving each stage. In this way, the present work was compared with other proposals to highlight the contributions regarding the problem addressed.

5. Conclusions

The model for the resolution of the problem of flow capacity achieved the optimal coordination of data routing in the network layer and allocated resources in the physical layer by fixing the costs in the capacities of the DAPs, thus providing a cross-layer solution.

The novel contribution of this model was the establishment of a multi-hop WSN that used cross-layer information to determine the routing of the network layers while involving decision aspects, such as wireless link capacity and traffic flow demands. The model did not use clustering methods to relax the NP-complete problem.

This paper focused on the sizing and routing of wireless sensor networks deployed for the provision of new IoT services and applications for smart cities by considering the locations of DAPs in a neighborhood area network.

Therefore, to achieve this objective, a problem was formulated in three stages (graph theory, multi-casting, and multiple flows) that were sequentially simulated, but had the same goal: to minimize the cost of the minimum number of DAPs and the minimum distance.

This paper presented an actual urban area that was geo-referenced with the latitude and longitude of each technological resource, and the performance of the optimization models was evaluated. Simulation results verified that the proposed solution could reduce the number of DAPs and generate random answers based on clustering methods. Additionally, a minimum-cost tree was initially created by considering the weight of the cost per distance for the backup wireless network. Finally, the binding capacity restriction was added.

Inter-DAP interference was not considered in this work, as it can be solved by assigning different channels to each DAP.

Author Contributions

E.I.: Conceptualization, Methodology, Validation, Writing—review and editing. J.I., A.O.: Conceptualization, Methodology, Software, Writing—original draft. J.I. and A.O.: Data curation, Formal analysis. E.I.: Supervision. E.I.: Writing—review and editing. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by Universidad Politécnica Salesiana and the Smart Grid Research Group (GIREI) under the project “Electric vehicle charging in buildings and its impact on the sizing and planning of electricity distribution networks”.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

This work was funded by the Smart Grid Research Group (GIREI) and Telecommunications Group (GITEL) of Universidad Politécnica Salesiana, as well as the Power Grids and Smart Cities (RECI) project of the Salesian Institutions of Higher Education (IUS).

Conflicts of Interest

The authors declare no conflict of interest.

References

Khalil, M.; Khalid, A.; Khan, F.U.; Shabbir, A. A review of routing protocol selection for wireless sensor networks in smart cities. In Proceedings of the 24th Asia-Pacific Conference on Communications, APCC, Ningbo, China, 12–14 November 2018; pp. 610–615. [Google Scholar] [CrossRef] [Green Version]
Afaneh, A.; Shahrour, I. Use of GIS for SunRise Smart City project, large scale demonstrator of the Smart City. SENSET 2017, 2017, 1–4. [Google Scholar] [CrossRef]
Jain, B.; Brar, G.; Malhotra, J.; Rani, S. A novel approach for smart cities in convergence to wireless sensor networks. Sustain. Cities Soc. 2017, 35, 440–448. [Google Scholar] [CrossRef]
S, S.N.; Mane, P.B. Swarm Intelligent WSN for Smart City. Proc. Int. Conf. Data Eng. Commun. Technol. 2017, 469, 603–611. [Google Scholar] [CrossRef]
Jawhar, I.; Mohamed, N.; Al-Jaroodi, J. Networking architectures and protocols for smart city systems. J. Internet Serv. Appl. 2018, 9. [Google Scholar] [CrossRef] [Green Version]
Masoud, M.Z.; Jaradat, Y.; Jannoud, I.; Al Sibahee, M.A. A hybrid clustering routing protocol based on machine learning and graph theory for energy conservation and hole detection in wireless sensor network. Int. J. Distrib. Sens. Netw. 2019, 15. [Google Scholar] [CrossRef] [Green Version]
Passos, D.; Rolim, G.; Ribeiro, I.; Moraes, I.; Albuquerque, C. Robust Advanced Metering Infrastructures and Networks for Smart Grid; Springer: Singapore, 2019; pp. 551–605. [Google Scholar] [CrossRef]
Hanif, S.; Khedr, A.M.; Aghbari, Z.A.; Agrawal, D.P. Opportunistically Exploiting Internet of Things for Wireless Sensor Network Routing in Smart Cities. J. Sens. Actuator Netw. 2018, 7, 46. [Google Scholar] [CrossRef] [Green Version]
Kumar, D.; Aseri, T.C.; Patel, R.B. EECDA: Energy efficient clustering and data aggregation protocol for heterogeneous wireless sensor networks. Int. J. Comput. Commun. Control 2011, 6, 113–124. [Google Scholar] [CrossRef] [Green Version]
Dabirmoghaddam, A.; Ghaderi, M.; Williamson, C. On the optimal randomized clustering in distributed sensor networks. Comput. Netw. 2014, 59, 17–32. [Google Scholar] [CrossRef]
Meenaakshi Sundhari, R.P.; Jaikumar, K. IoT assisted Hierarchical Computation Strategic Making (HCSM) and Dynamic Stochastic Optimization Technique (DSOT) for energy optimization in wireless sensor networks for smart city monitoring. Comput. Commun. 2020, 150, 226–234. [Google Scholar] [CrossRef]
Senthilkumar, R.; Tamilselvan, G.M.; Kanithan, S.; Arun Vignesh, N. Routing in WSNs powered by a hybrid energy storage system through a CEAR protocol based on cost welfare and route score metric. Int. J. Comput. Commun. Control 2019, 14, 233–252. [Google Scholar] [CrossRef]
Abujubbeh, M.; Al-Turjman, F.; Fahrioglu, M. Software-defined wireless sensor networks in smart grids: An overview. Sustain. Cities Soc. 2019, 51. [Google Scholar] [CrossRef]
Kumar, D.; Aseri, T.C.; Patel, R.B. A novel multihop energy efficient heterogeneous clustered scheme for wireless sensor networks. Tamkang J. Sci. Eng. 2011, 14, 359–368. [Google Scholar] [CrossRef]
Wang, W. Deployment and optimization of wireless network node deployment and optimization in smart cities. Comput. Commun. 2020. [Google Scholar] [CrossRef]
Hidalgo Lopez, R.; Moreno Novella, J.I. Routing Design in Wireless Sensor Networks and a Solution for Healthcare Environments. IEEE Lat. Am. Trans. 2011, 9, 408–414. [Google Scholar] [CrossRef]
Guidoni, D.L.; Souza, F.S.; Ueyama, J.; Villas, L.A. RouT: A routing protocol based on topologies for heterogeneous wireless sensor networks. IEEE Lat. Am. Trans. 2014, 12, 812–817. [Google Scholar] [CrossRef]
Inga-ortega, J.; Inga-ortega, E.; Gómez, C. Electrical Load Curve Reconstruction required for Demand Response using Compressed Sensing Techniques. In Proceedings of the IEEE PES Innovative Smart Grid Technologies Conference—Latin America (ISGT Latin America), Quito, Ecuador, 20–22 September 2017. [Google Scholar] [CrossRef]
Inga, E.; Céspedes, S.; Hincapié, R.; Cárdenas, A. Scalable Route Map for Advanced Metering Infrastructure Based on Optimal Routing of Wireless Heterogeneous Networks. IEEE Wirel. Commun. 2017, 24, 1–8. [Google Scholar] [CrossRef]
Inga, E.; Eléctrica, I.; Campaña, M.; Eléctrica, I.; Hincapié, R.; Céspedes, S. Optimal Placement of Data Aggregation Points for Smart Metering using Wireless Heterogeneous Networks. In Proceedings of the 2018 IEEE Colombian Conference on Communications and Computing (COLCOM), Medellin, Colombia, 16–18 May 2018; Volume 1. [Google Scholar]
Peralta, A.; Inga, E.; Hincapié, R. Optimal Scalability of FiWi Networks Based on Multistage Stochastic Programming and Policies. J. Opt. Commun. Netw. 2017, 9, 1172. [Google Scholar] [CrossRef]
Mekki, K.; Bajic, E.; Chaxel, F.; Meyer, F. Overview of cellular LPWAN technologies for IoT deployment: Sigfox, LoRaWAN, and NB-IoT. In Proceedings of the 2018 IEEE International Conference on Pervasive Computing and Communications Workshops (Percom Workshops), Athens, Greece, 19–23 March 2018; pp. 197–202. [Google Scholar]
Wang, G.; Zhao, Y.; Ying, Y.; Huang, J.; Winter, R.M. Data Aggregation Point Placement Problem in Neighborhood Area Networks of Smart Grid. Mob. Netw. Appl. 2018, 1572–8153. [Google Scholar] [CrossRef]
Hassan, A.; Zhao, Y.; Pu, L.; Wang, G.; Sun, H.; Winter, R.M. Evaluation of Clustering Algorithms for DAP Placement in Wireless Smart Meter Network. In Proceedings of the 2017 9th International Conference on Modelling, Identification and Control (ICMIC), Kunming, China, 10–12 July 2017; Volume 1, pp. 1085–1090. [Google Scholar]
Wang, G.; Zhao, Y.; Huang, J.; Winter, R.M. On the Data Aggregation Point Placement in Smart Meter Networks. In Proceedings of the 2017 26th International Conference on Computer Communication and Networks (ICCCN), Vancouver, BC, Canada, 31 July–3 August 2017. [Google Scholar]
B, G.W.; Zhao, Y.; Ying, Y.; Huang, J.; Winter, R.M. A Clustering Algorithm for the DAP Placement Problem in Smart Grid. Adv. Hybrid Inf. Process. 2018, 219, 349–359. [Google Scholar] [CrossRef]
Wang, G.; Zhao, Y.; Huang, J.; Duan, Q.; Li, J. A K-means-based Network Partition Algorithm for Controller Placement in Software Defined Network. In Proceedings of the 2016 IEEE International Conference on Communications (ICC), Kuala Lumpur, Malaysia, 22–27 May 2016. [Google Scholar]
Janani, E.S.V.; Univesity, A. Analytical techniques to characterize and optimize the performance of sensor network systems. In Proceedings of the IEEE- Fourth International Conference on Advanced Computing, ICoAC 2012 MIT, Chennai, India, 13–15 December 2012; pp. 1–5. [Google Scholar]
Wang, J.; Gao, Y.; Liu, W.; Sangaiah, A.K.; Kim, H.J. Energy efficient routing algorithm with mobile sink support for wireless sensor networks. Sensors 2019, 19, 1494. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Inga, E.; Hincapié, R.; Céspedes, S. Capacitated Multicommodity Flow Problem for Heterogeneous Smart Electricity Metering Communications Using Column Generation. Energies 2019, 13, 97. [Google Scholar] [CrossRef] [Green Version]
Winarno, E.; Hadikurniawati, W.; Rosso, R.N. Location based service for presence system using haversine method. In Proceedings of the 2017 International Conference on Innovative and Creative Information Technology (ICITech), Salatiga, Indonesia, 2–4 November 2017; pp. 1–4. [Google Scholar]
Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1959, 1, 269–271. [Google Scholar] [CrossRef] [Green Version]
Johnson, D.B. A note on Dijkstra’s shortest path algorithm. J. ACM (JACM) 1973, 20, 385–388. [Google Scholar] [CrossRef]

Figure 1. Geo-referenced sizing and routing of wireless sensor networks.

Figure 2. Minimization of the DAPs based on the sizing model.

Figure 3. Energy consumption of the wireless technology.

Figure 4. Optimal routing based on the Dijkstra algorithm.

Figure 5. Minimal spanning tree—wireless network backup.

Figure 6. Optimal routing of wireless link—capacity link constraint.

Figure 7. Routing with the capacity of the links—Table 3.

Figure 8. Coverage radius vs. total path cost.

Table 1. Summary of papers related to the sizing and geo-referenced routing of wireless sensor networks.

Scientific Paper	Problem				Constraints				Proposal
Author	Energy Efficiency	Data Collection	Scalability	DAPPlacement	Multi-Hop	Capacity	Coverage	Cost	Clustering Conglomerate	GIS	EnergyConsumption	Cross-Layer
Wang et al. [23]	✠	✠		✠	✠		✠	✠	✠	✠	✠
Hassan [24]	✠	✠		✠	✠		✠	✠	✠	✠	✠
Wang et al. [25]	✠	✠		✠	✠		✠	✠	✠	✠	✠
Guodong [26]	✠	✠		✠	✠		✠	✠	✠	✠	✠
Wang et al. [27]	✠	✠		✠	✠		✠	✠	✠	✠	✠
Passos [7]	✠	✠	✠	✠	✠	✠	✠	✠	✠		✠
Masoud [6]	✠	✠			✠	✠	✠	✠	✠		✠
Afaneh [2]	✠	✠	✠	✠	✠		✠	✠		✠	✠
Wang [29]	✠	✠			✠		✠	✠	✠		✠
Current Work		✠	✠	✠	✠	✠	✠	✠	✠	✠		✠

Table 2. Variables of Algorithms 1 and 2.

Variable	Definition
$C_{j}$	Capacity of DAP
R	Coverage radius of wireless technology/DAP
P	Wireless coverage percentage
$d i s t$	Distance matrix: from each sensor to each candidate site
$c o o r d S$	Coordinates of sites for DAPs
$c o o r d D$	Coordinates of sensors
M	Number of candidate sites
N	Number of sensors
$Z_{j}$	Set of links
$X_{j, i}$	Wireless link
$Y_{i}$	Sensor with coverage of a DAP
$d m i n$	Minimum distance of wireless technology
G	Connectivity matrix—graph
$d p$	Minimum distance between resources and a vertex
$p r e d$	Vertex preceding v in the shortest path
$p a t h$	Connectivity path
$t o t a l C o s t$	Tree extension in meters

Table 3. ZigBee simulation (250 Kbps)—flows were generated by using LPSolve.

Source Node	Destination Node	Requirement—# of Flows	Link Cost (Kbps)	Link Capacity—# of Flows	MILP—# of Flows
49	40	1	230	10	1
40	39	1	240	10	2
39	2	1	247	10	3
2	26	1	250	10	4
26	42	1	248	10	5

Table 4. Summary: the main contributions of similar research.

Goal	Proposal	A1 [26]	A2 [23]	A3 [25]	A4 [24]	A5 [27]
Sizing
`DAP location`	Candidate sites	Random	Random	Random	Random	Random
`Haversine distance`	✓	✓	✗	✓	✓	✗
`Euclidean distance`	✗	✗	✓	✗	✗	✗
`Optimization MILP`	✓	✗	✗	✗	✗	✗
`K-means clustering`	✗	✓	✓	✓	✓	✓
`Coverage`	✓	✓	✓	✓	✓	✓
`DAP capacity`	✓	✗	✗	✗	✗	✗
Routing
`Shortest path $G = (V, E)$`	Dijkstra $O (n^{2})$	Floy Warshall $O (\| V \|^{3})$	Floy Warshall $O (\| V \|^{3})$	Floy Warshall $O (\| V \|^{3})$	✗	✗
`Backup minimum spanning tree + multi-hops`	PRIM $O (E l o g (V))$	✗	✗	✗	✗	✗
`Shortest path $G = (V, E)$ + link capacity + Weight (bps)`	✓	✗	✗	✗	✗	✗

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Inga, E.; Inga, J.; Ortega, A. Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities. Sensors 2021, 21, 4692. https://doi.org/10.3390/s21144692

AMA Style

Inga E, Inga J, Ortega A. Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities. Sensors. 2021; 21(14):4692. https://doi.org/10.3390/s21144692

Chicago/Turabian Style

Inga, Esteban, Juan Inga, and Andres Ortega. 2021. "Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities" Sensors 21, no. 14: 4692. https://doi.org/10.3390/s21144692

APA Style

Inga, E., Inga, J., & Ortega, A. (2021). Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities. Sensors, 21(14), 4692. https://doi.org/10.3390/s21144692

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities

Abstract

1. Introduction

2. Related Work

3. Problem Formulation

3.1. Wireless Sensor Network Sizing

3.2. Wireless Sensor Network Routing

3.2.1. Routing Based on Graph Theory

3.2.2. Multicast Routing

3.2.3. Multiple Flow Routing

4. Analysis of Results

4.1. Wireless Sensor Network Sizing

4.1.1. Routing Based on Graph Theory

4.1.2. Multi-Cast Routing

4.1.3. Multiple-Flow Routing

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI