Transcript PowerPoint 簡報

慈濟大學醫學資訊系演講簡報
題目
運用叢集組合及分散法則於無線網路點遷移
拓樸之定型
(Cluster Association and Dissociation Method due
to node migrations for Topology Dominating in
Wireless Networks)
Presented by Reu-Ching Chen
2009/10/26
個人簡歷
•
•
•
•
•
學歷: 逢甲大學資訊博士(95年畢業)
經歷: 中華電信高級技術員(70/1~95/3)
現職: 南開科技大學助理教授(95/8~迄今)
證照: 高考及格
榮譽: 中央研究院 JISE 2007 Annual best
paper award
可教授科目
• 1. 演算法, 計算機結構, 作業系統
• 2. 線性代數, 機率論, 隨機過程
Outline
•
•
•
•
•
1. Introduction
2. Model Description
3. Mathematical Analysis
4. Numerical Results and Discussions
5. Conclusion
1.Introduction
• Traditional organization on real-time
communications  Infrastructure-based
( which is fixed organization)
• Modern organization Self-organized
• Peer-to-peer communication will be
unrealistic when the total number of
communicating node become large
Conti.
• Node partition method due to cluster association
and dissociation will be useful for topology
dominating.
• Closed migration system(total number of nodes in
the system N is fixed) is considered here.
• Markov-chain(memory-less property) is adopted
for the system topology dominating in our study.
2.Model Description
• Continuous time Markov chain (CTMC) is
used for analysis (Example: a two-state
model is depicted as follows)
State 0


State 1
Conti.
• Where  and 
are the transition
probability for state 0 and 1, respectively
• The system is assumed ergodic,
I.e., for the existence of the steady state
condition,we have
t
 X (s)ds
lim
t  
0
t
 E[ X ]
Conti.(Cluster organization)
• Two clusters: cluster 1 and 2 contain five
groups and three groups respectively
Cluster 1
Cluster 2
Conti.
• Therefore, in general, each group in cluster i
contains i nodes
Node 1
Node i
Conti.
• The system includes finite number of
clusters, where each group located in the
same cluster owning the same number of
nodes.
Conti.
• Theoretically, since the system topology
changes with time dynamically, then in a
unit of time,any nodes of a group (belongs
to a specific cluster) can dissociate and be
combined with other nodes to constitute one
group of a cluster.
Conti.
• For convenience, the system state
transitions are carried by the following
migration rules.
Rule1: U individuals of cluster 1 can
associate to constitute a group of cluster U.
Rule 2:one group of cluster U can only
dissociate to constitute a U individuals of
cluster 1.
Conti.(migration rule)
1
M
gM
1
M
Cluster M
Cluster 1
1
N
1
N
gN
Cluster N
3. Mathematical analysis
• The following notations are adopted for
parameters
Let N indicate the total number of nodes.
Let g i indicate the total number of groups
in cluster i then
N
 ig
i 1
i
N
Conti.
• Let AU indicate the probability intensity
that cluster 1 associates its U individuals to
generate a group of cluster U
• Let DU indicate the probability intensity
that a group in cluster U disassociate into U
individuals
Conti.(state transition diagram)
• Let G  ( g1 , g 2 ,..., g k ) indicate the
countable state space, and  be the state,
then the CTMC is as follows
DU ( gU  1)
 g1 
AU  
U 
 ( g1  U , g 2 ,..., gU  1,..., g k )
 ( g1 , g 2 ,..., gU ,..., g k )
Conti.
• Where
 g1 
g1!
  
 U  U !(U  g1 )!
• Define the disassociate and associate
operators as follows
OU1 (G )  ( g1  U , g 2 ,..., gU  1,..., g k )
O1U (G )  ( g1  U , g 2 ,..., gU  1,..., g k )
Conti.
• Then the transition rates between states are
 g1 
T (G, O (G ))  AU  
U 
1
U
and
T (G, O1U (G ))  DU ( gU )
Conti.
• We have the following theorem
Theorem: if there exist a positive numbers
k1 , k2 ,..., k N
denoted by
satisfying
the following relation U !kU DU  (k1 )U AU
then the solution for the N nodes system has
the closed form.
Conti.(closed form solution)
• I.e.,
N
gi
i
k
 (G )  C N 
i 1 g i !
Where C N is the unique collection of positive numbers summing
to unity, I.e.,   (G )  1
• Proof > the proof is completed by
conjunction of the above Equations and the
balanced equation
 (G )T (G, OU1 (G ))   (OU1 (G )T (OU1 (G ), G )
Conti.
• Since the group number g i is a stochastic
process with state space {1,2,…,k} that
restart itself , then we can think the process
is a regenerated counting process.
Conti.
• Using the strong law,The A/D ratio is

 X (t )dt
i
Ai P( X i  x) 1  E ( X i )



Di P(Yi  y ) 1  E (Yi )
lim
0
t  
t

 Y (t )dt
i
lim
t  
0
t
4. Results and discussions
Type of A/D
ratio
increasing
Estimated
bandwidth
33
Original
Reduced
bandwidth percent
45
26%
decreasing
36
45
20%
normal
25
45
44%
uniform
33
45
26%
Conti.
• a more accurate estimation for system
performance is obtained from the the
dominating topology provided here.
• The proposed method cab be easily
implemented in any topology dominating.
• Node association and disassociation can be
generalized without constraint.
General case considerations
State(2,2,1,0,…,0)
State (5,2,0,…,0))
Only allow one association or disassociation occurring
In an infinite small time unit
5. Conclusions
• <1> A/D ration has an critical influence to
the system topology dominating
• <2> the clustering method is wide spread
applicable to other systems for the topology
validation.
• <3> our contribution is focused on provide
simple estimation for topology construction
Conti.
• <4> future challenge (1): concentrating on
searching more generic topology to achieve
optimal performance.
• <5>future challenge(2): extend the system
of closed migration process to open
migration process (allow node to enter or
leave the as well as to move between
clusters).
Thanks so much for you