Health Articles

200805_lecture9.ppt [兼容模式]

r ng
i
n
i A
d hoc
ne
t ork
Application Layer Presentation Layer à What t r ss à Where Wireless Ad hoc network – Lecture 9 u e 9
Clustering in Ad hoc network

l Motivation for Clustering in ad hoc networks l What is Clustering l Clustering algorithm l DS-based clustering l Low-Maintenance clustering l Mobility-Aware clustering l Energy-efficient clustering l Load-balancing clustering l Combined-metrics-based clustering Wireless Ad hoc network – Lecture 9

f
o
f r
r C
lus
t ri
r ng
l Challenge of ad hoc networks l The routing overhead of a link-based proactive routing protocols increases with the square of the number of mobile nodes in an ad hoc network.
l Solution: Clustering l A hierarchical architecture is helpful for achieving a basic performance guarantee in a large-scale ad hoc network.
l In a clustering scheme, the mobile nodes are divided into different virtual groups. They are allocated geographically adjacent into the same cluster according to some rules.
Wireless Ad hoc network – Lecture 9

What
t i
s
i C
lus
t ri
r ng
Cluster 2
Cluster 1
Cluster 3
Wireless Ad hoc network – Lecture 9

What
t i
s
i C
lus
t ri
r ng
l Under a cluster structure, mobile nodes may be assigned a different status or function, such as cluster head, cluster gateway, or cluster member.
l Cluster head: serve as a local coordinator for its cluster.
l Cluster gateway: non-cluster head node with inter-cluster links, so it can access neighboring clusters and forward information between clusters.
l Cluster member: non-cluster head node without any inter- cluster links (ordinary node).
Wireless Ad hoc network – Lecture 9

Wireless Ad hoc network – Lecture 9

t re
r o
f C
f lus
t ri
r ng
l Flat clustering & hierarchical clustering Wireless Ad hoc network – Lecture 9 i o
f C
f lus
t ri
r ng
l Disjoint & overlapping Wireless Ad hoc network – Lecture 9 dvan ages
o C
l
C ust
us er
e ing
l Clusters are formed (dynamically) to provide hierarchy. Global routing is done to clusters. Local routing is done to nodes within a cluster. Clusters of clusters (super-clusters) can be formed to extend hierarchy. l Increasing the system capacity l With the non-overlapping multicluster structure, two clusters may deploy the same frequency or code set if they are not neighboring clusters.
Wireless Ad hoc network – Lecture 9 dvan ages
o C
l
C ust
us er
e ing
ng (
l Routing more efficient l The generation and spreading of routing information can be restricted in clusters.
l Increasing stability l When a mobile node changes its attaching cluster, only mobile nodes residing in the corresponding clusters need to update the information. Local changes need not be updated by the entire network, information processed and stored by each mobile node is greatly reduced.
Wireless Ad hoc network – Lecture 9 l Motivation for Clustering in ad hoc networks l What is Clustering l Clustering algorithm l DS-based clustering l Low-Maintenance clustering l Mobility-Aware clustering l Energy-efficient clustering l Load-balancing clustering l Combined-metrics-based clustering Wireless Ad hoc network – Lecture 9 t ri
r ng
a
lgo
r hm
l The clustering schemes classified according to different criteria For example: (1) cluster head-based clustering and non-cluster head-based clustering protocols.
(2)1-hop clustering and multi-hop clustering l We classify the clustering protocols based on their Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
(1) DS-based clustering (dominating set): Finding a (weakly) connected dominating set to reduce the number of nodes participating in route search or routing table maintenance.
l Wu's CDS algorithm l Chen's WCDS algorithm Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
algori hm: Find a minimum number of nodes as dominating nodes to construct a CDS (connected dominate set). Decrease the number of nodes participating in routing Reduce the DS size to eliminate unnecessary dominating nodes without breaking the direct connection between neighboring dominating nodes Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
Initially, every node v exchanges its neighbor list with all its neighbors. A mobile node sets itself as a dominating set if it has at least two unconnected neighbors. (marking process) Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
l Then some rules are implemented to reduce the size of a CDS generated in the marking process.
l CDS maintenance l any moving node needs to continue to send out a beacon message every t second during its movement l other related mobile nodes keep monitoring the messages from that moving node.
Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
lgorithm: l Find a minimum number of nodes as dominating nodes to construct a WCDS (Weakly CDS). l Decrease the number of nodes participating in l Reduce the DS size by relaxing the direct connection requirement between dominating nodes. Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
l The number of clusters produced by the CDS clustering is rather large and the formed cluster structure is likely highly overlapping.
l Chen proposed that by relaxing the requirement of direct connection between neighboring dominating nodes, l WCDS is smaller in size than CDS, and hence it is better for further simplifying the network structure.
Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
iii. Summary of DS-based algorithm: l The objective of the two DS-based clustering schemes is to attempt to select a small number of mobile nodes as dominating nodes to form the DS, which can form an inter-cluster routing backbone in a network. l Both schemes form 1-hop clusters with dominating nodes serving as clusterheads. Wireless Ad hoc network – Lecture 9 d
d c
lu
l s
r ng
l Compared with Wu's algorithm, Chen's algorithm can form fewer clusters, resulting in less overlapping cluster architecture by relaxing the direct connection requirement between dominating nodes. l Hence, Chen's algorithm should be more effective in simplifying a network structure.
Wireless Ad hoc network – Lecture 9 lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 l Motivation for Clustering in ad hoc networks l What is Clustering l Clustering algorithm l DS-based clustering l Low-Maintenance clustering l Mobility-Aware clustering l Energy-efficient clustering l Load-balancing clustering l Combined-metrics-based clustering Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
(2) Low-maintenance clustering: Providing a cluster infrastructure for upper layer applications with minimized clustering-related maintenance cost.
l LCC (Least Cluster Change) l 3hBAC (3-hop Between Adjacent Clusterheads) l Lin's algorithm l PC (Passive Clustering) Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
i. LCC (Least Cluster Change):
l Limiting re-clustering situations and reducing clustering control overhead.
l Clustering algorithm is divided into two steps: cluster formation and cluster maintenance.
l The cluster formation simply follows LIC, i.e. initially mobile nodes with the lowest ID in their neighborhoods are chosen as clusterheads.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
Re-clustering is event-driven and invoked in • When two clusterheads move into the reach range of each other, one gives up the clusterhead role.
• When a mobile node cannot access any clusterhead, it rebuilds the cluster structure for the network according to LIC.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
LCC significantly improves cluster stability by relinquishing the requirement that a clusterhead should always bear some specific attributes in its local area. But the second case of re-clustering indicates that a single node's movement may still invoke the complete cluster structure recomputation, and once this happens, the large communication overhead for clustering may not be avoided.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
ii. 3hBAC (3-hop Between Adjacent Clusterheads):
Limiting re-clustering situations, reducing clustering control overhead, and eliminating ripple effect of re-clustering; producing non-overlapping cluster structure and eliminating unnecessary small clusters.
The mobile node with the lowest ID closed neighbor set is chosen to be the first clusterhead. All the direct neighbors of this clusterhead change status to "clustermember." Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
A clustermember or a direct neighbor of any clustermember with status "unspecified" ( not included in any cluster) are declined the capability of serving as a clusterhead. A mobile node, without being declined clusterhead capability, declares as a new clusterhead when it is with the highest node degree in its neighborhood.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
When a mobile node finds out that it cannot serve as a clusterhead or join a cluster as a clustermember, but some neighbor is a clustermember of some cluster, it joins the corresponding cluster as a clusterguest.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
Cluster formation illustration Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
Cluster membership update illustration Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
iii. Lin's algorithm: An adaptive clustering scheme to form a non- overlapping cluster architecture without clusterheads, because clusterheads bear extra work compared with ordinary member nodes and likely will become the bottlenecks of a network.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
iv. PC (Passive Clustering):
PC is a clustering protocol that does not use dedicated clustering-protocol-specific control packets or signals.
Wireless Ad hoc network – Lecture 9 i ten
a ce
c c
lus
t ri
r ng
v. Summary of LCC and 3hBAC 1-hop or multi-
Wireless Ad hoc network – Lecture 9 l Motivation for Clustering in ad hoc networks l What is Clustering l Clustering algorithm l DS-based clustering l Low-Maintenance clustering l Mobility-Aware clustering l Energy-efficient clustering l Load-balancing clustering l Combined-metrics-based clustering Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
(3) Mobility-aware clustering: Utilizing mobile nodes' mobility behavior for cluster construction and maintenance and assigning mobile nodes with low relative speed to the same cluster to tighten the connection in such a cluster.
l DDCA (Distributed Dynamic Clustering Algorithm) Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
i. MOBIC:
Objectives:
Minimizing the influence of mobile nodes' movement
on cluster topology updates in terms of re-affiliation and re-clustering based on mobile nodes' explicit relative speed; tightening the connection between mobile nodes residing in the same clusters.
Clusterhead election should take mobility into consideration. It points out that clusterhead election is a local activity so that a clusterhead should be determined only by its neighbors and itself.
Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
By calculating the variance of a mobile node's speed relative to each of its neighbors, the aggregate local speed of a mobile node can be estimated.
Mobile nodes with low variance values in their neighborhoods take the clusterhead responsibility.
Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
ii. DDCA (Distributed Dynamic Clustering
Minimizing the influence of mobile nodes' movement on cluster topology updates in terms of re-affiliation and re-clustering to meet (a, t) criteria; adjusting the dominant routing mechanisms based on a network's mobility behavior.
Attempts to partition a number of mobile nodes into multi-hop clusters based on (a, t) criteria.
The (a, t) criteria indicate that every mobile node in a cluster has a path to every other node that will be available over some time period t with a probability more than a regardless of the hop distance between them.
Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
The purpose is to support robust and efficient routing, and adaptively adjust its dominant routing scheme depending on the network mobility manner.
Wireless Ad hoc network – Lecture 9 r c
lus
t ri
r ng
iii. Summary of mobility-aware clustering:
Wireless Ad hoc network – Lecture 9 l Motivation for Clustering in ad hoc networks l What is Clustering l Clustering algorithm l DS-based clustering l Low-Maintenance clustering l Mobility-Aware clustering l Energy-efficient clustering l Load-balancing clustering l Combined-metrics-based clustering Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
(4) Energy-efficient clustering: Avoiding unnecessary energy consumption or balancing energy consumption for mobile nodes in order to prolong the lifetime of mobile terminals and a network.
l IDLBC (ID Load Balancing Clustering)
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
IDLBC (ID Load Balancing Clustering):
Avoiding possible node failure because of excessive serving as clusterheads by limiting the time that a mobile node can serve as a clusterhead continuously.
Each mobile node has a variable, virtual ID (VID), and the value of VID is set as its ID number at first.
Mobile nodes with the highest IDs in their local area win the clusterhead role.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
When two clusterheads move into the reach range, the one with higher VID wins the clusterhead role.
Each non-clusterhead node keeps a circular queue for its VID and shifts the VID value by one every time unit in one direction.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
Thus, when a clusterhead resigns, a non- clusterhead with the largest VID value in the neighborhood can resume the clusterhead IDLBC tries to avoid possible node failure due to energy depletion caused by excessively shouldering the clusterhead Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
ii. Wu's Algorithm:
Guaranteeing the CDS connected and at the same time decreasing the total energy consumption of a network by deleting unnecessary mobile nodes with poor energy level from the CDS.
Mobile nodes inside a DS consume remarkably more battery energy than those outside a DS. Hence, it is necessary to minimize the energy consumption of a DS.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
Wu proposed that energy level instead of ID or node degree is used in the extension rules to determine whether a node u should remain Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
Although the algorithm is more energy- aware compared with other DS-based clustering algorithms, still cannot balance the great difference of energy consumption between dominating nodes and non-dominating nodes.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
iii. Ryu's Algorithm:
Serving slave nodes as many as possible and minimizing the total energy consumption between all communicating master-slave pairs.
There are two types of nodes in the algorithm, master (clusterhead) and slave (member). A slave node can connect to only one master node, and a direct link between slaves is not allowed.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
Master nodes are somehow selected in advance, and each can only serve a limited number of slave nodes.
The specific objectives of Ryu's scheme are to minimize the transmission energy consumption summed by all master-slave pairs and to serve as many slaves as possible in order to operate the network with longer lifetime and better performance.
Wireless Ad hoc network – Lecture 9 t
t c
lus
t ri
r ng
iv. Summary of Energy-efficient Clustering:
1-hop or multi-
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
(5) Load-balancing clustering: Distributing the workload of a network more evenly into clusters by limiting the number of mobile nodes in each cluster in a defined range.
l AMC (Adaptive Multi-hop Clustering)
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
i. AMC (Adaptive Multi-hop Clustering):
Balancing the traffic load in each cluster by limiting the number of mobile nodes that a cluster can handle within a predefined range.
Maintains a multihop cluster structure based on In AMC, when the number of members, /Ci/, in a cluster Ci is less than L, the merge mechanism is invoked.
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Cluster Ci tries to find a neighboring cluster Cj to satisfy /Ci/ + /Cj/ <U and maximize the sum value.
If /Ci/ + /Cj/ > U for all neighboring clusters, it tries to find a Cj to minimize the sum value.
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
When two clusters merge, the clusterhead with more member nodes wins to continue the clusterhead role.
Next, we will illustrate the cluster merging.
Figure a shows the initial structure of cluster A, B, and C.
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Figure b shows that the gateways f and j of cluster C exchange the information about the number of members with neighboring clusters. Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Figure c indicates that the information is forwarded to the clusterhead. Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Figure d shows that cluster C invokes the merge process and merges with cluster A. The clusterhead of cluster A becomes the clusterhead of the newly merged cluster because it has more member nodes than cluster C.
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
ii. DLBC (Degree-Load-Balancing
Objective:
Balancing the traffic load in each cluster by
limiting the number of mobile nodes that a cluster can handle around a predefined value periodically runs the clustering scheme in order to keep the number of mobile nodes in each cluster around a system parameter, ED, which indicates the optimum number of mobile nodes that a clusterhead can handle.
Wireless Ad hoc network – Lecture 9 c ng
c
lus
t ri
r ng
iii. Summary of Load-balancing Clustering:
1-hop or multi-
Wireless Ad hoc network – Lecture 9 C m
o bi
b ned
l
c ust
us er
e ing
(6) Combined-metrics-based clustering: Considering multiple metrics in cluster configuration, including node degree, mobility, battery energy, cluster size, etc., and adjusting their weighting factors for different application scenarios.
l On-Demand WCA (Weighted Clustering Algorithm)
Wireless Ad hoc network – Lecture 9 [1] Jane Y. Yu and Peter H. J. Chong, "a survey of clustering schemes for mobile ad hoc networks", IEEE Communications Surveys & Tutorials & First Quarter 2005 [2] Gerla M and Tsai J T C. Multicluster, Mobile, Multimedia Radio Network [J]. Wireless Networks, 1995, 1(3):255 265 [3] Raghupathy S, Prasun S, Vaduvur B. CEDAR: "a core-extraction distributed Ad Hoc routing algorithm". IEEE Journal on Selected Areas in Communication, 1999,17(8):78 89 [4] Bruce McDonald A, Taieb F. Znati. A mobile-based framework for adaptive clustering in wireless ad hoc networks [J]. IEEE Journal on selected areas in communications, 1999,17(8):1466 1487 [5] Ting-chao hou, Tzu-Jane Tsai. An access-based clustering protocols for multihop wireless ad hoc networks. IEEE journal on selected areas in communications,2001,19(7):1201 1210 Wireless Ad hoc network – Lecture 9 [6] Kaixin Xu, Xiaoyan Hong. "an ad hoc network with mobile backbones." In proceedings of IEEE international Conference on Communications, New York, NY, April 2002 [7] Izhak Rubin, Patrick Vincent. Topological Synthesis of Mobile Backbone Networks for Managing Ad Hoc Wireless networks.MMNS 2001:215 221 Wireless Ad hoc network – Lecture 9 Please point out the merits and drawbacks of the cluster structure compared with the flat structure exclusively based on proactive or reactive routing schemes.
Please list the six clustering schemes introduced in class, and give out their main features, At least one example should be given in each scheme. Wireless Ad hoc network – Lecture 9

Source: http://itec.hust.edu.cn/~liuwei/2008/2008spring-adhoc/courseware/lecture9.pdf