Thesis Proposal – for Master of Software Engineering



AMPL: Active Multi-Power Level Cluster Formation

by

Jeffrey D. Rupp

B.S.C.S University of Colorado, Colorado Springs 2000

A thesis submitted to the Graduate Faculty of the

University of Colorado at Colorado Springs

in partial fulfillment of the

requirements for the degree of

Master of Science

Department of Computer Science

2006

ii

This thesis for the Master of Science degree by

Jeffrey D Rupp

has been approved for the

Department of Computer Science

by

_________________________________

Dr. Edward Chow

_________________________________

Dr. Sudhanshu K. Semwal

_________________________________

Dr. Xiaobo Zhou

_______________________

Date

iii

Abstract

Jeffrey D Rupp

AMPL: Active Multi-Power Level Cluster Formation

Thesis directed by Professor Edward Chow.

Active Multi-Power Level Cluster Formation (AMPL) uses multiple transmit power levels to broadcast an initial hello message to establish the ranges at which nodes can detect each other. Every node executes this hello protocol, so that all nodes have a mapping of all the nodes they can hear. This allows for a pro-active cluster formation process, and facilitates the transfer of cluster head duties. This algorithm does entail more messages initially, but during the life of the network the traffic is predominantly for the data flow. Traffic and thus power is not expended on re-forming clusters until it becomes necessary. To confirm the theory behind the proposed clustering algorithm I have created a simulator, which is focused on the power consumption aspect of wireless sensor networks. The simulation results show that the performance of AMPL, as indicated by total data bits transmitted before battery power ran out, is inferior to that of LEACH[16], however the data provided by the multiple power level hello protocol allows for optimizations that should allow AMPL to exceed the performance of LEACH[16].

iv

Contents

Abstract iii

Chapter 1 Introduction 1

1.1 Document Organization 1

1.2 Background Information 1

1.2.1 Assumptions on signal propagation and power calculation. 2

1.3 Related Work 4

1.3.1 Cluster formation Algorithms 4

1.3.2 Network Simulators 5

Chapter 2 Active Multi-Power Level Cluster Formation (AMPL) Description 4

2.1 Cluster Formation 8

2.1.1 Pseudo-Code 10

2.2 Cluster Head Transition 12

2.3 Optimizations 13

2.4 Performance Analysis 13

Chapter 3 Simulator Architecture 28

3.1 Scheduler 29

3.2 Plug-in classes 31

3.3 Settable parameters 36

3.4 Automatically varied parameters 39

3.5 Simulator Main GUI 41

3.6 Debug Output 48

Chapter 4 Interesting Problems Encountered 51

Chapter 5 Future Work 53

Chapter 6 Conclusions 49

6.1 Active Multi-Power Level Cluster Formation 49

6.2 Simulator 49

Chapter 7 References 54

v

List of Figures

Figure 1: Hello levels 6

Figure 2: Cluster members 6

Figure 3: Normal communication 7

Figure 4 Tired Cluster Head 13

Figure 5. Total simulation tics 19

Figure 6. Total Bits 20

Figure 7. Average Power Per Packet 21

Figure 8 Transmit Levels 22

Figure 9. Re-hello Percent 23

Figure 10. Nodes Per Cluster 24

Figure 11. Ramp Area 25

Figure 12. Simulator Parameters 31

Figure 13. Ramped values 39

Figure 14. Main Simulator GUI 41

Figure 15. File Menu 41

Figure 16 Setup Menu 42

Figure 17 Graphs Menu 42

Figure 18 Help Menu 42

Figure 19 About Dialog 42

Figure 20 Debug Dialog 43

Figure 21 Color Key Dialog 44

Figure 22 Node Representation 45

Figure 23 Cluster Head Node 45

Figure 24 Cluster Indication 45

Figure 25 Power Levels 46

Figure 26 Node Information 46

Figure 27 Graph Display 47

Introduction

1 Document Organization

The Introduction gives some background information and addresses some related work for both AMPL and the network simulator. The Algorithm Description section goes into detail on how AMPL works and the experimental findings provided by the simulator. The Simulator Architecture section describes how the simulator is constructed, providing details on how it is implemented and how to expand the simulator via the plug-in interface. The Interesting Problems Encountered section describes some of the more interesting difficulties encountered and discoveries made during the creation of the simulator and testing of the various algorithms. The Future Work section lists several areas that merit further exploration.

2 Background Information

Small inexpensive wireless sensors are quickly finding broad application in today’s market place [17]. Wireless sensors are being used by commercial and military customers to monitor a wide variety of environmental parameters. As the use of these types of sensors grows, the demand for the sensors to last as long as possible becomes more and more market driven. Cluster formation is a promising approach to help meet this goal. Cluster formation allows several nodes to consolidate their data to a single cluster head, the cluster then head relays the aggregated data to the sink node. In a system utilizing clustering the child nodes are able to transmit at a lower power level to their head node. Only the head node must transmit at a higher power level to relay the data to the sink node. To allow us to test various algorithms, it is useful to have a simulator geared to measure the desired requirements.

1 Assumptions on signal propagation and power calculation.

The power consumption applied in the simulator is based only on transmission, no power is consumed for reception nor for mundane OS/scheduling chores. This is acceptable for comparison between algorithms since the same behavior is applied to all the algorithms tested. The simulator allows future expansion to incorporate power consumption for different reasons by either modifying the classes that implement the NodeIF, or creating new classes that implement the NodeIF interface. The path loss during transmission is assumed to be un-impeded free space, given by the equation:

pathloss in dB = 20*log10((1*pi*dist)/wavelength)

Where wavelength is 300/(frequency in MHz)

The dist and wavelength are in the same units

The power consumed to transmit a message is dependent on the data rate, and is given by the following formula:

WattHours = ((10.0 ^ (powerLeveldBm / 10)) / 1000) * ((TransmitedBitCount / dataRateBps) / s_SECONDS_PER_HOUR)

The power levels available to a node are based on the Crossbow Motes MPR410CB [18]

• Pout = -20 dBm I = 5.3 mA

• Pout = -5 dBm I = 8.9 mA

• Pout = 0 dBm I = 10.4 mA

• Pout = 5 dBm I = 14.8 mA

• Pout = 10 dBm I = 26.7 mA

The range claimed by crossbow in free space for these motes is 1000 feet. Reversing the free space propagation formula we can arrive an acceptable path loss of 70 dB, or a minimum receive signal strength of -60 dBm based on transmitting at the maximum power of 10 dBm[18].

The total power consumed by a transmission is based on the total bits transmitted. The message format used in the simulation has 30 bytes of header information consisting of:

Sequence number (4 bytes)

Acknowledge number(4 bytes)

Source Node (4 bytes)

Destination Node (4 bytes)

Last Node (4 bytes)

Next Node (4 bytes)

Message Number (4 bytes)

Message Type (1 byte)

Message Length (1 byte)

The power it takes to transmit a message containing no data, just the header, at 1000 bits per second is then:

WattHours = ((10^(10/10))/1000milliWatts/Watt *((30bytes*8bits/byte) / 1000bits/second)/ 3600 seconds/hour

WattHours = 6.67e-7 WattHours

The average power of a AA battery is approximately 4.5 WattHours, a watch battery has about 0.0028 WattHours [19].

3 Related Work

1 Cluster formation Algorithms

There are many cluster forming algorithms in existence already, such as: TEEN (Threshold sensitive Energy Efficient sensor Network protocol)[9] for reactive networks. Fault Tolerant Clustering of Wireless Sensor Networks [1] which addresses fail-over in networks. Scaleable Self-Assembly for Ad Hoc Wireless Sensor Networks [2] which describes a link level Ad-hoc network scheme. A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks [6] which uses geometry, and thus knowledge of the nodes location, to for an efficient topology. Low Energy Adaptive Cluster Hierarchy with Deterministic Cluster-Head Selection [7] which modifies LEACH [16] to add determinism to the cluster head selection. Energy Efficiency of Many-to-One Communications in Wireless Networks [9] which attempts to determine the ideal minimum energy required to gather data for both flat and clustered networks. Optimal Energy Aware Clustering in Sensor Networks [10] which forms balanced clusters based on distance and node distribution. FLOC: Fast Local Clustering Service for Wireless Sensor Networks [11] which forms clusters based on distance restrictions where all nodes within a set distance become part of a cluster with no nodes farther than that distance. There have been many derivative efforts to improve a given algorithm for a specific feature [12], as well as many other efforts to produce an optimal clustering algorithm.

In this paper I compare AMPL with LEACH [16], a well known rounds based algorithm, HEED [1], a rounds based algorithm that does more work on determining the next cluster head, and a system that uses no cluster heads, instead every node must relay every message to ensure all messages reach the sink node. The LEACH [16] algorithm uses a rounds approach where the cluster head duties are transferred to a new node at predetermined intervals. LEACH [16] uses a formula that ensures every node serves a turn as cluster head over the course of the rounds. LEACH [16] uses the received power level to determine the transmit level for the child nodes, thus the child nodes do not transmit at maximum power. The HEED [1] algorithm also uses a rounds approach where the head duties are transferred at a predetermined periodic interval. HEED [1] uses more logic than LEACH [16] in selecting the next cluster head. In the HEED [1] algorithm the remaining power in a node is factored into the choice for cluster head. The non-cluster forming algorithm is included to provide a worst case example to compare the other algorithms to.

2 Network Simulators

NS2 () provides a simulation of network traffic and topology, but not the aspects of particular interest to wireless networks, power consumption and cluster formation. JSim () is similar to NS2 in that it concentrates more on the topology, not on the constraining factors of a wireless network. NAB () is also a topology oriented simulator, concentrating on the flow of data rather than the power needed to achieve this flow.

Active Multi-Power Level Cluster Formation (AMPL) Description

In an effort to create clusters in a more planned fashion, a simulator was created to test an algorithm that uses a multiple level neighbor finding protocol to determine cluster heads. This algorithm attempts to make more informed decisions on which nodes to cluster together based on the levels at which the nodes can hear each other. By doing so the intent is that the clusters do not have to reform regularly, as in the rounds approaches used by both LEACH [16] and HEED [1]. Also with the many level neighbor finding approach nodes are more certain of the power levels at which they need to communicate. The nodes will communicate with their cluster head at the lowest level at which they heard the cluster head node, then the cluster head aggregates the data and relays it to the sink node at a higher power level. This allows the majority of the nodes to pass their data on to their cluster head at a low power level. The cluster head duties are reassigned by the current cluster head when it reaches a level of 40% of the power it had upon assumption of cluster head duties. The current cluster head sends a proactive message to its child nodes to determine which currently has the most power, then passes the cluster head duties to that child.

AMPL uses a configurable number of broadcast levels to determine the range at which neighboring nodes can be heard. At a signal from the sink node, after the nodes have been deployed, each node broadcasts a message at each of the levels. The nodes that hear the broadcast record the source node and the lowest level at which it was heard. The initial cluster formation takes more time than with the other algorithms due to the multiple levels. This initial formation cost is balanced out by the later dynamic cluster head re-assignment logic. Once all the nodes have finished their broadcasts, the sink node sends a message telling them to begin to form clusters. The sink node begins with the transmit power level at the lowest level and works its way up until a node responds that it has heard. The node that heard the sink node’s message will begin forming clusters, by telling all of the nodes in its neighbor list below a configurable power threshold that it wants to become their cluster head. The cluster formation limits the number of nodes per cluster to a configurable quantity. The nodes that have been told to join a cluster have the option of rejecting the offer if they are cluster heads themselves or are members of anther cluster. To reject an offer of a cluster head a node sends a message to the offering node stating its rejection. Once a node has clustered all the neighboring nodes it has heard below a configurable power threshold, that node tells the neighboring nodes it heard at higher levels to form their own clusters. This process cascades until all nodes are either cluster heads, or members of a cluster.

Figure 1: Hello levels shows a node with its Hello power levels drawn as dotted circles. The pink square in the upper left corner is the sink node.

Figure 2: Cluster members shows a cluster formed based on the Hello levels. The circles around the nodes indicate cluster membership, the blue square beside a node indicates that it is the cluster head.

Once the initial cluster heads have been established the network goes into the data gathering mode. In this mode the nodes periodically transmit the sensor data they have gathered to their cluster head, at the lowest possible power level as determined by the table the node has containing the initial neighbor finding node to level mapping. The cluster head then aggregates the data to transmit it to the sink node periodically. The transmit to the sink node is done at the same interval as the data gathering, hence the cluster head relays the aggregated data after it has sampled its data. The transmit to the sink node is accomplished by transmitting at maximum power since this algorithm does not establish a path to the sink node. Also due to not having a path to the sink node, any cluster head that hears a message destined for the sink node must relay that message. This relay approach causes the cluster heads to consume power much faster than their child nodes. When the cluster head senses that it is at a power level that is 40% of the power level it had when it assumed the cluster head duties it sends a message to its child nodes to determine which has the most power. The child nodes all respond to their parent node with their current remaining power. The current cluster head then chooses from its children the node with the most power and transfers the cluster head duties to that child. Part of the transfer process is to send a list of the child nodes to the new cluster head. The now former cluster head also informs the other children of the new cluster head so that the children will transmit their sensor data to the new cluster head.

Figure 3: Normal communication shows the normal communication phase. The dark blue lines are from children to their cluster heads, the light blue lines are from the Cluster heads to the sink node. The Cluster head messages all get relayed by the other cluster heads.

This algorithm places more intelligence in the nodes themselves, since they are keeping a list of neighbors and keeping track of their own power levels. This complexity provides a more precise control over the clusters and the transference of the cluster head duties.

1 Cluster Formation

The cluster formation process is initiated by a message from the sink node. The sink node begins by transmitting at its lowest power level and incrementally increases the transmit power level until a node responds that it heard the sink node’s message. This first node then begins the hello protocol. The nodes have a pre-determined number of levels at which they will transmit the hello message. The hello message consists of a single byte indicating the level at which the message was transmitted. This level indicator allows the nodes that hear the message to catalog the exact level at which the transmitting node was heard. The level indicator was chosen over the receiving nodes detected power level to provide a more accurate indication of the power, not dependent on the reception node’s characteristics. The transmitting node transmits one broadcast message at each predetermined level.

Each node that receives the hello message catalogs the node number that sent it and the level at which it was transmitted. Receiving nodes will mark themselves as needing to perform the hello protocol after they receive the transmitting node’s highest level transmission. This delays the next round of hello messages until after the first node completes. The subsequent nodes then rely on the transmission control protocol to avoid collisions. Eventually all nodes will execute the hello protocol, this provides all nodes with a table of their neighbor nodes and the power levels at which they were heard.

When the sink node decides that sufficient time has passed for the hello protocol to finish it sends a message to initiate cluster formation. This is accomplished in the simulator by monitoring the scheduling queue. The decision that a phase is complete is made when the scheduling queue is empty for ½ second of real-time. The message to begin forming clusters is sent out at the same power level at which the initial begin-hello message was sent, so that only one node will receive it. This first node to receive the message marks itself as a cluster head. The cluster head then chooses from its table of nodes heard the nodes it heard below a threshold, limited by a predetermined cluster size. The threshold at which a node is chosen as a child versus told to form its own cluster must be low enough that the resulting cluster will leave some nodes at higher levels in the table. This ensures that the broadcast messages will reach other cluster heads. If the child threshold is too high then the clusters will cover too large an area and the broadcast messages will not be heard by other cluster heads to be passed along to the sink node. The cluster head then sends a message to each of the chosen children that it wishes to become their cluster head. If the child node is a cluster head itself already, or is a member of another cluster, it will send a reject message back to the requesting cluster head. Eventually sink node must decide when sufficient time has passed for clusters to form to send a begin-normal-communication message. This is accomplished by the simulator through monitoring the scheduling queue once more.

Once the nodes receive the begin-normal-communication message, they will begin gathering the data they are designed for and passing it to their cluster heads. The child nodes will transmit to their cluster head at the level at which they heard the cluster head. Periodically the cluster head will aggregate the data received from the child nodes to transmit a broadcast message that contains a flag indicating that it is intended for the sink node. Other cluster heads are required to relay the broadcast messages to ensure that the message eventually reaches the sink node. This algorithm does not attempt to determine a path to the sink node, hence all cluster heads must relay all broadcast messages.

1 Pseudo-Code

Sink node:

transmitLevel = 1

gotResponse = false

while not gotResponse && transmitLevel ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download