Slide 1Slide 2Link-Clustered Architecture [Baker+ 1981a, 1981b, Ephremides+ 1987]Slide 4ClusterheadsPrevious WorkSlide 7Slide 8Slide 9Weighted Clustering Algorithm (WCA) StepsSlide 11Slide 12Slide 13Load Balancing Factor (LBF)ConnectivitySlide 16Slide 18Slide 19Features of WCAPerformance MetricSimulation EnvironmentExperimental ResultsSlide 24Load BalancingSlide 26Performance of WCAGenetic AlgorithmsEncoding of the ChromosomeMapping WCA to GASlide 31GA StepsSlide 33Cfit Value AlgorithmSlide 35Slide 36Slide 37Slide 38Slide 39Slide 40Load Balancing with WCASlide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58LEACH [Heinzelman+ 2000, 2002]Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Clustering in Ad hoc and Sensor Networks–The data collected by each sensor is communicated through the The data collected by each sensor is communicated through the network to a single processing center that uses the datanetwork to a single processing center that uses the data–ClusteringClustering groups nodes into groups such that each node communicate groups nodes into groups such that each node communicate information only to clusterheads and then the clusterheads information only to clusterheads and then the clusterheads communicate the aggregated information to the processing center, communicate the aggregated information to the processing center, saving energy and bandwidthsaving energy and bandwidth–The cost of transmitting a bit is higher than a computation; therefore, it The cost of transmitting a bit is higher than a computation; therefore, it may be beneficial to organize the sensors into clustersmay be beneficial to organize the sensors into clusters–Cluster-based control structures provides more efficient use of Cluster-based control structures provides more efficient use of resources for large dynamic networksresources for large dynamic networksClustering can be used forClustering can be used for–Transmission management Transmission management –Backbone formationBackbone formation–Routing Efficiency Routing Efficiency Why Clustering?Link-Clustered Architecture[Baker+ 1981a, 1981b, Ephremides+ 1987]–Reduces interference in multiple-access broadcast environmentReduces interference in multiple-access broadcast environment–Distinct clusters are formed to schedule transmissions in a contention-Distinct clusters are formed to schedule transmissions in a contention-free wayfree way–Each cluster has a clusterhead, one or more gateways and zero or Each cluster has a clusterhead, one or more gateways and zero or more ordinary nodesmore ordinary nodes–Clusterhead schedules transmission and allocates resources within its Clusterhead schedules transmission and allocates resources within its clustercluster–Gateways connect adjacent clustersGateways connect adjacent clustersTo establish link-clustered control structureTo establish link-clustered control structure1.1.Discover neighborsDiscover neighbors2.2.Select clusterhead to form clustersSelect clusterhead to form clusters3.3.Decide on gateways between clustersDecide on gateways between clustersClusterheadGatewayOrdinary nodeClusterLink-Clustered Architecture[Baker+ 1981a, 1981b, Ephremides+ 1987]Clusterheads–Resemble base stations in cellular networks, but dynamicResemble base stations in cellular networks, but dynamic–Responsible for resource allocationResponsible for resource allocation–Maintains network topologyMaintains network topology–Acts as routers – forwards packets from one node to anotherActs as routers – forwards packets from one node to another–Aware of its cluster membersAware of its cluster members–Aware of its one-hop neighboring clusterheadsAware of its one-hop neighboring clusterheadsSince clusterheads decide network topology, Since clusterheads decide network topology, electionelectionof clusterheads optimally is criticalof clusterheads optimally is criticalPrevious WorkHighest-Degree Heuristic [Gerla+ 1995, Parekh 1994]Computes the degree of a node based on the distance Computes the degree of a node based on the distance (transmission range) between the node and the other nodes(transmission range) between the node and the other nodesThe node with the maximum number of neighbors (maximum The node with the maximum number of neighbors (maximum degree) is chosen to be a clusterhead and any tie is broken degree) is chosen to be a clusterhead and any tie is broken by the node idsby the node idsDrawbacks:A clusterhead cannot handle a large number of nodes due to A clusterhead cannot handle a large number of nodes due to resource limitationsresource limitationsLoad handling capacity of the clusterhead puts an upper Load handling capacity of the clusterhead puts an upper bound on the node-degreebound on the node-degreeThe throughput of the system drops as the number of nodes The throughput of the system drops as the number of nodes in cluster increasesin cluster increasesLowest-ID Heuristic [Baker+ 1981a-b, Ephremides+ 1987]The node with the minimum node-id is chosen to be a clusterheadThe node with the minimum node-id is chosen to be a clusterheadA node is called a A node is called a gateway gateway if it lies within the transmission range of if it lies within the transmission range of two or more clusterstwo or more clusters Distributed gateway Distributed gateway is a pair of nodes that reside within different is a pair of nodes that reside within different clusters, but they are within the transmission range of each otherclusters, but they are within the transmission range of each otherDrawbacks:Since it is biased towards nodes with smaller node-ids, leading to Since it is biased towards nodes with smaller node-ids, leading to battery drainage battery drainage It does not attempt balance the load for across all the nodesIt does not attempt balance the load for across all the nodesPrevious WorkPrevious WorkNode-Weight Heuristic [Basagni 1999a, 1999b]Node-weightsNode-weights are assigned to nodes based on the suitability are assigned to nodes based on the suitability of a node being a clusterheadof a node being a clusterheadThe node is chosen to be a clusterhead if its node-weight is The node is chosen to be a clusterhead if its node-weight is higher than any of its neighbor’s node-weights and any tie is
View Full Document
Unlocking...