Resource Allocation and Parallel Routing in Sensor Networks

Lecture Note 11: Application II Resource Allocation and Parallel Routing on Sensor Networks

Distributed Resource Management and Parallel Routing for Data Acquisition in Heterogeneous Sensor Networks W. Chen, H. Miao, S. Z. Sabatto, H. A. Adas, K. Suzan Dr Wei Chen, Professor College of Engineering, Technology and Computer Science Center of Excellence for Battlefield Sensor Fusion Tennessee State University International Conference on Sensor Networks and Application, 2009 SNA 09 -1

Presentation Outline Introduction: Sensor network, Fusion, Resource Allocation Problem Statement Review of Centralized & DecentralizedMarket-based Approach for Resource Allocation Proposed Hierarchical Market Approach for Resource Allocation Parallel Routing in Heterogeneous Sensor Networks Implementation and Experiment Results Future Work SNA 09 -2

Introduction Sensor Network & Sensor Fusion Fusion missions: Target tracks, target identification, environment monitoring Upper-level fusion Base Station Ask for data/information Return back sensed/fused data Lower-level fusion sink Sensor Network SNA 09 -3

Problem Statement Given a task or tasks, how to assign sensors and network resources to fulfill the task/tasks with the goal of less delay, high QoS, and long network lifetime? For example, a task of mobile target tracking can be fulfilled by a sequence of node actions: sampling, listening, transmitting, aggregation, sleeping, and each action uses some resources. What action each node should take at each timeslot to fulfill the task that best matches the above goal? SNA 09 -4

Problem Statement Resource Allocation How to assign the resources for achieving the requested data with smallest delay while keeping the network alive as long as possible? SNA 09 -5

Review of Market-Based Resource Allocation Centralized Resource Allocation (CRA) (Dr. T. Mullen and others, Penn State Univ.) Using an auction mechanism for a single-platform or single-hop sensor network A winner has to be decided from resource bids during each round of scheduling according to the current status of all resources and requirements of given tasks. Base Station (Clients, Consumers) Central Sensor manager Computation intensive Single-platform or one-hop Sensor Network Not suitable to a multi-hop sensor network, where communication cost of relaying data are the dominant cost. SNA 09 -6

Review of Market-Based Resource Allocation Decentralized Resource Allocation (DRA) (G. Mainland & others, Harvard Univ.) At each timeslot, the IRM at each node locally selects an action that can maximize the utility function. = Base Station (Clients, Consumers) Infrequently central control ( ) ( ) if the action available is a a price a ( ) u a 0 otherwise ( is ) the estimation of probabilit y of receiving payment a a IRM Tuning node behavior: when action is successful, the utility function receives a reward. Nodes can determine locally which actions were successful . Central control: adjusting the price of resource infrequently IRM IRM IRM IRM IRM IRM Sensor Network No control points, hardly achieving optimal resource allocation Overlap on sensing, computation, and networking Individual Resource Manager SNA 09 -7

Proposed Approach- Framework Underlying Network: Most sensor networks nowadays are built with a hierarchical structure by clustering that introduce efficient sensing, computing and networking, and long network lifetime. Hierarchical Resource Allocation (HRA) in Cluster-Based Sensor Networks Local Resource Manager (LRM) at cluster-head nodes is local centralized Individual Resource Manager (IRM) at cluster-member nodes is decentralized. Simple central control by adjusting the price of resource infrequently Using the routing protocols and reconfiguration functions of the underlying cluster-based sensor network Base Station (Clients, Consumers) Infrequently central control Cluster head Cluster LRM IRM IRM LRM Goal: (1)providing promise solution of resource allocation for given tasks with less delay and high QoS; and (2)extending network lifetime LRM IRM IRM Sensor Network SNA 09 -9

Proposed Approach Detail Design Autonomous Scheduling 1. Rather than static scheduling, individual nodes tune their schedules over time 2. Cluster-heads do local optimization in their clusters 3. Nodes avoid wasting energy by using a payment-possibility threshold. 4. Using the feedback to tune node behavior: nodes receive rewards when they take useful actions 5. Reinforcement learning to select best actions Action model at nodes: 1. Nodes select an action among a set of actions at each timeslot 2. Each action has an associated energy cost 3. When an action is successful, the node earns a reward Examples of actions: Sample a sensor, Listen for incoming radio messages, Transmit a radio message, Aggregate multiple sensor readings into a single value 4. Each node attempts to maximize its reward 5. Taking an action may or may not produce a good of value to the sensor network. 6. The nodes can determine locally whether a given action deserves a payment. SNA 09 -11

Proposed Approach Design Details Algorithm of the IRM at a node r for each timeslot (scheduling cycle) do (1) with 1- probabilityselect an action a from the available action set which has largest utility value; (2) with probability randomly select an action a from the action set //exploring action space to avoid falling to local minima// (3) if (a) < payment-possibility threshold then node r goes to sleep //saving energy// else begin node r takes action a; if action a receives a payment then (a) = +(1- ) (a) //estimated probability of success gets larger // else (a) =(1- ) (a); //estimated probability of success gets smaller // end; (4) if node r runs out of the energy then call the network reconfiguration functions; G. Mainland s algorithm:An energy budget is used for each fixed period. Nodes take the actions that can maximize the utility function even the profit is very small when he budget allowed. ( ) ( ) if the action available is a a price a Utility function = ( ) u a SNA 09 -12 0 otherwise

Proposed Approach Design Details Algorithm of the LRM at a cluster-head for each timeslot (scheduling cycle) do begin (1) collect status of each member node in the cluster; (2)determine the optimal resource allocation according to the current status in the cluster and the given tasks; (3) inform the decision to the cluster member nodes; (4) if the head runs out of the energy then call the network reconfiguration functions; end; Price Selection and Adjustment at the Central Controller Prices are propagated to sensor nodes from the GRM through data dissemination algorithm. The client can adjust prices to affect coarse changes in system activity. Routing Protocols Broadcast protocol and data gathering protocol for the underlying cluster-based sensor network are used. Reconfigurable Function When a node runs out of battery, the network will be self-reconfigured. SNA 09 -13

Implementation Application: Tracking Mobile Targets Field: 105m 105m Nodes: 800 MICA2/Crossbow motes Resource: (1) Radio: member 15 m, head 30 m; (2) Magnet sensor: sensing range 11m; Buffer: 2 buffers (2256 byte) with totally 14 packages Sample reading: 29 byte (one buffer can save 17 samples) Moving target: one or two with speed 1.5 m/s or 3 m/s moving on random straight routes Packet size: 35 byte (payload 29 byte with header 6 byte) Data rate: 38.4 kbps Timeslot for an action: 0.25 second Initial energy at each node: e = 3.88 J (energy in an Nickel Cadmium AA battery = 4320 J) MAC protocol: CAMA/CA Local optimization at LRM: cluster-head select the best radio messages (most accurate message) when it receives multiple overlap messages from its member nodes Routing protocols: data dissemination broadcast protocol by using the backbone tree, message collection data gathering protocol which relays data back to the base station from sensor nodes by using the backbone tree from children to the parent Energy consumption for actions at each time slot Action 1: Sending, 2.33 mJ, Action 2: Listening, 6.56 mJ, Action 3: Sampling, 84.1 uJ Action 4: Aggregation, 84.1 mJ, (Action 5): sleeping, 12 uJ SNA 09 -14

Experimental Results Cluster-based Sensor Networks sink SNA 09 -16

Experimental Results Flat Sensor Network sink SNA 09 -15

Experimental Results Latency (one mobile target) In 20 seconds, DRA received 77 messages, HRA received 119 messages DRA (Without Local Optimization) HRA (With Local Optimization) Test field Test field Latency of Messages (One Target, NOPT) Latency of Messages (One Target, OPT) 2; 1% 11; 2% 16; 3% 9; 7% 24; 4% 26; 5% 46; 39% 0 - 5 sec 0 - 5 sec 19; 16% 5 - 10 sec 5 - 10 sec 10 - 15 sec 10 - 15 sec 15 - 20 sec 15 - 20 sec 458; 86% >20 sec >20 sec SNA 09 -17 45; 37%

Experimental Results After tracking a mobile target 200 seconds SNA 09 -18

Experimental Results Observation: change the price of sending only may not work well. SNA 09 -19

Parallel Routing for Heterogeneous Sensor Networks Recently deployed sensor networks are increasingly following heterogeneous designs. For example, a sensor network can include large number of small MICA sensors with a few of more powerful Garcia micro robotic nodes. In order to solve the performance bottleneck for data acquisition we consider a parallel routing architecture induced from the high- end nodes. SNA 09 -20

Formation of Parallel Routing Architecture Heterogeneous Sensor Network: Suppose there are k high-end nodes and n L-nodes in the heterogeneous sensor network, where k << n. Formation of the Parallel Routing Architecture with k H-nodes (PRA(k)) 1. For each H-node u,u broadcasts its ID at different timeslot. 2. For each L-node v, if v receives the IDs from at least one H-node, it assigns itself to the closest H-node. If vdoesn t receive the ID from any H- node, it assigns itself to a group called as temp. 3. Each group forms a cluster-based routing tree structure with the H-node as its root (for group temp, the root can be any low-cost node) by using any existing algorithms. 4. Merge temp to another group. 5. H-nodes (the roots of all groups) form a tree structure with the sink as the root. Each group forwards data to the H- node using a cluster-based routing tree; the H-nodes forward data back to the sink using the backbone tree SNA 09 -21

Experimental Results Parallel routing architecture induced by 4 high-end nodes (PRA(4)) SNA 09 -22

Experimental Results Tracking a mobile target by HRA scheme (left), and by PRA(4) scheme (right), where white, yellow, dark blue, red, green, and orange dots are the locations that the vehicle is detected and reported back to the sink in 5, 10, 15, 20, 30 and 60 seconds, respectively. SNA 09 -23

Experimental Results Latency and Network Throughput Data Quality 200 80% 180 Number of received data 70% 160 number of received data 60% 140 50% 120 DRA DRA 100 40% HRA HRA 80 30% PRA(4) 60 PRA(4) 20% PRA(8) 40 PRA(8) 10% 20 0% 0 0m-3m 3m - 6m 6m - 9m 9m - 11m 5 10 15 20 25 30 35 40 45 50 55 60 > 60 Seconds Distance of the sensed target and the sensing sensor node SNA 09 -24

Experimental Results Propotion of Actions Rate of Dead nodes 600000 7.00% 5.84% 6.00% 500000 5.09% number of actions 5.00% 400000 DRA 4.00% 300000 HRA 3.00% PRA(4) 200000 2.00% 1.34% 1.30% PRA(8) 100000 1.00% 0 0.00% Send Listen Sample Aggregate Sleep DRA HRA PRA(4) PRA(8) SNA 09 -25

Exercises: Explain why hierarchical resource allocation (HRA) scheme can improve latency, QoS and network lifetime. Explain how high-end nodes in heterogeneous sensor network induces parallel routing. SNA 09 -26