An expert system approach for the design of cable networks
Abstract
The aim of this paper is to show the utility of expert systems in the task of designing cable networks. At Enditel Endesa' we are currently developing a project called Datacab in collaboration with the Electronic Technology Department of the University of Seville. Datacab is an expert system for automatic routing and positioning of the elements of both the civil design and the cabling of a cable telecommunication network. It uses as input data from a GIS (Geographic Information System) and obtains an optimal design by applying a specific design rules database. Datacah's representation of the geographic information is entirely based on graphs. Among the advantages of the proposed expert system approach is the possibility to add new rules or to modify present rules easily if design criteria change.
Full text
AN
EXPERT SYSTEM APPROACH FOR
THE
DESIGN
OF
CABLE NETWORKS
IBigo Monede o Ca los Leon Robe Denda
School
o
Compu e
School
o
Compu e
Endi el
Endesa:
Science and
Enginee ing
Science
and
Enginee ing R&D Depamnen
Elec onic Technology
Elec onic
Technology
Wo ld
T ade
Cen e
lsla
de
la
Cmja
s/n
41012
Se ille(Spain) 41012 Se ille
(Spain)
41092Se ille(Spain)
Dep;uimen
Depa men
A da,
Reina
Me cedes
sin
A da,
Reina
Me cedes sin
Abs ac
-
The aim o his pape is o show he u ili y
o
expe
sys ems in he ask o designing cable ne wo ks. A Endi el
Endesa' we a e cu en ly de eloping a p ojec called Da acab in
collabo a ion wi h he Elec onic Technology Depa men o he
Uni e si y o Se ille. Da acab is an expe sys em o au oma ic
ou ing and posi ioning o he elemen s o bo h he ci il design
and he cabling o a cable elecommunica ion ne wo k. I uses
as inpu da a om a GIS (Geog aphic In o ma ion Sys em) and
ob ains
an
op imal design by applying a speci ic design ules
da abase. Da acah's ep esen a ion o he geog aphic
in o ma ion is en i ely based
on
g aphs. Among he
ad an ages o he p oposed expe sys em app oach is he
possibili y o add new ules o o modi y p esen ules easily i
design c i e ia change.
I.
INTRODUCTION
A.
Expe
Sys ems
An expe sys em is a compu e p og am, which uses non-
nume ical domain-speci ic knowledge in o de
o
sol e
p oblems wi h a compe ence le el compa able wi h ha o a
human expe who is able o e icien ly sol e domain-
speci ic p oblems. Rule-based p og amming is one o he
mos commonly used echniques o de eloping expe
sys ems
[I].
In his p og amming pa adigm, ules a e used o
ep esen heu is ics,
o
" ules o humb, which speci y
a
se
o ac ions o he pe o med o a gi en si ua ion.
Expe sys ems ha e been success ully applied on
elecommunica ion ne wo ks
[2][3][4]
and, in gene al, o he
sea ch
o
op imal solu ions o p oblems o g aphs
[5].
Since
a cable ne wo k's opology can he s udied as a connec
g aph, i makes i pe ec ly sui able o applying such an
expe sys em app oach.
E.
Cable ne wo ks
Cu en cable ne wo ks a e ypically implemen ed as HFC
(Hyb id Fib e Coax) ne wo ks, whe e ansmission media a e
op ical ib es and coaxial cables, and po en ially
a
pa allel
elephony ne wo k.
I
All in ellec ual p ope y igh s o he p esen ed Sys em a e
hold by Endi el Endesa. Fo u he in o ma ion, please
con ac any one o he au ho s.
0-7803-7474-6102/517.00
02002
IEEE
Samuel Muiioz
JosC
Manuel Elena Joaquin Luque
Endi el
Endesa:
School
o
Compu e
School
o
Compu e
R&D
Depamnen
Science
and
Enginee ing Science
and Enginee ing
Wo ld
T ade
Cen e
Elec onic
Technology
Elec onic
Technology
Isla
de
la
Cmja
sin
41092Se ille(Spain)
41012
Se ille
(Spain) 41012 Se ille(Spain)
Depamnen
Depamn-Z"
A da,
Reina
Me cedes
sin
A da, Reina Me cedes
dn
The cable ne wo k s uc u e o he designed suppo s Cable
ele ision, In e ne access and elephony se ices. The ibe
op ic ne wo k is s uc u ed by a head-end connec ed o a
p ima y ne wo k, which con ains a numbe o main nodes
se icing be ween
30.000
o
90.000
homes each. These main
nodes a e connec ed o a ne wo k o se e al seconda y nodes
(seconda y ne wo ks), each o which se es a ound
10.000
homes. In gene al, he seconda y nodes also con ain
a
RTC
(Remo e Telephony Cen e ). The e ia y ne wo ks
(dis ibu ion ne wo k) connec o he seconda y node and
se ice abou
2.000
homes. E e y e ia y ne wo k ends in
ONTs (Op ical Ne wo k Te mina ion), which a e connec ed
o a Coax Ne wo k. This Coax Ne wo k inally dis ibu es
he signal o subsc ibe s.
The Telephony Ne wo k ypically s a s a each RTC and has
h ee le els. The i s le el connec s each RTC o a ONT, he
second le el eaches each package o homes, and inally, he
hi d le el connec s he subsc ibe s' homes.
C. Da acab
Da acab is an expe sys em based on ules
o
au oma ic
ou ing o a HFC elecommunica ion ne wo k as well as i s
co esponding ci il design. Da acab will be applied o
a ious cable communica ion ne wo ks wi h an a e age o
mo e han
200.000
use s each.
Some o he ad an ages o he p oposed expe sys em
app oach a e he possibili y o adding new ules and o
modi y p esen ules easily i he design c i e ion changes.
Design ules can be s died in
a
di ahase in o de o imp o e
accessibili y; inally he de eloped sys em can he used o
ain new s a .
11.
DESIGNING DATACAB EXPERT SYSTEM
A.
Knowledge acquisi ion
The i s s ep in building an expe sys em is he knowledge
acquisi ion. I in ol es elici ing, analyzing, and in e p e ing
he knowledge abou he cu en ne wo k design. Se e al
echniques
o
ex ac ing expe knowledge ha e been
desc ibed in he li e a u e
[6].
We selec ed an app oach o
s uc u ed in e iews wi h he human ope a o s as he main
acquisi ion echnique. A s uc u ed in e iew is a
con e sa ion be ween he expe s and he knowledge
1899
enginee s. The di e ence be ween a s uc u ed in e iew and
a no mal mee ing is ha he knowledge enginee mus decide
on he ques ions and objec i es o discuss be o e he mee ing.
A specialized echnician was commended o ca ying ou
he expe wo k. Along
5
sessions om
1
o
2
hou s
we e
necessa y o build ou i s knowledge base. A ailable
demons a ions abou
HFC
sys em we e addi ionally used.
B. Knowledge Rep esen a ion
Once knowledge had been acqui ed, he nex s ep was i s
ep esen a ion. A class diag am and a ule-based sys em had
o be buil o i . The geog aphic elemen s wi h hei loca ion
and e-design in o ma ion (i.e., possible accc:ss o
accommoda ions, p e ious channel loca ions, non-pe mi ed
aqades
...)
a e s o ed in he
GIS
applica ion.
Class diae am
The class diag am o Da acab was designed wi h he help
o
he Ra ional Rose ool using an
UML
app oach
[7][S]
and
is
composed o
7
packages, which a e linked in he way shown
in ig.
1.
I includes he geog aphical elemen s ((s ee s,
buildings...), e-design in o ma ion (buildings accesses..
.),
coax elemen s (wi es, ampli ie s
...)
and ci il elemen s
(caske s, channels
...)
in addi ion o supe classes o all he
p e iously men ioned elemen s (poin -class, coax-class...).
These supe classes we e c ea ed o gene alize some common
p ope ies o
ou
objec s such as dis ances in linea elemen s
and signal losses in elemen s o he coax ne wo k.
Fig.
1. Package diag am
The
Ke nel
package is made up by he knowledge classes,
e.g., he algo i hm-class. All o Da acab's classes a e de i ed
om one supe class called
Cis
om he
BaseType
package
(see ig.
2).
This class emb aces he main shapes. o he
geog aphical elemen s: poin , segmen and a ea. On he o he
hand, in he
Map
package a e he classes ela ed
o
ci y
elemen s: buildings, blocks, s ee s, oads, pa ks and
:io
o h.
Fig.
2.
BaseTpe package
The
Coax
]package has a supe class called
Coax,
which
con ains h ee classes co esponding o he ype
o
coax
elemen : pa,isi e componen (i.e., wi es), ac i e componen
(ampli ie s) and powe sou ce ( o eed ac i e componen s).
The di e en passi e componen classes o he coax design
a e shown in ig.
3.
In his example ( ig.
3),
he ad an ages o
he inhe i ance can he seen: inhe i ed classes om
Passi e
ge he cha ac e is ics om coax elemen s and hei
geome ic d:i a.
Fig.
3.
Coax passi e elemen s
Finally, he design o he ci il componen classes is made up
by a main class called
Ci il.
Simila ly o he o he
supe classej,
Ci il
has wo child classes depending on hei
cha ac e is ics, dis inguishing segmen s and poin s. The i s
class inhe i s om
Segmen
whe eas he second one om
Poin .
Da acab will ins an ia e one copy o each di e en child class
o he coax diag am and ci il diag am and he a ibu es wi h
echnical cha ac e is ics a e illed in acco ding o hei
cons uc o ia da abase accesses.
Da acab's da abase con ains all he cha ac e is ic da a o he
ne wo k elimen s as well as hei subg oups used o he
co esponding ci y
o
zone. The adminis a o only has o
change he da abase o upda ing Da acab.
1900
Rules-based s s em
Ou knowledge base
is
a
ules-based sys em: he knowledge
is
ep esen ed in he o m o IF
...
THEN ypes ules (p emises
and conclusions), ac s and assump ions abou he p oblem.
This easoning sys em was chosen o e o he s (e.g., case-
based easoning) due o he ac ha he al e na i es in he
cable ne wo k design a e subjec o ules.
So,
when an
expe ca ies ou he design, he guides himsel by p io i y
ules and expe ience, wi h he main pu pose o eaching
e e y subsc ibe homes o u u e subsc ibe homes. Some
ules in ou ing phases a e shown
in
able
I
and he code o
an example one
in
able
XI.
Cu en ly, ou sys em con ains
abou
80
ules.
be
P io ih,w
SESS-OI max
SESS-02 mid
SESS-03 min
111. DATACAB EXECUTION PROCESS
A. Phases
Da acab achie es he ou ing
o
he HFC ne wo k h ough
di e en phases. The di e en phases o Da acab's execu ion
a e shown
in
ig.
4.
Fo coding o hese phases we used a
powe ul ool o expe sys ems called A 'En e p ise.
The i s and he las p ocess o he execu ion diag am (GIS
In e p e e ) a e ela i ely simple due o he ease o he
GIS
ool o expo da a o a desi ed o ma . As a esul , he
in e p e e module gene a es a ile wi h he
GIS
in o ma ion
acili a ing he con e sion p ocess.
The a ibu es o he geog aphical elemen s a e speci ied in
ou class diag am and he objec s c ea ed in he second s ep
a e ins ances o hese classes.
I
GIS
In o ma ion
Cable o e apade
is
be e han cable
ia ubes.
Cable ia ubes unde asphal is be e
han unde pa emen .
The highe he sa ings in cable he
TABLE
I
SOME
RULES FROM
DATACAB
SEDC-02 mid Cable p e e ed i i does no c oss
a enue o Main S ee .
I
be e .
Dynamic (dependen o p e iously selec ed edges)
be
SEDC-01
I
max
I
No
cycles in he g aph
o
ou cable
I
I
I
edges he be e
I
TABLE
II
CODE
OF
SESS-OI
RULE
le ine- ule SESS-01
(decla e (salience
900))
(objec ?algo i hm (ins ance-o algo i hm500-1)
(phase s a ic-cos )
(CS ?node-lis )
(RS
?non-node-lis ))
(ins ance-o dcs ee ))
(ins ance-o dc:non- aqade))
(objec ?s ee 1
(objec ?s ee 2
( es (no (equal ?s ee 1 ?s ee 2)))
( es (no (membe $ ?s ee 1 ?node-lis )))
( es (no (membe $ ?s ee 1 ?non-node-lis )))
( es (supe imposed ?s ee 1 ?s ee 2))
(add-amihu e- alue ?algo i hm CS 7s ee l))
=>
Da acab
In o ma ion
C ea ion
o abjec
Coax
and
Ci il
Solu ion
.(
GIS Solu ion
Fig.
4.
Execu ion diag am o Da acab
E.
Rou ing algo i hm
The
Ke neI
package (see ig.
1)
has embedded he
Ke nel
supe class and
Algo i hm
class. These classes, which make
up he knowledge base, ake ca e o i ing he ules in e e y
phase o he algo i hm'. Besides, he esul s a e s o ed
in
he
class
Algo i hm.
The ke nel algo i hm, cu en ly unde de elopmen , will he
made up o phases each one
o
which will i e
a
g oup o
ules. The i s design idea o he algo i hm consis s o i s
pe o ming he cable ne wo k ou ing, and hen loca ing hee
coax and ci il elemen s.
In
he case ha i u ns ou o be
1901
impossible o place he elemen s wi hin one single cable
ne wo k ou ing,
i
will be ca ied ou du ing a second
ou ing.
The i s s age o he sea ch algo i hm will be based
on
he
K uskal’s algo i hm [9], which
is
a his o ical minimum
expansion ee sea ch algo i hm. These algo i hms ha e a
connec ed g aph as inpu and gene a e a ee co e ing he
whole g aph wi h he lowes possible cos .
In
pa icula ,
K uskal’s algo i hm selec s he lowes cos edge in each one
o he i e a ions, as
long
as his does no gene a e any cycles.
The di e ence be ween K uskal’s algo i hm and ou
algo i hm is in he dynamic cha ac e is ic o he la e one.
While he edge cos in K uskal’s algo i hm does no depend
on
he p e iously selec ed edges, in
ou
algo i hm . he cos
will he allowed o a y. The di e en phases o he algo i hm
o Da acab a e shown in ig.
5.
places-
coax-elemen s
esal s-edges-
by-s a ic-cos
phases
o
he ne wo k ou ing ha e been implemen ed. We
a e cu en ly de eloping he s age o he p ojec ha will
allow
us
o place he coax and ci il elemen s acco ding o he
es ablished ules and signal le el calcula ions.
Besides, we a e p epa ing a es me hod ( alida ion p ocess).
Once inalized hese phases, an expe will e i y he co ec
ne wo k dasigns ca ied ou by Da acab ( e i ica ion
p ocess).
calls
GIS
In e p e e
Fig.
6.
Example o ou ing ob ained o a cable ne wo k
V.
REFERENCES
[I]
E.M. A ad. “Building Expe Sys ems”. Wes Publishing
Company, 1996.
[2] C. Le6n, M. Mejias,
J.
Luque y
F.
Gonzalo. “Expe
sys em o he in eg a ed managemen o
a
powe u ili y’s
communicai:ion sys em”.
IEEE
T ansac ions
on
Powe
Deli e y,
ol. 14,
no
4,
pp, 1208-1212, Oc . 1999.
[3] Jay Liehowi z ed:
“The handbook
o
Applied Expe
Sys ems”.
CRC P ess, 1998.
[4]
I.
Vlahu. as e al. “Expe Ne : An In elligen Mul iagen
Sys em o WAN Managemen ”. IEEE In elligen Sys ems,
ol.
17,
n”4, pp. 62-12,2002.
[5]
E. Cas illo,
J.
Gu ie ez, A1i.S Hadi. “Sis emas Expe os y
Modelos da Redes P obahilis icas”. Monog a ias de la
Academia EspaRola de Ingenie ia, Mad id, 1998.
[6] K.L. McG aw and
K.
Ha hison-B iggs. “Knowledge
acquisi ion: P inciples and guidelines”. P en ice-Hall,
Englewood Cli s, N.J.
[7]
G.
Booch,
J.
Rumbaugh and I. Jacobson. “UML. El
Lenguaje Uni icado de Modelado”, Addison Wesley, 1999.
[8] W. Boggs, M. Boggs. “Mas e ing UML wi h Ra ional
Rose”,
Sybex Inc,
1999.
[9]
R.
Sedgewick “Algo i mos
en
C++”.
Addison Wesley
Ibe oamenca, 1995.
1902