=Paper=
{{Paper
|id=Vol-1950/paper2
|storemode=property
|title=Optimal Placement of Universal Data Aggregation Points for Smart Electric Metering based on Hybrid Wireless
|pdfUrl=https://ceur-ws.org/Vol-1950/paper2.pdf
|volume=Vol-1950
|authors=Miguel Campaña,Esteban Inga,Roberto Hincapié
|dblpUrl=https://dblp.org/rec/conf/ssn/CampanaH17
}}
==Optimal Placement of Universal Data Aggregation Points for Smart Electric Metering based on Hybrid Wireless==
https://ceur-ws.org/Vol-1950/paper2.pdf
Optimal Placement of Universal Data Aggregation Points
for Smart Electric Metering based on Hybrid Wireless
Miguel Campaña Esteban Inga Roberto Hincapié
Ingeniería Eléctrica Ingeniería Eléctrica Ingeniería en Telecomunicaciones
Quito - Ecuador, Quito - Ecuador, Medellín - Colombia
mcampana@ups.edu.ec einga@ups.edu.ec roberto.hincapie@upb.edu.co
árboles, de tal manera que, ayude a mejorar la veloci-
dad de transmisión [IH16] introduciendo de esta man-
Abstract era el concepto de [GIKK11], que es una operación
fundamental en redes inalámbricas.
The Smart Electric Metering (SEM), seeks to Para la construcción de los conglomerados nos
supply quality services without neglecting the basaremos en el algoritmo de PRIM. Otros trabajos
reliability of the system. Therefore, a quality han presentado métodos para resolver este tipo de
service must be closely linked to the wireless problemas basados en una previa clusterización ar-
communication technologies, to technify the ticulados con árboles de mínima expansión según se
SEM, not only the read, but also cuts, recon- presenta en [ICHA17]. Posteriormente, para el en-
nections, and another additional services that rutamiento, se utiliza el algoritmo de Dijkstra.
the infrastructure of intelligent measurement
Para validar nuestro modelo se ejecuta varias simu-
provides through wireless technologies, such
laciones basándose en los parámetros de medición in-
as Cellular or WiFi. This article proposes an
teligente [IIO+ 17].
quasi-optimal planning and deployment model
En adelante este artículo se organiza dela siguiente
of smart meter (SM) for SEM in order to guar-
manera. En la sección II se introduce los requisi-
antee reliable wireless links communication at
tos fundamentales de redes híbridas para medición in-
the lowest implementation cost. The proposed
teligente de energía eléctrica. En la sección III se
algorithm gives global solutions within a finite
plantea la formulación del problema. En la sección
scenario, making it a scalable model in time
IV se realiza el despliegue cuasi-óptimo de MIs. Final-
capable of managing the use of available links.
mente, en la sección V concluimos nuestro artículo.
Keywords: smart electric metering, hybrid wireless
networks, universal data aggregation point, optimiza- 2 Redes Inalámbricas Híbridas para
tion, smart grid
Medición Inteligente
1 Introducción Para el despliegue de redes inalámbricas se debe con-
siderar aspectos como: enrutamiento fiable, ubicación
La en la actualidad, se busca implementar nuevos con-
segura y agregación segura de datos. Las redes in-
ceptos de redes eléctricas inteligentes, aplicables al sis-
alámbricas están constituidas a partir de dos elementos
tema eléctrico tradicional. El presente trabajo plantea
básicos: muchos MIs y uno o varios puntos de agre-
resolver el problema combinatorio que en ciertos tra-
gación de datos (PADs) [NDL14] y forman una red
bajos se han definido como NP-Complete [IOPSH+ 16];
dentro de una área de cobertura [IOPSH+ 16]. Los MIs
de esta manera, presentamos una opción heurística
capturan información de parámetros eléctricos, tales
para lograr un despliegue cuasi-óptimo de medidores
como: potencia reactiva y consumo para proyectar la
inteligentes (MI). La información obtenida de cada MI
respuesta a la demanda y, transmiten los datos hacia
se transmitirá mediante saltos, en caso de ser nece-
los PADs para que ellos se encarguen de retransmitir
sario, con una topología de enrutamiento basada en
la información hacia las estaciones base (EB) más cer-
Copyright © 2017 by the paper’s authors. Copying permitted for canas y finalmente las EBs se encargarán de reenviar-
private and academic purposes. los a los centros de control [IIO+ 17]. Por lo tanto, los
X
algoritmos de planeación, despliegue y enrutamiento M I = Zi,j , ∀ Z ∈ A(n) (6)
juegan un papel muy importante en redes inalámbri- M I∈A(n)
cas.
En nuestro método las agrupaciones se organizan X
en racimos. La característica fundamental de un PAD, M I = Xi,j , ∀ X ∈ A(n) (7)
radica en poseer doble tarjeta incorporada en el MI, M I∈A(n)
es decir, un PAD es un MI con doble tarjeta de ac-
ceso inalámbrico (WiFi y Celular), diferenciándose así X
S ≤ m, ∀ S ∈ A(n); ∀ m > 1 (8)
de un MI simple, que únicamente dispone de una sola s∈S
tarjeta de acceso inalámbrico WiFi, pero con disponi-
bilidad de dos slots. Por lo tanto, los PADs son capaces X
de recibir la información proveniente de los MIs me- Xi,j = rni ≤ rds , ∀ X ∈ A(n) (9)
diante tecnología WiFi y reenviar los datos mediante rnii,j ∈rds
tecnología celular.
X
Zi,j = rns ≤ rdb , ∀ Z ∈ A(n) (10)
3 Formulación del Problema rnsi,j ∈rdb
Existe n números de MIs para medición de energía
eléctrica distribuidos aleatoriamente en un área A, La ecuación (3) corresponde a la función objetivo,
A(n). Al formar agrupaciones, se selecciona un PAD que consiste en minimizar los costos empleando re-
Z. Cada conglomerado tiene una capacidad de agru- des inalámbricas híbridas. La ecuación (4) afirma
par hasta m MIs. Suponemos que el rango máximo de que necesariamente existe dos tipos de costos. En la
transmisión bidireccional de los MIs hacia los PADs ecuación (5) presenta una restricción de verificación,
es rds , y desde los PADs hacia las EBs es de rdb . Es en la que debe cumplirse que, la suma de enlaces me-
decir, cualquier pareja de nodos cuya distancia euclidi- diante tecnología WiFi y la suma de enlaces con tec-
ana rni y rns este dentro de rds y rdb respectivamente, nología celular no supere el número total de medidores
pueden comunicarse entre sí. Los MIs X y PADs Z inteligentes desplegados en el área, de esta manera se
que no alcancen la distancia euclidiana máxima per- garantiza que no exista bucles o loops.
mitida a un solo salto h, lo harán mediante múltiples Las ecuaciones (6) y (7) habilita a que cualquier
saltos. MI del escenario sea un PAD. La restricción de ca-
Inicialmente, todos los MIs se comunican mediante pacidad, de la ecuación (8), limita el número de MIs
tecnología celular hacia las EBs con un costo C1 . Una intra-clúster. En las ecuaciones (9) y (10) se da lugar a
vez identificado los conglomerados se eliminan los en- la existencia de los diferentes enlaces (Celular o WiFi),
laces celular y se adiciona enlaces WiFi para establecer que formaran parte de la red.
la comunicación intra-clúster a un costo C2 . Además
Basándose en el Algoritmo de PRIM, que se ha
se advierte que , C1 >> C2 .
modificado para los fines de la investigación, se con-
A continuación, en las ecuaciones (1 y 2) se expresan
struye los conglomerados considerando las restric-
los costos totales de cada tecnología (WiFi y Celular).
ciones de distancias máximas permitidas. En el algo-
k ritmo 1 se da solución al despliegue de MIs mediante
redes heterogéneas.
X
Cwf = C2 ∗ (sj − 1) (1)
j=1
Ccell = C1 ∗ k (2) 4 Análisis de Resultados
De esta manera, el problema de optimización puede Las restricciones ensayadas en el algoritmo son los
ser expresado de la siguiente manera. siguientes: distancias máximas Celular y WiFi 1.5 y
0.5 respectivamente, ubicación de las EBs [0,75 1,5]
min Cwf + Ccell (3) [2,25 1,5], número de exploraciones 100, capacidad
máxima de MIs de cada agrupación 23 y la densidad
Sujeto a: de MIs es 512.
El criterio de arranque para dar lugar a la forma-
Ci ∈ <+ , ∀ i = 1, 2 (4) ción de los conglomerados es a partir de distancias en-
tre MIs. El objetivo es generar diferentes escenarios,
X
(s − 1) + k = n, ∀ sk ∈ n; ∀ n ∈ A(n) (5) partiendo de distintas distancias tomadas en cada it-
s,k ∈ n eración.
Algoritmo 1 Despliegue de Medidores Inteligentes las EB mediante tecnología celular representado de
color celeste. Por lo tanto, en la Figura 1 se ilustra
Paso: 1 rdb , rds , xs , ys , EBx , EBy , G,
la topología tipo árbol cuasi-óptima para el despliegue
encuesta ← usados.
de MIs al menor costo garantizando cobertura al 100%.
Paso: 2 x= [xs EBx ], y= [ys EBy ]
100
# PADs (EB #1)
Cap-PAD 3
80
Paso: 3 Calcular: disti,j Cap-PAD 6
60 Cap-PAD 12
40 Cap-PAD 15
Paso: 4 Algoritmo de PRIM-Modificado. 20
Cap-PAD 18
return: tmp Cap-PAD 21
0
0 100 200 300 400 500 600
Número de MI
Paso: 5 nivel inferior 100
# PADs (EB #2)
while encuesta ≤ n do 80
Cap-PAD 3
Cap-PAD 6
if indice6= 1 60 Cap-PAD 12
indice(tmp) = 1 40 Cap-PAD 15
20
Cap-PAD 18
encuesta= sum(sum(indice)) Cap-PAD 21
0
endif 0 100 200 300 400 500 600
Número de MI
f or k → length(tmp)
f or j → length(tmp)
Dijkstra intra-clúter Figure 2: Número de PADs requeridos en diferentes
G(tmp(k), tmp(j)) = 1 poblaciones por cada EB. Fuente: Autor
G(tmp(j), tmp(k)) = 1
endf or En la Figura 2, cuando la capacidad de un PAD
endf or de albergar MIs es mínima y la población aumenta,
endwhile la necesidad de agregar PADs se torna indispensable
para garantizar de cobertura a los MIs. Por otro lado,
Paso: 6 Selección PAD cuando el PAD tiene mucha capacidad disponible,
la necesidad de PADs disminuye considerablemete en
Paso: 7 Dijkstra PAD
relación a un PAD con capacidades mínimas. Por lo
for i → 1 : length(P AD) tanto, a mayor capacidad disponible en los PADs y a
G(i, EB) = 1, G(EB, i) = 1. mayor número de MIs desplegados, se puede reducir
if rns > rdb al máximo el uso de tecnología celular, la cual es muy
G(i, EB) = 0, G(EB, i) = 0. costosa, y esto responde únicamente a que, dentro de
endif una red vecindaria se dispone de conglomerados clara-
endf or. mente definidos evitando la dispersión que a la larga
se traduce en pérdidas.
En la Figura 1 se ubican los MIs, PADs y las EBs
FSL(dB) (EB #1)
representados con circunferencias de color azul, verde 47
Cap-PAD 3
y triángulos amarillos respectivamente. 46 Cap-PAD 6
Cap-PAD 12
3 45 Cap-PAD 15
Cap-PAD 18
2.5
44 Cap-PAD 21
0 100 200 300 400 500 600
Número de MI
FSL(dB) (EB #2)
2
Distancia (km)
47
Cap-PAD 3
46 Cap-PAD 6
1.5
BS1 BS2 Cap-PAD 12
45 Cap-PAD 15
1 Cap-PAD 18
44 Cap-PAD 21
0 100 200 300 400 500 600
0.5
Número de MI
0
0 0.5 1 1.5
Distancia (km)
2 2.5 3
Figure 3: Pérdidas en el Espacio Libre Computados a
Estación Base MI Enlace Celular Enlace Wi-Fi PAD
una frecuencia de 5GHz . Fuente: Autor
Figure 1: Despliegue cuasi-óptimo de MIs para sis- Cuando el escenario tiene pocos PADs el prome-
temas de medición eléctrica inteligente Fuente: Autor dio de las pérdidas por propagación en el espacio libre
(FSL) es menor, pero cuando la población de PADs
Los MIs se enlazan a los PADs con tecnología WiFi aumenta el promedio de FSL aumenta. Por lo tanto,
representado de color rojo y los PADs se enlazan a en la Figura 3 se expresa que, a medida que los MIs
considerados como PADs se acercan a la EB, el prome- lo que nos lleva a requerir al mínimo, la tecnología
dio de FSL disminuyen, y por el contrario, cuando los celular que es la mas costosa. Además, el modelo ad-
PADs se alejan de la EB las pérdidas FSL aumen- mite parámetros reales tales como: capacidad y cober-
tan. Otra información importante que se obtiene de tura. En futuros trabajos se presentará una heurística
la Figura 3 es que el FSL no depende de la capacidad con diferentes criterios de clusterización y la inclusión
de los PADs, sino que depende de las distancias y la de flujos de información para evaluar cada enlace con-
frecuencia del espectro radioeléctrico, que para el caso siderando un multígrafo.
del cálculo de FSL se lo hace con una frecuencia de 5
GHz. Referencias
Se realizó varios ensayos para poder determinar por-
[GIKK11] Amitabha Ghosh, Özlem Durmaz Incel,
centajes máximos a los que se puede reducir el uso de
V. S. Anil Kumar, and Bhaskar Kr-
tecnología celular para minimizar costos de la IMA de
ishnamachari. Multichannel Scheduling
energía eléctrica. En la Figura 4, se ensayó con difer-
and Spanning Trees: Throughput Delay
entes densidades de MIs. La iteración 0 representa
Tradeoff for Fast Data Collection in Sen-
el punto inicial del problema, partiendo del supuesto
sor Networks. IEEE/ACM Transactions
que todos los MIs pueden ser DAPs, situación muy
on Networking, 19(6):1731–1744, 2011.
costosa. A medida que el algoritmo encuentra solu-
ciones cuasi-óptimas la necesidad de emplear DAPs va [ICHA17] Esteban Inga, Sandra Céspedes, Roberto
disminuyendo. Además, se puede apreciar que, a me- Hincapié, and Cesar Andy. Scalable
dida que la densidad de MIs es menor, menor es el Route Map for Advanced Metering In-
porcentaje posible para reducir costos. Por lo tanto, frastructure Based on Optimal Rout-
el algoritmo siempre logra reducir los costos de imple- ing of Wireless Heterogeneous Networks.
mentación de una IMA de energía eléctrica observando 24(April):1–227, 2017.
criterios de capacidad y cobertura.
[IH16] Esteban Inga and Roberto Hincapie.
600 Matched Channel Allocation for Ad-
Costo-min: 68.75 %
500 Costo-min: 82.81 % vanced Metering Infrastructure based on
Costo-min: 91.40 %
Costo-min: 92.97 %
Cognitive Mobile Virtual Network Oper-
400
Costo-min: 94.36 % ator. IEEE Latin America Transactions,
# PADs
300 14(4):1780–1785, 2016.
200
[IIO+ 17] Juan Inga, Esteban Inga, Andres Or-
100 tega, Roberto Hincapíé, and Cristina
Gómez. Optimal Planning for Deploy-
0
0 1 2 3 4 5 6 7 8 ment of FiWi Networks based on Hybrid
# Iteraciones
Heuristic Process. IEEE Latin America
Figure 4: Porcentajes máximos de reducción de uso de Transactions, 15(9):1684–1690, 2017.
tecnología celular logrado por el algoritmo con difer-
entes poblaciones de MIs. Fuente: Autor [IOPSH+ 16] Esteban Inga-Ortega, Arturo Peralta-
Sevilla, Roberto Carlos Hincapie, Fer-
ney Amaya, and Idelfonso Tafur Mon-
5 Conclusiones roy. Optimal dimensioning of FiWi net-
works over advanced metering infrastruc-
El algoritmo planteado permite desplegar el número ture for the smart grid. 2015 IEEE
necesario de PADs para medición de energía eléctrica PES Innovative Smart Grid Technolo-
proporcionando de cobertura a un número n de MIs. gies Latin America, ISGT LATAM 2015,
Una característica fundamental del modelo propuesto pages 30–35, 2016.
es que se adapta a las condiciones de la red inalámbrica
requerida para medición inteligente de energía eléc- [NDL14] Tamil Nadu, C Deepa, and B Latha.
trica. Al modificar los clústeres el algoritmo modifica HHCS : Hybrid Hierarchical Cluster
la topología y almacena las matrices de conectividad Based Secure routing protocol for wire-
para presentar al final la solución cuasi-óptima fruto less sensor networks. International
de varias exploraciones. La simulación del algoritmo Conference on Information Communica-
ha permitido analizar el uso de tecnología requerida en tion and Embedded Systems (ICICES),
la infraestructura híbrida propuesta, logrando con ello (978):0–5, 2014.
determinar la mínima cantidad de PADs a emplearse,