Developing Smart Grids Based on GPRS and ZigBee Technologies Using Queueing Modeling–Based Optimization Algorithm

Gustavo Batista de Castro Souza
,
Flávio Henrique Teles Vieira
,
Cláudio Ribeiro Lima
,
Getúlio Antero de Júnior Deus
,
Marcelo Stehling de Castro
,
Sérgio Granato de Araujo
,
Thiago Lara Vasques

ETRI Journal.
2016.
Mar,
38(1):
41-51

- Received : August 10, 2014
- Accepted : October 14, 2015
- Published : March 01, 2016

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

Smart metering systems have become widespread around the world. RF mesh communication systems have contributed to the creation of smarter and more reliable power systems. This paper presents an algorithm for positioning GPRS concentrators to attain delay constraints for a ZigBee-based mesh network. The proposed algorithm determines the number and placement of concentrators using integer linear programming and a queueing model for the given mesh network. The solutions given by the proposed algorithm are validated by verifying the communication network performance through simulations.
RF mesh system architecture (adapted from [1] ).
One of the greatest difficulties in designing an NAN metering network is to position collectors to optimize costs and improve the performance of any remote metering system. It can be verified by simulations or in practice that the position of a GPRS concentrator influences the performance of the communication network of a Smart Grid in terms of throughput and delay. The number and positions of GPRS concentrators must be determined for a Smart Grid implantation to achieve a desired delay value for the messages that come from start meters. This is important for monitoring and control purposes once the delay of the messages may become critical as the number of meters is increased. Besides, the number of GPRS concentrators that have to be installed will affect the implementation cost.
In this paper, we propose a new approach for choosing the placement of concentrators in a ZigBee mesh network of smart meters to minimize the average delay of messages in concentrators. We use the
k
-means clustering algorithm as one of a variety of tools to distribute the meters into subnetworks, queueing-theory modeling to determine the average delay network, and binary linear programming (BLP) to determine the ideal locations of concentrators. We also evaluate the efficiency of the proposed algorithm in enhancing the communication network performance through simulations with a network simulator.
Much research has been done for evaluating the performance of wireless networks for Smart Grids. In
[4]
–
[6]
, the effects of the number of hops and data arrival rate in mesh networks were addressed by using queueing theory to model the network. In these papers, the authors propose a model suitable for a generic mesh network. In the model, the MAC layer and routing system of the network are simplified to represent all kind of mesh networks. The same authors tested networks with different configurations and compared the results of simulations to those of their model. In
[6]
, the authors verified the impact of any wireless interference that could limit a transmission.
Regarding Smart Grid applications, we can find many works describing technologies and improvements to a power system. In
[7]
, different communication methods are described, and illustrations of how a Smart Grid can be served by such methods is given. The authors discuss about routing systems in a ZigBee architecture and about the importance of planning communication networks for Smart Grids.
Related to our work, we can still mention papers regarding facility location. Iyigun and Ben-Israel present an algorithm
[8]
for solving the multi-facility location problem. They used clustering techniques to group and cluster elements, serving all individuals by at least a single facility. This same work helped us to visualize our problem in terms of facility location and to realize the significance of the
k
-means clustering algorithm in grouping meters in a mesh network.
k
-means algorithm. This algorithm can be considered as a method for minimizing the sum of squared errors
[8]
. The
k
-means algorithm works by partitioning objects into
k
groups, minimizing some criteria within groups. In this paper, we applied
k
-means clustering to minimize the distance between each given meter and the center of a given cluster. The method is based on two procedures. The first is the assignment of objects into groups. An object is generally attributed to the group whose average Euclidean distance is closest to the center. The second procedure is the calculation of a new group based on designations established for a cluster (for example, cluster size, number of clusters, maximum number of elements, and so on)
[8]
. The procedure ends when individual movements between groups cease or the sum of squares no longer decreases. A limitation established for those clusters that feature in our work is that a cluster’s size is not permitted to exceed 300 m; that is, in accordance with the considered transmitter power. It can be shown that this value is acceptable for ZigBee mesh networks.
N
nodes and a gateway that acts as a concentrator for the mesh nodes. In the system model, a node whose hop-count distance to the gateway is equal to
x
is referred to as an
x
-hop node. We assume that the hop-count distribution for each node is given (that is, the ratio of the
x
-hop nodes in the network is given). To make the model more general, we do not assume any specific mechanism for medium access control (MAC), setting a generic MAC scheme with a probability of
p
(
x
) that a node will access a channel.
Traffic flows in wireless mesh networks (WMNs) are considered among mesh clients and GPRS concentrators. Thus, we assume that the destinations of all traffic loads are to the GPRS network.
Figure 2
presents such a WMN under our assumptions, where solid arrows indicate traffic flows generated by mesh client nodes and where dashed arrows represent the direction of possible flows within the WMN. The first index number at each node denotes its hop-count.
As shown in
Fig. 2
, the traffic loads of (
s
+ 1) hop nodes (0 ≤
s
<
S
) affect the packet arrival rates of
s
hop nodes, because the
s
hop nodes will need to accumulate the packages of the more distant nodes from the gateway.
Traffic flow in mesh network [6] .
The wireless channel capacity is
W
bits per second. That is, for each node, the transmission rate is
W
bits per second. This rate is constant and independent of the number of network nodes. The packets are sent over multiple hops to or from the gateway. Without loss of generality, we consider one-way traffic; that is, traffic flows that only come out of mesh network nodes to the gateway (also referred to as upstream traffic). We consider a saturated condition; that is, each node is always backlogged (there is always queueing in the buffer), and always presents data to transmit to the gateway
[5]
.
The routing scheme used in the model in
Fig. 2
is based on shortest path algorithms, seeking the lowest number of hops. Since the WMNs are generally considered robust and highly connected, it is assumed that each mesh node can always find at least one path to the gateway. We further assume that each
x
-hop node should retransmit packets received by the (
x
+ 1)-hop node, and the (
x
− 1)-hop nodes will supply a link to packets forwarded to them. When an
x
-hop node has more than one (
x
− 1)-hop node neighbor, it can randomly select one of its neighbors to relay their packets
[5]
.
The parameter
h
(
x
) denotes the ratio of the number of
x
-hop nodes in the network. The
h
(
x
) value is affected by many factors, including the routing algorithm, the spatial distribution of the meters (nodes), and the transmission range. This parameter can be analytically computed or obtained via simulations. Once the area is limited and the gateway can restrict the maximum number of hops within the network, nodes can be served; we note here that
h
(
x
) approaches zero when
x
is very large. We denote the maximum possible distance to a hop from the network gateway by
H
. Thus, there will be no traffic relayed to the gateway through
H
-hop nodes
[5]
.
Given
h
(
x
), we can obtain the expected number of
x
-hop nodes; this is represented by
N
(
x
) as follows, where
N
is the number of nodes
[5]
:
x
-hop node is assumed to relay packets from (
x
+ 1)-hop nodes, the expected number of (
x
+ 1)-hop nodes to which each
x
-hop node has to retransmit their packets is designated by
N
_{r}
(
x
), which is given by the following equation
[5]
:
μ
(
x
) is the service rate to an
x
-hop node, while
λ
(
x
) is the relay rate for an
x
-hop node. Equation (3) shows the relation between
μ
(
x
) and
λ
(
x
)
[5]
.
ρ
(
x
) represents the amount of traffic in an
x
-hop node and is given by
[5]
:
x
-hop node output, it is possible to determine the end-to-end traffic throughput. First, it is necessary to determine the blocking probability for messages/packets at each hop. The throughput of an
x
-hop node, given by
T
(
x
), is defined as the average number of packets (per unit of time) successfully received by the receiver; that is, the gateway. More specifically, the
x
-hop node throughput is defined as the departure rate of packets for those
x
-hop nodes that are not blocked by any intermediate nodes that lie between the given
x
-hop node and the gateway. The blocking probability for the
x
-hop node is given by
P
_{b}
(
x
). From the M/M/1/K Queueing Model (it is assumed that the system is composed of one server and a buffer of size
K
), we have the following
[5]
:
ρ
(
x
) is given by (4) and
K
is the buffer to the
x
-hop node. Therefore, the non-blocking packet probability for the
x
-hop node is [1−
P
_{b}
(
x
)]. For any path, the end-to-end non-blocking probability is equal to the product of non-blocking probabilities at all intermediate nodes. Therefore, the throughput
T
(
x
) to an
x
-hop node is equal to the product between output rate and the effective non-blocking end-to-end probability; that is, we have the following
[5]
:
T
_{agg}
the efficiency of the system; that is, the throughput aggregate value per node. The parameter
T
_{ave}
represents the average efficiency per node. Since the number of
x
-hop nodes is
N
(
x
), we have
[5]
x
-hop node. We denote as
L
_{r}
(
x
) the queue size in a steady state for an
x
-hop node. According to the M/M/1/K queue formulas, we have
[5]
D
(
x
) is the actual delay of a packet generated from an
x
-hop node. To obtain
D
(
x
), we first calculate the waiting time at each hop. The waiting time of a packet from one intermediate node is equal to the time between when the packet is placed in the queue of this node and when the node starts sending the first bit of the packet to the next node (or gateway). Therefore, the total time for a packet passing through an intermediate node is equal to the waiting time in the queue plus the transmission time. We denote as
W
_{r}
(
x
) the waiting time for packets in the
x
-hop node. According to Little’s formula, we have
[5]
D
(
x
) value is obtained by adding the time spent waiting in intermediate nodes and the transmission time to cross the
x
-hop nodes. We can calculate the
D
(
x
) value, where
t
_{c}
represents the transmission time
[5]
, by the following equation:
D
_{ave}
, which is obtained by calculating the average delay of packets that are successfully received by the gateway. Therefore, within a unit time,
T
(
x
) represents the total number of packets that are generated by an
x
-hop node and successfully received by the gateway. The total number of packets generated by all
x
-hop nodes and successfully received by the gateway is equal to
N
(
x
)·
T
(
x
). Thus, the total delay of packets generated and successfully received by all
x
-hop nodes is
N
(
x
)·
T
(
x
)·
D
(
x
). Consequently, we have
[5]
m
as the number of potential facilities;
n
the number of customers/users;
a_{j}
the demand of customer/user
j
;
b_{i}
the capacity of facility
i
;
f_{i}
the fixed cost of using facility
i
; and
c_{ij}
the cost to assist customer/user
j
by facility
i
. All coefficients are assumed to be non-negative integers. We define the following decision variables to the optimization problem of
[9]
:
The main cost used in the optimization algorithm is the number of hops between each meter and GPRS data concentrator (facility). To determine the number of hops, shortest path algorithms are used in accordance with the routing protocol of ZigBee mesh networks.
Algorithm fluxogram.
In Smart Grids, communication networks are the backbone of the system
[7]
. Therefore, the resources required for communication between devices should be well sized, because they represent much of the budget in Smart Grids. The Smart Grid scenarios considered in this work are based on ZigBee mesh network nodes that communicate to a concentrator, which in turn sends the messages via GPRS to the power utility. A real Smart Grid will be deployed in our Project of Research and Development with a Brazilian utility company, and involves a ZigBee network operating at a frequency of 2.4 GHz with a transmission rate of approximately 115 kbps. As commonly used, we assume that meters send data every 15 min to a GPRS concentrator
[1]
,
[11]
.
The main purpose of the simulations in this work is to evaluate network performance considering different positions for the GPRS concentrators. Using simulations, we can determine the best position for a concentrator among the possible alternatives for the considered scenarios in Figs. 4 and 5. The considered scenarios represent real networks with meters connected to two transformers, containing one or more GPRS concentrator modules. Scenario 1 (
Fig. 4
) presents 67 meters and scenario 2 (
Fig. 5
), 72 meters.
Positions of meters (case study 1).
Positions of meters (case study 2).
Routes to best concentrator point (C5): case study 1.
To verify the network traffic performance with the concentrator in the C5 position, we simulate the communication network in an event-driven simulator. We set the simulation parameters according to those of the scenario of case study 1. For this scenario, we analyze the delay, the queue size in the concentrator, and the traffic load of the system in the positions C1, C2, C3, C4, and C5.
Figure 7
shows the average delay (in seconds) of packet transmission in the concentrator. From
Fig. 7
, we can observe that the average delay in the network is lowest when the concentrator is in position C5. The simulations confirm that we can obtain the best concentrator position choice in terms of average delay with the proposed algorithm.
Average delay for five concentrator positions where meters send data every 15 min: case study 1.
Positioning two concentrators: case study 1.
Average network delay using two concentrators: case study 1.
Routes to best concentrator point (C1): case study 2.
The parameters of the simulations are set according to the scenario considered in case study 2, repeating the analysis of case study 1 for positions C1, C2, C3, C4, C5, and C6.
Figure 11
shows the average delay (in seconds) of packet transmission in the concentrator.
Figure 11
reveals that a lower average delay is obtained by using the proposed approach.
Average delay for six concentrator positions where meters send data every 15 min: case study 2.
Positioning three concentrators: case study 2.
Solutions to case study 2 with limited delay of 200 ms, 50 ms, and 25 ms.
Comparing average delays for case study 1.
Comparing average delays for case study 2.
Corresponding Author gustavo2x4@gmail.com
Gustavo Batista de Castro Souza received his BS degree in computer engineering from the Federal University of Goiás (UFG), Brazil, in 2011 and his MS degree in electrical and computer engineering from UFG in 2014. He has served both as a researcher and a product development engineer for smart grids. Currently, he is an information technology analyst at Instituto Federal de Educação, Ciência e Tecnologia de Goiás, Brazil. His research interests include wireless telecommunications, computer networks, smart grids, and computer systems.
flavio@eee.ufg.br
Flávio Henrique Teles Vieira received his BS degree in electrical engineering from the Federal University of Goiás (UFG), Brazil, in 2000 and his MS degree in electrical and computer engineering from UFG in 2002. He received his PhD degree in electrical engineering at the State University of Campinas, Brazil, in 2006. He is currently working as a professor with the Electrical, Mechanical and Computer School of Engineering (EMC), UFG, where he is also a research coordinator for EMC-UFG. His research interests include network traffic modeling and control; communication networks; and computational intelligence and optimization algorithms applied to communication and power systems.
crlima100@gmail.com
Cláudio Ribeiro Lima served as vice-chair, author, and member of the Writing Group of the IEEE P2030 Smart Grid Standards, and as a member of the NIST-SGIP Smart Grid Architecture Council. He is currently involved in smart grid energy, ICT energy strategy, next-generation smart grids, micro-grids, DG architectures, and advanced smart grid technologies. Prior to this, he headed several teams and strategic initiatives for Sprint-Nextel at the Sprint Advanced Technologies/CTO Organization in Silicon Valley, including Sprint's Next-Generation Networks, Emerging Services, and Digital Innovation/Venture-R&D, where he was responsible for new technologies and business opportunities development. Between 2009 and 2012, he was the Global CTO of Smart Grid of Huawei Technologies, where he was responsible for Huawei Strategic initiatives worldwide, particularly with the State Grid Corporation of China. He has more than 30 years of experience leading advanced energy solutions, ICT innovation, system architectures, and emerging technologies. He holds a PhD degree in electronic engineering, which he received from the University of Kent, Canterbury, England, in 1995; in addition, he received his MS degree in electronic engineering from Universidade Estadual de Campinas, Brazil, in 1990. He has completed a venture capital executive program at Haas Business School and holds an executive MBA from the Dom Cabral Foundation.
getulio@eee.ufg.br)
Getúlio Antero de Deus Júnior received his BS degree in electrical engineering from the Federal University of Goiás (UFG), Brazil, in 1995. He received his MS and PhD degrees from the State University of Campinas, Brazil, in 1997 and 2002, respectively. From January 1998 to February 1998, he served as a visiting professor at the Polytechnic University of Valencia, Spain. He is now a tenured professor of electrical engineering (and university research professor) at UFG. His research interests include intellectual property, education in engineering, information theory, digital television, renewable energy, wireless communications, and telecommunications.
mcastro@eee.ufg.br
Marcelo Stehling de Castro received his BS degree in electrical engineering from the Universidade Federal de Juiz de Fora, Brazil, in 1993. In 1995, he went on to receive his MS degree in electrical engineering from the Universidade Estadual de Campinas, Brazil. Currently, he is working towards his PhD degree in electrical engineering at the Universidade de Brasília, Brazil. Since 1996, he has been a professor with the School of Electrical and Computer Engineering, Universidade Federal do Goias, Brazil. His areas of expertise include network engineering, optical communications, and smart grids. His research interests include communication networks, process management, and engineering education.
granato@eee.ufg.br
Sergio Granato de Araujo received his BS degree in electronic engineering from the Federal University of Rio de Janeiro (UFRJ), Brazil, in 1988 and his MS and PhD degrees in electrical engineering from the UFRJ in 1993 and 2004, respectively. He is currently working as an associate professor with the Electrical, Mechanical and Computer School of Engineering, Universidade Federal de Goiás, Brazil. His research interests include telecontrol, network protocols, smart grids, business intelligence, computational intelligence, and big data.
tlvasques@gmail.com
Thiago Lara Vasques received his associate degree in network computers from Salgado de Oliveira University, Goiânia, Brazil, in 2007 and his MS degree in electrical and computer engineering from Universidade Federal de Goiás, Brazil, in 2010. He is currently pursuing his PhD degree in sustainable energy systems from MIT Portugal program at the University of Coimbra, Portugal. His research interests include smart grids, power systems, renewable energy, and communication networks.

I. Introduction

The main purpose of a smart metering system based on radio frequency (RF) mesh is to allow utilities to provide automatic data readings at regular time intervals and offer programs, such as demand response, for the control of critical loads. Such systems require reliable bidirectional communication between the measurement points and the utility final host (head-end system (HES)). Currently, more than 10 million measurement points worldwide are managed using RF Mesh technology
[1]
.
Most solutions are proprietary, corresponding to an important part of the Smart Grid Network architectures. These Smart Grid solutions are intended to follow the IEEE 2030 Smart Grid Technical Standard
[2]
. This standard, launched in September 2011 by the IEEE Standards Association, defines Smart Grid architectures, concepts, elements, connections, and interoperability. Regarding mesh communication–based Smart Grids, the IEEE 802.15 Smart Utility Networks Task Group 4g is developing a new specific standard based on the IEEE Technical Standard 802.15.4g (802.15.4 evolution) to determine both current and future requirements as well as the functionality and interoperability of mesh networks with neighborhood area network (NAN) topology
[3]
.
An example of a mesh network architecture for Smart Grids is given in
[1]
. In such an architecture, meters located at endpoints transmit and receive data at a speed of 9.6 kbit/s; collector nodes (concentrators) are able to transmit and receive at speeds of up to twice that of meters (19.2 kbit/s). Concentrators are often strategically placed at the top of light poles, presenting high-speed line-of-sight communication paths that extend several meters. Collectors are installed throughout an area covered by a utility, covering the full range of meters employed. A commonly used protocol — ZigBee Mesh IEEE 802.15.4 communication protocol — in NAN network topologies uses smart meters in access communication and in the general packet radio service (GPRS) of concentrators directly connected with the HES of the utility. This GPRS connection is considered as a backhaul network. The use of GPRS concentrators allows an extension of the reach of messages of a ZigBee network to the power utility.
By definition, smart meters, a communication network, and an HES form part of the basic modules that define an advanced metering infrastructure technology, predominant in Smart Grids pertaining to remote metering.
Figure 1
presents such an architecture.
PPT Slide

Lager Image

II. Clustering Algorithm for Grouping Meters

Basically, the goal of clustering techniques is to group individuals in a population, aiming to discover a structure in the data. The results of a cluster analysis can identify a data structure representation, which can then be used to generate a hypothesis for each given group
[8]
.
Among the existing clustering algorithms, one of the simplest and most used is that of the
III. Throughput and Delay Analysis by Queueing Theory

In this paper, we consider a static mesh network composed of
PPT Slide

Lager Image

(1) N( x )= N×h( x ).

Since each
(2) N r (x)={ N(x+1) N(x) = h(x+1) h(x) x=1,2,…,H−1, 0 x=H.

To analyze the queueing behavior, we must know the packet arrival rates planned for the queues. The parameter
(3) λ(x)={ N r (x)⋅μ(x+1) x=1,2,…,H−1, 0 x=H.

Finally, the parameter
(4) ρ(x)= λ(x) μ(x) ={ N r (x)⋅μ(x+1) μ(x) x =1,2,…,H−1, 0 x=H.

- 1. Throughput Analysis

After obtaining the input parameters and each
(5) P b (x)={ [1−ρ(x)]⋅ρ (x) K 1−ρ (x) K+1 ρ(x)≠1, 1 K+1 ρ(x)=1,

where
(6) T(x)={ μ(1) x=1, μ(x)⋅ ∏ i=1 i=x−1 [1− P b (i)] x=2,…,H.

We denote as
(7) T agg = ∑ x=1 x=H [N(x)⋅T(x)],

(8) T ave = T agg N .

- 2. Delay Analysis

To obtain the end-to-end delay, we investigate the expected number of packets queued at an
(9) L r (x)={ ρ(x) 1−ρ(x) − ρ(x)[ Kρ (x) K +1 ] 1−ρ (x) K+1 ρ(x)≠1, K(K−1) 2(K+1) ρ(x)=1.

The end-to-end delay experienced by a packet is defined as the time between when the first bit of a packet is sent by the source and when the packet is completely received by the destination, or the gateway. We assume that the propagation delay is negligible. Thus, the end-to-end packet delay is equal to the sum of the transmission times and delays in the queues for all intermediate nodes. The parameter
(10) W r (x)= 1 μ(x) + L r (x) λ(x)[1− P b (x)] x=1,2,…,H−1.

The
(11) D(x)={ t c x=1, x⋅ t c + ∑ i=1 i=x−1 W r (i) x=2,3,…,H.

The end-to-end average delay is represented by
(12) D ave = ∑ x=1 x=H [N(x)⋅T(x)⋅D(x)] T agg .

IV. Positioning of GPRS Concentrators Using Binary Programming

In this paper, the localization of the concentrators is determined through BLP. The BLP algorithm decides which of the possible points as highlighted by clustering will be chosen to install a GPRS concentrator. To mathematically formulate the model, some notation must be introduced. We consider
(13) y i ={ 1 if facility i being used, 0 otherwise,

(14) x ij ={ 1 if facility i serves the client/user j, 0 otherwise.

The problem can be solved by the following binary programming algorithm
[9]
:
(15) min ∑ i=1 m ∑ j=1 n c ij x ij + ∑ i=1 m f i y i

s.t.
(16) ∑ j=1 n a j x ij ≤ b j ∀i,

(17) ∑ j=1 m x ij =1 ∀j,

(18) ∑ i=1;∀j n x ij − y i ≤0 ∀i,j,

(19) x ij ∈{ 0,1 } ∀i,j,

(20) y i ∈{ 0,1 } ∀i.

The objective function seeks to minimize the implementation cost of the facility (GPRS concentrator) so that all customers/users are attended to. The set of constraints in (16) ensures that the demand served to the users does not exceed the established capacity. Constraint (17) ensures that each customer/user is served by only a single facility. Constraint (18) determines that only those facilities that are open may be assigned to customers/users. Constraints (19) and (20) ensure that our problem will have only binary integer variables. BLP was used in this work to determine the point in the network at which a concentrator will be installed to maximize performance while minimizing costs (in this case, the number of hops). The number of hops was chosen as a criterion because it directly affects the delay in the system as well as the signal propagation to the concentrator. The considerations about the optimization model are as follows:
- cij= number of hops given by packets from meterjto facilityi
- fi= installation cost of facilityi
- aj= size of sent packets in bytes (200 bytes)
- bj= facility capacity in bytes (512 kbytes)

V. Proposed Methodology: GPRS Positioning Using Queueing Modeling–Based Facility Location Algorithm

In this section, we present the proposed approach for GPRS positioning using both a queueing model and a facility location algorithm. We can describe the proposed methodology as follows. First, we obtain the localization of each meter. The georeferencing of the meters allows us to group them into clusters and to calculate routes to possible locations for data concentrators. Initially, there is only one concentrator. Thus, there is only one cluster where one concentrator is responsible for the traffic flow. A clustering algorithm decides the positioning of the center of a single cluster of meters. To reduce the number of possible concentrator points, we select as candidates those poles that are in a radius of 50 m from where the center was established by the clustering algorithm. Therefore, all poles of the power grid should be georeferenced.
For all potential concentrator locations, we calculate routes from each meter to these location points. At this stage, we calculate the shortest paths by using a breadth-first search (BFS) algorithm
[10]
, which minimizes the number of hops between a meter and its final destination; that is, a potential concentrator location. The BFS algorithm reproduces the routing done by the ZigBee technology.
We assume in the proposed concentrator positioning algorithm that a traditional ZigBee routing algorithm is carried out without link breakage. That is, all ZigBee nodes can communicate with each other in a determined range given by the transmission power of the ZigBee technology. Traditional ad hoc routing protocols, such as the ad hoc on-demand distance vector (AODV), aim to find the shortest path from a source node to a destination node
[3]
. The AODV routing protocol is often used in the IEEE standard 802.15.4 ZigBee protocol stack. In other words, in the proposed concentrator positioning algorithm, the ZigBee nodes that will communicate are those that provide the shortest path from source to destination. This approach results in a concentrator position that provides the lowest message delay in a ZigBee simulator that uses the AODV algorithm.
In the positioning algorithm, we assume that communication between ZigBee nodes occurs for links that are below 100 m in length. BLP is used after finding the routes to choose the best concentrator locations. The network performance is optimized by choosing concentrator locations that minimize the cost of both installing concentrators and the number of hops between meters and GPRS concentrators.
After choosing the points of data concentration, we estimate the average delay of a network by using the queueing theory model presented in Section III. At this point, a maximum average delay can be set to be attained; for example, 200 ms. If the average delay of the system is attained, then the algorithm is finished, giving the position of the concentrators. However, if the average delay exceeds the imposed limit, then the algorithm adds 1 to the number of concentrators and returns to the point of resizing the clusters by the clustering algorithm. Concentrators will be added to the system until the threshold condition (for example, 200 ms) for the average delay is reached.
Figure 3
shows the flowchart representing the algorithm.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

VI. Simulation and Results

- 1. Smart Metering with Delay Bound Equal to 200 ms: Case Study 1

By requiring a maximum packet delay of 200 ms in the network of case study 1 (
Fig. 4
), the proposed algorithm gives the point C5 as the solution. In this case, only one concentrator was required for the delay constraint to be attained.
Figure 6
presents the chosen point in the network, as well as the routes of each meter to the GPRS concentrator.
PPT Slide

Lager Image

PPT Slide

Lager Image

- 2. Smart Metering with Delay Bound Equal to 50 ms: Case Study 1

There has to be a certain number of GPRS concentrators installed in the Smart Grid so that the system does not overload. The positions of these concentrators in this problem are not only limited to finding the best route, but it is necessary to evaluate the groups of meters that communicate with each concentrator.
The proposed algorithm is used to determine the position of the concentrators when the delay is limited to 50 ms. To attain such a condition, according to our algorithm, it is necessary to install two concentrators, working independently. Independent networks are created and packets are transmitted to two points of concentration data.
Figure 8
shows the two groups (red and blue points) of meters chosen by using the proposed algorithm, requiring a maximum delay of 50 ms (case study 1).
By using the proposed algorithm, two concentrators for the simulation were positioned. Positions C1 and C5 were chosen, reproducing the solution shown in
Fig. 8
. To validate the solution offered by the proposed algorithm, two scenarios were simulated with two concentrators, one being the solution presented by the algorithm and another with two other concentrators.
Figure 9
shows that the average delay of the network obtained by using two concentrators in positions C1 and C5 is lower than with two concentrators in the C2 and C4 positions.
PPT Slide

Lager Image

PPT Slide

Lager Image

- 3. Smart Metering with Delay Limited to 200 ms: Case Study 2

According to the proposed optimization approach, a delay constraint of 200 ms in case study 2 (
Fig. 5
) is attained by choosing point C1 as the concentrator position.
Figure 10
presents the chosen point in the network, as well as the routes of each meter to the GPRS concentrator.
PPT Slide

Lager Image

PPT Slide

Lager Image

- 4. Smart Metering with Delay Limited to 25 ms: Case Study 2

By limiting the average delay to 25 ms in case study 2, the proposed algorithm gave positions C1, C3, and C6 as a solution.
Figure 12
shows the groups of meters indicated by the proposed algorithm so that the average delay is attended in case study 2.
The algorithm determines that is necessary to install concentrators at positions C1, C3, and C6 to attain a maximum delay of 25 ms, as shown in
Fig. 12
.
Figure 13
compares the results of average delay in situations where the maximum delay is limited to 200 ms, 50 ms, and 25 ms. For these conditions to be attained, installations of 1, 2, and 3 concentrators were evaluated, respectively. The delay values in
Fig. 13
are obtained through simulations and are close to those calculated by the queueing model–based algorithm, as we will show in the next section.
PPT Slide

Lager Image

PPT Slide

Lager Image

- 5. Delay Analysis for Case Studies 1 and 2

The previous sections showed that the average delay could be reduced with the installation of new concentrators. With the creation of subnetworks, where they are connected to different concentrators, smaller values of packet transmission delay can be obtained. Network traffic performance is enhanced when new concentrators are installed.
Figures 14
and
15
show the reduction in the average delay for different numbers of concentrators for case studies 1 and 2, respectively. It can be observed that the average delay values obtained via simulations and those given by equation (12) are close for both case studies.
PPT Slide

Lager Image

PPT Slide

Lager Image

VII. Conclusion

This paper presented a methodology for optimal positioning of GPRS concentrators in mesh networks, attaining the average delay in the concentrators of the network. Using queueing theory and linear programming, we proposed an optimization method that provides reliable solutions according to the simulations and, especially, can be applied to real environments.
Two scenarios were simulated and the proposed methodology is used to find the number and positions of GPRS concentrators in these scenarios. The results of the proposed queueing model approach were compared to those obtained by computer simulations. In both scenarios, the proposed positioning approach gave the same locations for concentrators as those indicated by the simulations.
The presented methodology of concentrator positioning can be applied to different scenarios, with different configurations and quantities of nodes. Finally, the proposed approach can be used as an optimization tool for mesh-based Smart Grids regardless of its configuration or size, providing a reliable way of implementing Smart Energy Grids.
BIO

Lichtensteiger B.
“RF Mesh Systems for Smart Metering: System Architecture and Performance,”
Smart Grid Commun.
Gaithersburg, MD, USA
Oct. 4–6, 2010
379 -
384

2011
IEEE 2030, Guide for Smart Grid Interoperability of Energy Technol. and Inform. Technol. Operation with the Electric Power Syst. (EPS), and End-Use Appl. and Loads
Piscataway, NJ, USA

2011
IEEE 802.15 WPAN, Task Group 4g (TG4g) Smart Utility Networks
Piscataway, NJ, USA

Bisnik N.
,
Abouzeid A.
“Delay and Throughput in Random Access Wireless Mesh Networks,”
IEEE Int. Conf. Commun.
Istanbul, Turkey
June 11–15, 2006
403 -
408

Liu T.
,
Liao W.
2008
“Location-Dependent Throughput and Delay in Wireless Mesh Networks,”
IEEE Trans. Veh. Technol.
57
(2)
1188 -
1198
** DOI : 10.1109/TVT.2007.905389**

Muller C.
“Performance Analysis of Radio Propagation Models for Smart Grid Applications,”
Smart Grid Commun.
Brussels, Belgium
Oct. 17–20, 2011
96 -
101

Liotta A.
2012
“A Survey on Networks for Smart-Metering Systems,”
Int. J. Pervasive Comput. Commun.
8
(1)
23 -
52
** DOI : 10.1108/17427371211221072**

Iyigun C.
,
Ben-Israel A.
2012
“The Multi-facility Location Problem: A Probabilistic Decomposition Method,”
2000 Math. Subject Classification
1
(1)
1 -
33

Holmberg K.
,
Ronnqvist M.
,
Yuan D.
1999
“An Exact Algorithm for the Capacitated Facility Location Problems with Single Sourcing,”
European J. Operational Res.
113
(3)
544 -
559
** DOI : 10.1016/S0377-2217(98)00008-3**

Robinson J.
“Adding Capacity Points to a Wireless Mesh Network Using Local Search,”
IEEE Conf. Comput. Commun.
Phoenix, AZ, USA
Apr. 13–18, 2008
74 -
80

Yu R.
2011
“Cognitive Radio Based Hierarchical Communications Infrastructure for Smart Grid,”
IEEE Netw.
25
(5)
6 -
14

Citing 'Developing Smart Grids Based on GPRS and ZigBee Technologies Using Queueing Modeling–Based Optimization Algorithm
'

@article{ HJTODO_2016_v38n1_41}
,title={Developing Smart Grids Based on GPRS and ZigBee Technologies Using Queueing Modeling–Based Optimization Algorithm}
,volume={1}
, url={http://dx.doi.org/10.4218/etrij.16.0114.0971}, DOI={10.4218/etrij.16.0114.0971}
, number= {1}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Souza, Gustavo Batista de Castro
and
Vieira, Flávio Henrique Teles
and
Lima, Cláudio Ribeiro
and
Deus, Getúlio Antero de Júnior
and
Castro, Marcelo Stehling de
and
Araujo, Sérgio Granato de
and
Vasques, Thiago Lara}
, year={2016}
, month={Mar}