Improving Throughput of Video Streaming in Wireless Sensor Networks Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classi ed information. Shuang Li Certi cate of Approval: Xiao Qin Assistant Professor Computer Science and Software Engineering Alvin S. Lim, Chair Associate Professor Computer Science and Software Engineering Wei-Shinn Ku Assistant Professor Computer Science and Software Engineering George T. Flowers Interim Dean Graduate School Improving Throughput of Video Streaming in Wireless Sensor Networks Shuang Li A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Ful llment of the Requirements for the Degree of Master of Science Auburn, Alabama August 9, 2008 Improving Throughput of Video Streaming in Wireless Sensor Networks Shuang Li Permission is granted to Auburn University to make copies of this thesis at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Shuang Li, daughter of Fu?an and Derong Li, was born October 21, 1983, in Chongqing, China. She earned her Bachelor?s degree in Computer Science from Wuhan University of Technology, Hubei, China in 2005. iv Thesis Abstract Improving Throughput of Video Streaming in Wireless Sensor Networks Shuang Li Master of Science, August 9, 2008 (B.S., Wuhan University of Technology, China, 2005) 115 Typed Pages Directed by Alvin S. Lim Wireless sensor networks are originally distributed event-based systems that di er from traditional communication networks in several ways. These networks typically have nodes with severe energy constraints, variable quality links, low data-rate and many-to-one event- to-sink ows. Recently, Wireless Multimedia Sensor Networks (WMSNs) have been devel- oped with the availability of low-cost cameras, microphones, and other sensors producing multimedia data. The applications, accordingly, are extended to video surveillance and noti cation, video and computer assistance in living, etc. The stringent requirements of real-time multimedia applications include end-to-end delay, bandwidth and loss during data transmission. Communication algorithms for WMSN must therefore be specially designed to operate e ciently under these constraints. Directed di usion is a data-centric protocol designed for wireless sensor networks. However, it is not e cient in more challenging do- mains, such as video sensor networks, because of inability to satisfy the throughput and delay requirements of multimedia data. Instead, we propose EDGE, a greedy algorithm based on directed di usion that reinforces routes with high link quality and low latency, v thus maximizing throughput and minimizing delay. ETX (Expected Transmission Count) is used as the metric for measuring link quality. And we present an improved method for computing aggregate ETX for a path that increases end-to-end throughput. Multiple-path is one of the ways how QoS routing issues are dealt with in wired environment. Besides, some existing ad hoc routing algorithms also provide multi-path routing. Directed di u- sion has been commonly used for wireless sensor networks because of its energy e ciency and scalability. However, the basic protocol only routes packets through a single path, which barely meets the throughput requirement of multimedia data. Instead, we propose a multi-path algorithm based on directed di usion that reinforces multiple routes with high link quality and low latency. In directed di usion, many routing messages are propagated unnecessarily and may cause di erent interference characteristics during route discovery phase and in the actual application data transmission phase. We propose a routing proto- col that uses ID-free epidemic ooding to limit interference in conjunction with metrics for increasing throughput and reducing delay. vi Acknowledgments I would like to express my appreciation to Dr. Lim for the guidance he has provided throughout my study at Auburn. I would also like to express my gratitude to the advisory committee members, Dr. Xiao Qin and Dr. Wei-Shinn Ku. I would also like to thank several fellow students including Raghukisore Neelisetti and Santosh Kulkarni for their signi cant contributions to this research. Above all, I would like to thank my parents who helped me come to U.S. and pursue graduate study at Auburn. vii Style manual or journal used Journal of Approximation Theory (together with the style known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speci cally LATEX) together with the departmental style- le aums.sty. viii Table of Contents List of Figures xi 1 Introduction 1 2 Related Work 6 2.1 Hardware Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 On-going Video Sensor Network Research . . . . . . . . . . . . . . . . . . . 7 2.3 QoS issues in WMSN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Routing Metrics in Wireless Sensor Networks . . . . . . . . . . . . . . . . . 8 2.5 Interference-aware Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.6 Short-comings in ETX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.7 Theoretical Analysis of Throughput-Delay Tradeo . . . . . . . . . . . . . . 11 2.8 Multi-path Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.9 Multistream Video Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.10 Message Redundancy in Routing Protocols . . . . . . . . . . . . . . . . . . 12 3 Motivations and Applications 14 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.1 Multimedia Surveillance . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.2 Data-centric Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.3 Tra c Conditions and Collision Avoidance . . . . . . . . . . . . . . 16 4 Problem Statement 17 4.1 Single-path metric Costp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1.1 Assumptions and Goals . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1.2 De nitions, Notations and Formulae . . . . . . . . . . . . . . . . . . 18 4.1.3 Computing Path Metric . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Multi-path Protocol DCHT . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3 Interference Limiting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.1 Overview of Directed Di usion and Its Variants . . . . . . . . . . . . 26 4.3.2 Route Selection Problems . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Protocol Design 29 5.1 EDGE Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1.1 Optimum Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ix 5.1.2 EDGE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.3 Look-ahead Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 DCHT Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.1 Route discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2.2 Parameter settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3 Epidemic Algorithm in Di usion . . . . . . . . . . . . . . . . . . . . . . . . 44 5.3.1 Epidemic Interest Flooding . . . . . . . . . . . . . . . . . . . . . . . 45 5.3.2 Epidemic Exploratory Data Propagation . . . . . . . . . . . . . . . . 46 6 Implementation 49 6.1 EDGE implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.1.1 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.1.2 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2 Multi-path Protocol Implementation . . . . . . . . . . . . . . . . . . . . . . 54 6.3 Implementation of Epidemic Interest Flooding . . . . . . . . . . . . . . . . 56 7 Performance Evaluation 58 7.1 EDGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 DCHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.2.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.2.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7.3 Epidemic ooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8 Conclusions and Future Work 91 Bibliography 94 x List of Figures 2.1 Scenario for MD source coding with two channels and three receivers [1] . . 12 4.1 Transmission range and interference range for a chain of nodes. The solid line circle is a nodes transmission range while the dotted line circle shows the interference range. Nodes within 3 hops interfere with each other. . . . . . . 20 4.2 Pipelining mechanism of data transmission in sensor networks with intra- ow interference taken into account. . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Transmission and interference ranges of Node 3. The solid circle is the trans- mission range and the dashed circle is the interference range. R = 2r. We assume homogeneous nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 A simple topology of triangular tessellation with 19 nodes. Each node has the same distance to its nearest neighbors. . . . . . . . . . . . . . . . . . . . 28 5.1 Illustration of the centralized algorithm. In each tuple, the rst element is the ETX value of the link and the second element is the delay of the link which includes the packet queuing delay at the upstream node. Gradients are indicated by arrows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 The worst case routes. Every 2 nodes except the source and sink are put in a vertical line. Every node in a line has two gradients pointing to both nodes in the next line. The number of routes is O(2n2 ). If we put B nodes in each vertical line, the number becomes O(BnB). . . . . . . . . . . . . . . . . . . . 32 5.3 An example showing that Costp does not have sub-solution optimality prop- erty. The numbers denote the ETX values of those links. delay for each link is 1. Suppose = 1 and = 1. . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.4 How to avoid the node already reinforced in another path. . . . . . . . . . . 38 5.5 How to avoid loops. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.6 Unavoidable bottleneck nodes. Nodes connected by a line are able to com- municate with each other. Or else, they are out of range. . . . . . . . . . . 42 xi 5.7 Overlapping of A?s and B?s transmission ranges. . . . . . . . . . . . . . . . . 43 5.8 The relation of P(x> 1) and N. . . . . . . . . . . . . . . . . . . . . . . . . 44 5.9 Probabilistic interest dropping reduces interference level during exploratory data phase. The dotted circle is the interference range of Node 1. . . . . . . 46 5.10 Comparison of two gossip-based algorithms. The left is GOSSIP and the right is Fireworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.1 A 10-by-10 Grid Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2 Topology with equilateral triangular tessellations. There are 77 nodes in this graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.3 Topologies of triangular, grid and hexagon tessellation, from left to right. Every node has 6, 4, and 3 neighbors, respectively. . . . . . . . . . . . . . . 57 7.1 Throughput and delay comparison between EDGE and directed di usion in grid topologies. The error rate of outgoing channels follows uniform distri- bution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2 Throughput and delay comparison between EDGE and directed di usion in 10-by-10 grid with di erent delivery ratios of the lossy links. Tra c rate is 40 packets per second. = 1, = 1 in Costp. Packet size is 500 bytes. . . . 69 7.3 Throughput and delay comparison between EDGE and directed di usion in 10-by-10 grid with di erent tra c rates. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.4 Network delivery ratio comparison between EDGE and directed di usion in 10-by-10. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. 71 7.5 Jitter comparison between EDGE and directed di usion in 10-by-10 grid with di erent delivery ratios. = 1, = 1 in Costp. Tra c rate is 40 packets per second. Packet size is 500 bytes. . . . . . . . . . . . . . . . . . . . . . . . . 72 7.6 Throughput and delay comparison between 3-hop EDGE and 5-hop EDGE in 10-by-10 grid with di erent tra c rates. The error rate of outgoing channels follows uniform distribution with 0.7. = 1, beta = 1 in Costp. Packet size is 500 bytes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 xii 7.7 Throughput and delay comparison with di erent and values in Costp of EDGE in 10-by-10. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. Tra c rate is 40 packets per second. . . . . . . . . . . . . 74 7.8 Throughput of DCHT, EDGE and basic di usion with di erent network sizes. 75 7.9 Goodput of DCHT, EDGE and basic di usion with di erent network sizes. 75 7.10 End-to-end delay of DCHT, EDGE and basic di usion with di erent network sizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7.11 Number of loss packets per frame in DCHT. There are 29 packets in a large video frame. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7.12 Number of loss packets per frame in EDGE. There are 29 packets in a large video frame. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.13 Delivery ratio and goodput ratio of DCHT with di erent numbers of descrip- tions/paths. The network size is 77 nodes. . . . . . . . . . . . . . . . . . . . 77 7.14 Throughput and goodput of DCHT with di erent numbers of descrip- tions/paths. The network size is 77 nodes. . . . . . . . . . . . . . . . . . . . 78 7.15 End-to-end delay of DCHT with di erent numbers of descriptions/paths. The network size is 77 nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.16 Average energy consumption of a single node in the network of DCHT with 3 paths (descriptions), EDGE and basic di usion with di erent network sizes. 79 7.17 Average energy consumption of a single node in the network of DCHT with di erent number of paths (descriptions). The network size is 77 nodes. . . . 79 7.18 Extra routing overhead (we only consider NEG RESPONSE) of the whole network of DCHT with di erent number of paths (descriptions) in di erent network sizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.19 Throughput of triangular tessellation topology with di erent sizes. . . . . . 81 7.20 End-to-end delay of triangular tessellation topology with di erent sizes. . . 81 7.21 Percentage of zero throughput, no path built and no interest reaching source of triangular tessellation topology with 77 nodes. . . . . . . . . . . . . . . . 82 xiii 7.22 Throughput of grid topology with di erent sizes. . . . . . . . . . . . . . . . 83 7.23 End-to-end delay of grid topology with di erent sizes. . . . . . . . . . . . . 84 7.24 Throughput of hexagon tessellation with 32, 50, 72 nodes. . . . . . . . . . . 85 7.25 End-to-end delay of hexagon tessellation with 32, 50, 72 nodes. . . . . . . . 86 7.26 Throughput of random topology with 60, 80, 90, 100 nodes. . . . . . . . . . 87 7.27 End-to-end delay of random topology with 60, 80, 90, 100 nodes. . . . . . . 88 7.28 Throughput comparison of 4 topologies. . . . . . . . . . . . . . . . . . . . . 88 7.29 End-to-end delay comparison of 4 topologies. . . . . . . . . . . . . . . . . . 89 7.30 Throughput comparison of 3 topologies with full ooding. . . . . . . . . . . 89 7.31 End-to-end delay comparison of 3 topologies with full ooding. . . . . . . . 90 xiv Chapter 1 Introduction In September 1999, networked microsensors technology was heralded as one of the 21 most important technologies for the 21st century by Business Week [2]. Cheap, smart devices with sensors, connected by wireless links and deployed in large numbers, make instrumenting and controlling homes, cities, and the environment feasible [3]. Networked microsensors is a subcategory of sensor networks that use multiple distributed sensors to collect information on entities of interest. Applications of sensor networks include: military sensing, physical security, air tra c control, tra c surveillance, video surveillance, industrial and manufacturing automation, distributed robotics, environment monitoring, and building and structures monitoring [3]. Early research focused on military sensor networks. During the Cold War, the Sound Surveillance System (SOSUS), a system of acoustic sensors on the ocean bottom, was de- ployed at strategic locations to detect and track quiet Soviet submarines. Modern research on sensor networks started around 1980 with the Distributed Sensor Networks (DSN) program at the Defense Advanced Research Projects Agency (DARPA). Researchers at Carnegie Mellon University (CMU), Pittsburgh, PA, Massachusetts Institute of Technology (MIT), Cambridge, University of Massachusetts, Amherst were working on di erent sensor network testbeds. Talking about sensor network research in the 21st century, we can- not ignore the microelectromechanical system (MEMS) [4] technology, wireless networking, and inexpensive low-power processors. The recently concluded DARPA Sensor Information Technology (SensIT) program [5] pursued two key research and development thrusts. First, 1 it developed new networking techniques. The second thrust was networked information processing, i.e., how to extract useful, reliable, and timely information from the deployed sensor network. We are focusing on one of the applications, video surveillance. Recent advances of wire- less technologies, embedded systems, multimedia source coding techniques and inexpensive hardware such as CMOS cameras (e.g. Stargate board interfaced with a medium resolution camera and Acroname GARCIA [6]), microphones, etc. have fostered the development of Wireless Multimedia Sensor Networks (WMSNs), over which multimedia data streams are transmitted. Accordingly, new applications are created, such as multimedia surveillance, storage of potentially relevant activities, tra c avoidance, advanced health care delivery, and automated assistance for the elderly and family monitors [6]. They usually have a set of stringent QoS requirements, such as, end-to-end delay, bandwidth, and jitter guarantees. For example, the data rate of H.264 varies between 64 kbps and 240 Mbps depending on the level [7]. To meet them, a more e cient routing protocol needs to be designed for WSNs. Data- centric networking, such as directed di usion [8], has been commonly used for wireless sensor networks because of its energy e ciency and scalability. It enables sensor data to be disseminated from data sources to sinks with low delay. WMSNs require larger amount of real-time multimedia data to be disseminated with low latency and high delivery ratio. In transmitting multimedia data tra c, additional quality of service constraints must be satis ed. The main challenge is to develop a practical data-centric networking algorithm that can maximize throughput, minimize delay and meet other QoS constraints as much as possible in wireless sensor networking environments. 2 Multipath transport provides higher available bandwidth for a session by splitting tra c and achieving better load balancing. This technique has long been used in wired networks. Heuristics-based solutions to nd the set of paths that minimizes the cost or maximizes throughput are proposed in [9], [10]. For ad hoc networks, DSR and AODV are modi ed to support multiple paths [11][12][13] by sending back multiple REPLYs from the destination. Disjoint paths are preferred [11][12][13] since the node shared by more than one path is not able to send packets from di erent paths simultaneously. Shared nodes increase queuing delay and end-to-end delay. On the other hand, contention and interference cause packets to be dropped which leads to lower throughput. Data-centric networking, such as directed di usion [8], enables sensor data to be dis- seminated from data sources to sinks with low delay. In addition to low delay, multimedia dissemination also requires high bandwidth and delivery ratio. This throughput require- ment cannot be guaranteed by a single path reinforced in basic directed di usion. Thus enhancement to directed di usion is needed. Multiple Description Coding (MDC) is a coding technique which generates multiple equally important descriptions [14]. The descriptions refer to n independent sub-streams (n >= 2). The packets of each description are transmitted over multiple paths. The de- coder reconstructs the video clip from any combination of descriptions received, including a single description. MDC is error resilient to media streams in that packet loss or net- work congestion will not interrupt the stream but only cause a temporary loss of quality. MDC is better for wireless links than the layered coding as used in MPEG-2 and MPEG-4. Layered coding mechanisms generate a base layer and n enhancement layers. If the base layer is missing, which is quite possible for the time-varying wireless links, media streams 3 are interrupted. MDC matches multipath routing very well in that di erent descriptions generated by MDC are transmitted over di erent paths. In WSNs, especially video sensor networks, transmitting multimedia data requires the selection of paths that ensure high throughput and low latency. As pointed out by Gupta and Kumar [15], the fundamental reason leading to the degradation of the performance as the number of nodes increases is the fact that each node has to share the radio channel with its neighbors. Standard NS-2 uses primitive propagation models, including Free Space, Two Ray Ground and Shadowing which set a signal strength threshold to determine whether one frame is received correctly by the receiver. To provide a more accurate error model that re ects real BER (bit error rate), Wu [16] added SNR and BER models into NS-2 and model interference accurately. Thus other frames received by a receiver simultaneously are also modeled. We use their model in our simulation. Routing protocols that require location information, such as LAR [17], GPSR [18], and DREAM [19], do not need to ood routing requests. Others, such as DSR [20], AODV [21], ZRP [22], and TORA [23], su er from the e ects of ooding, even with some optimizations, since nodes do not know their locations. Flooding causes many routing messages to be propagated unnecessarily. To reduce the number of routing messages sent and to guar- antee reliable data dissemination, epidemic algorithms, which was rst used in replicated databases [24], has begun to be used in the context of wireless sensor networks, such as GOSSIP [25] and Fireworks [26]. These protocols require the sender to have knowledge of the potential receivers, which is achieved by exchanging beacons. Anonymous Gossip (AG) [27] overcomes this problem by attempting to send a gossip message and waiting until the other node sends back a gossip reply, incurring higher overhead. 4 Directed di usion, though regarded as an epidemic algorithm in [28] since it avoids broadcast storm, does not perform well with interest ooding. No matter what metrics are used in selecting a route (basic directed di usion uses delay), the route which performs best during route discovery phase may not perform well during the actual data transmis- sion phase due to di erences in interference levels caused by the di erent tra c patterns. Interest ooding increases tra c in the network and causes maximum level of interference. Exploratory data are ooded to determine the best path, which follows gradients estab- lished in the interest propagation phase. Actual application tra c only ows through the reinforced path, which is not a ected by inter-path tra c at all, assuming there is no other data transmission at that time. Every node has an interference range. Interference set [29] and con ict graph [30] are used to schedule network tra c or theoretically analyze the im- pact of interference on wireless networks. However, no routing protocol could have the prior knowledge about which path the actual data tra c will go through and what the tra c pattern will be like before the route is determined. Our goal is to design solutions which make more accurate routing decisions by reducing the interference level during the route discovery phase and making it more similar to that during the actual data transmission phase. Chapter 2 gives background information about research related to our protocols for video streaming over wireless sensor networks. In Chapter 3, we discuss the motivations for our work. We describe the problem statement in Chapter 4. Protocol design is presented in Chapter 5. Chapters 6 and 7 explain the implementation and performance of the protocols. We conclude our research and discuss future work in Chapter 8. 5 Chapter 2 Related Work 2.1 Hardware Support The latest series of TelosB motes [31], the ZigBee motes [32] with improved abilities, or PC104 [33] may be used for applications in WSNs which require intensive memory and bandwidth. Telos is an ultra low power wireless sensor module ("mote") for research and experi- mentation [30]. The latest in a line of motes developed by UC Berkeley to enable wireless sensor network (WSN) research is called Telos. It is a new mote design built from scratch based on experiences with previous mote generations. Its new design consists of three major goals to enable experimentation: minimal power consumption, easy to use, and increased software and hardware robustness. ZigBee [32] is an important standardized approach to the control of sensor and actuator networks in home/building/industrial automation applications that use low rate wireless PAN network technology. ZigBee stack includes Network and Application Layer proposed by ZigBee Alliance and IEEE 802.15.4 MAC and Physical Layer for both mesh and tree- based communication. PC104 [33] is a popular standardized form-factor for small computing modules typically used in industrial control systems or vehicles. It gets the name from the popular desktop personal computers initially designed by IBM called the PC, and from the number of pins used to connect the cards together (104). PC104 cards are much smaller than ISA-bus cards found in PC?s and stack together which eliminates the need for a motherboard, backplane, 6 and/or card cage. Power requirements and signal drive are reduced to meet the needs of an embedded system. Because PC104 is essentially a PC with a di erent form factor, most of the program development tools used for PC?s can be used for a PC104 system. This reduces the cost of purchasing new tools and also greatly reduces the learning curve for programmers and hardware designers. Most of the sensors used in research for audio/video streaming are found to use em- bedded microprocessors which have higher computing abilities [34]. 2.2 On-going Video Sensor Network Research Many world-wide universities and research companies have been conducting research projects of video sensor networks or WMSNs, such as self-con guring video-sensor networks for healthcare at Imperial College London [35], large scale video sensor networks for dis- tributed surveillance at Palo Alto Research Center (PARC) [36], Video Web at University of California at Riverside [37], a video-based sensor network architecture for video surveillance and environment monitoring proposed by Feng et. al. [38], maximizing the life of wireless video sensor networks at Virginia Tech [39], the Distributed Interactive Video Array (DIVA) system at Spawar Systems Center (SSC) San Diego [40], WMSNs research at Ohio State University [41], video sensor network for autonomous coastal sensing at Boston University [42], Quality of Service (QoS) research for vision-based WSNs at Purdue [43], etc. 2.3 QoS issues in WMSN The network layer of WMSN needs to address QoS issues of multimedia streams. [44] considers the bandwidth constraints for multimedia mobile medical calls. Distributed image 7 sensing with QoS-based geographic routing is used in [45] for network localization, dynamic routing and load balancing. Other papers are more concerned with real time streaming is- sues, e.g. RAP [46], SPEED [47] and its extension MMSPEED [48]. They prioritize packets based on their delivery speed, computed from geographic information and time elapsed, at the source, hop-by-hop or every a few hops. MMSPEED also performs route selection in reliability domain. Although they are generic protocols for real time data transmission over ad hoc or sensor networks, real time protocols for WMSN could be developed by extending their framework. 2.4 Routing Metrics in Wireless Sensor Networks Routing metrics in wireless ad hoc networks are important considerations due to the unpredictability and heterogeneity of link qualities [49]. Existing wireless ad hoc routing protocols typically select routes using minimum hop count, e.g. DSR [20] and DSDV [50]. Directed di usion [8] selects routes in sensor networks with the least delay. Recently, many new link quality metrics have been proposed. [51] compares the performance of the follow- ing three metrics. Adya et al. [51] measures the round trip delay of unicast probes between neighboring nodes and proposes Per-hop Round Trip Time (RTT). Per-hop Packet Pair De- lay (PktPair) measures the delay between a pair of back-to-back probes to a neighbor node [51]. Expected Transmission Count (ETX) [52] measures the loss rate of broadcast packets between pairs of neighboring nodes and estimates the number of retransmissions required to send unicast packets. Weighted Cumulative Expected Transmission Time (WCETT) [53] is used for selecting channel-diverse paths and accounts for the loss rate and bandwidth of individual links. Park et al. [54] presented a new metric, Expected Data Rate (EDR), for 8 accurately nding high-throughput paths in multi-hop ad hoc wireless networks based on a new model for transmission interference. Unfortunately, none of these metrics can be directly applied to wireless sensor network that simultaneously take into account delay, throughput and interference. Furthermore, none of previous papers proposed a combined metric for sensor networks with all those considerations. In [52], ETX was incorporated into DSR and DSDV to improve throughput with little consideration of delay or interference. WCETT [53] is more suitable in multi- radio wireless mesh networks. EDR [54], unlike ETX, cannot be computed dynamically. More space and computation are required by EDR when it is incorporated into DSR and AODV. 2.5 Interference-aware Protocols Interference-aware protocols have recently been explored in multi-hop wireless net- works. [55] studies routing problems in a multihop wireless network using directional an- tennas with dynamic tra c and presented new de nitions of link and path interference. In their other paper [56], they present routing algorithms to compute interference-optimal cost-bounded paths and an optimal bandwidth allocation algorithm to allocate timeslots. We do not give detailed analysis, computation and implementation for interference because we try to make full use of the ETX information. [57] and [58] give the throughput bounds and capacity for interference-aware routing in wireless networks respectively. We may use them to test our protocol by observing the throughput performance. [59] derives an inter- ference aware metric NAVC based on the information collected from 802.11 MAC. In [60], an interference aware routing scheme is designed to alleviate the near-far problem at the 9 network level for cellular systems. EIBatt et. al. [61] address the problem of interference- aware routing by coupling the lower three layers of the ISO Open Systems Interconnection (OSI) protocol stack. We only use ETX, the link layer indicator, to measure the link quality as well as interference to simplify the problem. Nguyen et. al. [62] consider radio interfer- ence and modify OLSR routing protocol for bandwidth reservation and interferences. Our paper modi es directed di usion, a routing protocol for wireless sensor networks, to take into account throughput, interference and delay. 2.6 Short-comings in ETX In sensor networks, each node has limited memory and requires in-networking pro- cessing. Link quality is highly variable and delay metrics may not be able to measure the variation. Most sensor network nodes are equipped with one omni-directional radio and use one channel at a time. Thus there is more interference than in multi-radio or multi-channel nodes. Taking the summation of ETX in a route penalizes routes with more hops and as- sumes that this will lower throughput due to interference between di erent hops of the same path [52]. It is not true that all the hops in a path will interfere with each other. Bader et al. [63] discovered the optimal packet injection in linear networks and they found that the rst packet has outpaced the rest of the packets when the fourth packet is to be injected. Based on this result, we modify the computation of ETX for a path to more accurately quantify intra- ow interference. With this change, Dijkstras algorithm can no longer be utilized and greedy algorithm is used instead. Inter- ow interference is also considered in Dynamic Codeword Routing (DCR) [64]. 10 2.7 Theoretical Analysis of Throughput-Delay Tradeo Wireless nodes are composed of nodes which communicate with each other over a wire- less channel. Its capacity is di erent from wireline networks. Gupta-Kumar [65] presents a network model and analyzes the capacity of wireless networks. The conclusion is that when n identical randomly located nodes, each capable of transmitting at W bits per second and using a xed range, form a wireless network, the throughput obtainable by each node for a randomly chosen destination is ( Wnlogn) bits per second under a noninterference protocol. Throughput-delay trade-o in the Gupta-Kumar xed network model [65] is theoret- ically analyzed in [66]. Gamal et. al. [66] focuses on characterizing the delay and de- termining the throughput-delay trade-o . They show that the optimal throughput-delay trade-o is given by D(n) = (nT(n)), where T(n) and D(n) are the throughput and delay respectively. Our results also show similar trade-o between throughput and delay in practical sensor network algorithms. 2.8 Multi-path Routing Multipath routing has long been researched in wired networks. One of the earliest papers [13] proposed an extension of the distance-vector algorithm to nd multiple disjoint paths, one of which is the shortest path to a destination. Alternate path routing (APR) [12] provides load balancing and failure prevention by distributing tra c among a set of diverse paths in mobile ad hoc networks. Geographic proximity of candidate paths is avoided in the algorithm. Split Multipath Routing (SMR) [11] is another multipath protocol for ad hoc networks that allows paths to share nodes when no disjoint paths can be found. They 11 also use a per-packet allocation scheme to distribute packets over multiple paths instead of splitting tra c only at the source. 2.9 Multistream Video Coding In a framework for supporting multipath video transport over ad hoc networks, multi- stream video coding is one of the essential components. Mao et. al. [10] combines multipath transport with multiple description coding (MDC) in ad hoc networks. Other e cient cod- ing schemes that were proposed are feedback-based reference picture selection (RPS) [67], layered coding (LC) with selective ARQ [68] and multiple description motion compensation (MDMC) [15]. Figure 2.1: Scenario for MD source coding with two channels and three receivers [1] 2.10 Message Redundancy in Routing Protocols Message redundancy caused by excessive ooding has been realized in recent years. The taxonomy of the major proposed solutions is described in [26]: Probabilistic-based schemes, area-based methods and neighbor knowledge methods. GOSSIP [25], Anonymous 12 gossip [27] and Fireworks [26] fall under the rst category. In GOSSIP, when a node rst receives a route request, it broadcasts the request to its neighbors with probability p and it discards the request with probability 1 p. In Fireworks, a node re-broadcasts the message to all its neighbors with probability p and it sends it to only c randomly selected neighbors with probability (1 p). The Fireworks protocols results in higher reliability given the same number of links over which the broadcast packet is transmitted. Anonymous gossip (AG) does not require any member to know the other members of the multicast group because the sender sends a gossip message and it will gossip until the other node sends back a gossip reply. The other two categories require location awareness or two hop neighborhood knowledge, both of which incur more overhead than the rst category. 13 Chapter 3 Motivations and Applications In this chapter we discuss the motivations for our protocols in video sensor networks as well as its potential applications. 3.1 Motivation Although directed di usion is a widely used in sensor networks, it has several weak- nesses when applied to Wireless Multimedia Sensor Networks (WMSN). It only considers delay as the routing metric to select best path. As a result, high throughput may not be achieved. Furthermore, directed di usion is a single-path protocol, which causes through- put degradation for multimedia applications, considering the limited bandwidth and energy constraint of sensor nodes. Besides, its failure to consider deadline during the route selection lowers the percentage of packets which can meet the deadline of real-time tra c. Finally, its reliance on ooding gives rise to di erences in interference levels during the exploratory data phase and the actually data transmission phase, which makes the route decision even more inaccurate. We propose three routing protocols to augment and extend directed di usion to handle these issues. First, we propose EDGE (ETX-Delay GrEedy algorithm) where a single-path metric which considers throughput, delay and intra- ow interference. Secondly, we further address the throughput and deadline issues in multimedia streaming over sensor networks by proposing multi-path protocol DCHT (Delay-Constrained High Throughput). Lastly, we present the improvement on QoS-based routing by limiting interference in lossy wireless sensor networks. 14 3.2 Applications Wireless Sensor Networks (WSNs) can support a wide range of applications such as target tracking, home automation and environmental monitoring. They serve to explore the requirements, constraints and guidelines for general sensor network architecture design. Some of the applications may be reinforced or augmented with transmission of multimedia data over WSNs so that we may have multimedia surveillance, storage of potentially relevant activities from networked cameras, tra c conditions and collision avoidance. 3.2.1 Multimedia Surveillance With the improvement of video technology and sensor networks, the infrastructure for new generations of multimedia surveillance systems was proposed. Many di erent media streams, such as audio, video, images, textual data and sensor signals, will be collected and analyzed automatically to interpret the controlled environment in real-time [69]. Dis- tributed architectures with xed and active cameras are devised as new solutions in order to enlarge the view of traditional surveillance systems. Their view is enhanced with other sensed data and multi-resolution views are explored with zooming and omnidirectional cameras. Multimedia surveillance applications involve both indoor and outdoor areas and people surveillance gains its most popularity. Biometric technology is also used to enrich multimedia surveillance systems. 3.2.2 Data-centric Storage Habitat and environmental monitoring is a new class of sensor network applications which has enormous potential bene ts for scienti c communities and the whole society [70]. 15 Long-term data collection in di erent scales and resolutions can be enabled by equipping natural spaces with networked microsensors. It is hard to obtain the localized measure- ments and detailed information through traditional instrumentation; while sensor has in- timate connection with its immediate physical environment, which allows each sensor to win over traditional methods. Sensor nodes communicate with each other and cooperate in performing more complex tasks. 3.2.3 Tra c Conditions and Collision Avoidance Vehicular network is composed of cars with GPS devices and, in a more advanced systems, with video cameras. Cameras may acquire information about the environment, such as tra c signs, congestions, tra c accidents, and road merging information, and either report them to the base station or broadcast them to their neighbors. Although cars have more power than sensor nodes, the bandwidth limit due to mobility is similar to that of sensor networks which is caused by constrained power of sensors. 16 Chapter 4 Problem Statement 4.1 Single-path metric Costp WMSNs have urgent needs for new protocols which meet the stringent QoS require- ments of multimedia streaming. For example, the data rate of H.264 varies between 64 kbps and 240 Mbps depending on di erent levels [7]. Both throughput and delay requirements should be embodied in the new protocols. The shortcomings of minimum hop-count as a metric have been widely recognized. Routing protocols with minimum hop-count metrics assume that all links have identical properties. In practice, wireless links often do not have the same quality, due to di erent antenna power, background noise and interference. None of the other metrics can be directly used in directed di usion to take into account all the delay, throughput and interference constraints. Interference a ects throughput which is a critical requirement need for multimedia data. In designing a metric to take into account delay, throughput and interference for WMSNs, the key challenge here is to nd an e ective way to combine them so that we can compute the cost of each route and nd a route with the minimum cost that satisfy our goals for multimedia data. 4.1.1 Assumptions and Goals We begin by listing the assumptions we made about the networks. All nodes in the network are stationary. Each node is equipped with one 802.11b radio. 17 There are one source and one sink in the network. Based on these assumptions, we have three main goals. First, the protocol should take both end-to-end delay and ETX of a route into account. Since the 802.11b MAC implements an ARQ (retransmission) mechanism, a links ETX can be computed. Second, the path metric should not decrease when one more hop is added to the route. Third, the method for computing the path ETX must consider intra- ow interference. 4.1.2 De nitions, Notations and Formulae The ETX of a link is the predicted number of data transmissions required to send a packet over that link [52]. ETX = 1d f dr (4.1) The forward delivery ratio, df, is the probability that a data packet successfully arrives at the recipient; the reverse delivery ratio, dr, is the probability that the ACK packet is successfully received. De nition of ETXp: The path ETX is the maximum of the sum of the ETXs of any three successive hops in a route. This computes the amount of bottleneck. N is the number of hops. ETXj is the ETX value of the jth hop. The number of bottleneck links may vary according to the network density. ETXp = N 3maxi=0 ( i+2X j=i ETXj) (4.2) 18 De nition of delayp: The end-to-end delay of a packet in a network is the time it takes the packet to reach the sink from the time it leaves the source. De nition of Costp: The path cost is the combined metric of a route. and are non-negative integers. Costp = ETXp delayp (4.3) De nition of decision interval (INTERVAL): We start an adaptive timer at each node (except the source) when the node receives the rst exploratory packet. After an INTERVAL period, the timer expires and it selects the route with the lowest Costp. EXPLORE DELAY is a constant with the basic timeout value. ETXi is the ETX value of the upstream link on which the rst exploratory data arrive. Di erent INTERVAL may be computed at di erent nodes based on the following formula: INTERVAL = ETXi EXPLORE DELAY (4.4) 4.1.3 Computing Path Metric Our path metric is called Costp which conforms to the three goals we set earlier. First, it takes both end-to-end delay (delayp) and ETX of a route (ETXp) into account. By adjusting the values of and , we are able to set di erent weights to each factor. If throughput is more important for an application, should be greater than and vice versa. The way we compute ETX for a path is based on the theoretical analysis and experimental demonstration in [63]. Bader et al. employed the Packet Decoupling property to conclude that the rst packet has outpaced the rest of the packets when the fourth packet is to be 19 injected. Li. et al. [71] examined the capacity of a chain of nodes and they found that an ideal MAC protocol could achieve chain utilization as high as 1/3. The example below illustrates this principle for the node placement in Figure 4.1. Figure 4.1: Transmission range and interference range for a chain of nodes. The solid line circle is a nodes transmission range while the dotted line circle shows the interference range. Nodes within 3 hops interfere with each other. We compute the maximum summation of ETXs in every three successive hops and regard it as the bottleneck. This is a more accurate indicator of the worst bottleneck in the entire path. Assuming that 2, 2, 2, 2, 2, 3 are the ETX values for the six links in Figure 4.1. Then ETXp is 7. If we change the ETX values in Figure 4.1 to 1, 1, 1, 3, 3, 3, the new ETXp becomes 9. According to the de nition of ETXp, the latter path is worse. If path ETX is computed using the total ETX of a path, we get 13 for the former path and 12 for the latter. Then the latter path is better. Total ETX exaggerates the intra- ow interference and will leads to a wrong route selection. Another reason for using our path ETX is the impact of intra- ow interference in the pipeline of packet transmission (Figure 4.2). A packet is injected at Hop 0 every unit time 20 interval. p1 is the rst packet transmitted. Suppose that each packet takes the same time to transmit on each hop, say, 30ms. When p1 nishes transmission on Hop 1, p2 is injected into network. p2 has to wait till p1 is transmitted on Hop 3 due to the intra- ow interference. The delay here should be 60ms. Figure 4.2: Pipelining mechanism of data transmission in sensor networks with intra- ow interference taken into account. The combined metric also satis es the second goal that it does not decrease when one more hop is added to the route. We consider intra- ow interference in the third rule by adding the ETX values of three successive hops together. Refer to [52] for more information. 4.1.4 Problem Formulation Our routing algorithm with metric Costp can be formulated as a cross-layer combi- natorial optimization problem, where the objective is minimizing metric Costp in order to meet QoS requirements of multimedia data. In formulation, constraints include connectiv- ity, link stability, and retransmission times. The solution space consists of combinations of 21 all possible routes that provide a connection from the source to the sink. We now present the NLP (Nonlinear Programming) formulations for our routing algorithm. We model the network as a directed graph G(V;E) and a collection of sub-paths from the source to any other node in the network. Let P denotes the set of all sub-paths from the source to any other node in the network: thus , P = (src;i), src is the source node; , dest(p) = i, in which p = (src;i). With such path models, we want to minimize both the ETXp and delayp. The math- ematical formulation is as follows: minp2P (ETXp delayp ) The above objective function is subject to: 8p2P;ETXp = dest(p) 3maxi=0 i+2X j=i ETXj 8p2P;delayp = tdest(p) t(src) 8j2E;0 <= ETXj <= 1 8j2E;ETXj = 1d f dr 22 8j2E;0 and is the number of paths needed at the source. We need to nd more than the required number of paths because some candidate paths may not be reinforced i disjoint nodes cannot be found or the delay exceeds the playout deadline. If two nodes try to reinforce a link that converges to the same node, the rst one to reinforce would win. In Figure 5.4, A reinforces C rst. Then, B tries to reinforce C and C will drop the packet because C regards it as an old message. C will then send B a NEG RESPONSE so that B could delete the entry of C in its local candidate table and selects the next candidate, e.g. D. In addition, delay constraints must be satis ed by computing the di erence between two local timestamps. We can guarantee that if we choose the node within the delay constraint in each step, the nal route can also meet the delay constraint, no matter how many times we have to choose the next-best node. This technique not only guarantees disjoint nodes (paths with disjoint nodes are de nitely disjoint paths), but also ensures loop-free path since loops are broken when selecting the next candidate in the local table. In Figure 5.5, A has already reinforced B and C, D, E are reinforced sequentially. When E tries reinforcing B, B drops the packet and sends NEG RESPONSE to E. So E is able to select the next candidate F to reinforce. Standard di usion only reinforces one 37 Figure 5.4: How to avoid the node already reinforced in another path. route and when there is a loop, the reinforcement packet is simply dropped and no packet is received at the source. Our algorithm guarantees the success of reinforcement packets reaching the source provided that the delay constraint could be satis ed. When a node discards the already-reinforced node and selects the next candidate, it must estimate the new end-to-end delay so that the deadline set earlier can still be met. In Figure 5.4, B reads the local timestamps of C and D (tC and tD respectively) from its local table and if tC tD <= n ( is the slack between the real playout deadline and the deadline used by the sink to get candidate paths; n is the estimated number of hops in the reinforced path), we reinforce D; else, we search for more candidates in the table. If it still fails, the reinforcement packet is dropped. It is possible that the throughput of the newly-selected route with disjoint nodes is degraded. Since delay is more important than throughput in multimedia data transmission, the slight di erence in throughput is tolerable. 38 Figure 5.5: How to avoid loops. Probabilistic tra c splitting Multiple Description Coding (MDC) is used for multimedia tra c. We let the coder generate the same number of descriptions (streams) as that of paths found. Descriptions are sent through di erent paths. In order to avoid using the same paths all the time, redundant paths are built to share the tra c load. Assume the source has 2 routes and descriptions to be sent. Their Costp values are C1 < C2 < < C2. Then, path 1 and path 2 are allocated to transmit the rst description, path 2 and path 2 1 the second, etc. The transmission of each description alternates between the paired paths with certain probabilities. For example, Description 1 has the probability of 1=C2 1=C1+1=C2 to be sent over Path 1. In a pair of paths, the one with better quality is being used more often. 39 5.2.2 Parameter settings , adjustment The problem of nding the suitable values for and can be converted into a Con- straint Satisfaction Problem (CSP) [76]. We have two constraints: delay and throughput. The initial goal of our algorithm is to maximize throughput within a certain delay con- straint. The playout deadline is a natural upper bound for delay constraint. We use ETX to estimate throughput and ETX also has an upper bound in di erent hardware or sim- ulators. For example, since the maximum retransmission time in NS2 is 7, ETX has a maximum value of 8. Besides, we can also estimate the upper bound for ETXp given the required bandwidth requirement. We use a min-con icts algorithm [77] to solve the CSP problem in this paper. A similar method is also use in [78] to solve the problem of nding a path with two additive constraints called multi-constrained path (MCP) problem. Since ETXp is not a completely additive constraint and our formula is a weighted product instead of weighted sum, the algorithm we use is slightly di erent. The basic idea is to rst combine the delay and ETX, i.e. Costp, and then nd the corresponding shortest path. In Table 5.8, D and E are delay and ETXp upper bounds respectively. d and e are the delay and ETXp of a certain path. p, q, and r are paths between source and sink. q and r can be obtained using any algorithm or enumeration. p is obtained from the Dijkstras algorithm. The maximum probability that exists in a feasible path is less than 1=2 if algorithm MCP-DE cannot nd a solution [78]. 40 Table 5.8: Algorithm MCP-DE (D, E, d, e). Costp formula is simpli ed to d e ( is not necessarily an integer) and it is equivalent to d e as the combined metric for routing. 1 q path with lowest ETXp 2 if (e(q) >E) then 3 return NULL 4 else if (d(q) <= D) then 5 return q 6 p Dijk(d) 7 if (d(p) >D) then 8 return NULL 9 else if (e(p) <= E) then 10 return p 11 while TRUE do 12 [lg(d(q)) lg(d(p))]=[lg(e(p)) lg(e(q))] 13 r path with lowest d e 14 if (e(r) = e(q) or e(r) = e(p) then 15 return NULL 16 else if (e(r) >E) then 17 p r 18 else if (d(r) >D) then 19 q r 20 else 21 return r Bottleneck nodes One of our goals is to nd disjoint paths. In real situations, some nodes have to be shared by more than one path. In Figure 5.6, Node A is a bottleneck node since nodes in C1 can only communicate with nodes in C2 through Node A and vice versa. A is a cut-vertex and the two edges incident to A are cut-edges [79]. There might be more than one cut-vertex in a certain topology. Min-cut algorithm is used to nd bottleneck nodes the failure of which will cause the least partition [80]. The time to compute the min-cut value of a given graph G is O(n4logn). We can also use this algorithm to nd the bottleneck nodes which prevent us from nding disjoint routes. However, it is not scalable. When 41 the network size increases, it consumes too much energy to nd bottleneck nodes than to deploy more nodes in their neighbourhood to build disjoint paths. Figure 5.6: Unavoidable bottleneck nodes. Nodes connected by a line are able to commu- nicate with each other. Or else, they are out of range. In real situations, there is human intervention to the deployment of sensor nodes. Given the lower bound of node density, the percentage of bottleneck nodes is limited. In Figure 5.7, if C is the only node in the overlapping area, it has a high probability to become a bottleneck node (it may not be if A has other nodes in its transmission range that have paths to B without the help of C). If more than one node is put in the overlapping area, no bottleneck nodes will exist. The condition is su cient but not necessary. Hence, we are giving a looser bound for node density. Assume node deployment follows Poisson distribution. x is the number of nodes in the overlapping area mentioned above. Given the average density and overlapping area A, x = A. P(x = k) = e A( A)k k! (5.1) 42 Figure 5.7: Overlapping of A?s and B?s transmission ranges. Suppose the entire network is a square with the side of E and the number of nodes is N. R is the radius of the transmission range. = NE2 (5.2) If nodes are evenly distributed and we only consider the scenario in Figure 5.7, that is, EpN >R> 12 EpN . So, A = 2(R2arccos E2R(pN 1) E q 4R2(pN 1)2 E2 4(pN 1)2 ) (5.3) Then, the probability that there is more than one node in the overlapping area is P(x> 1) = 1 P(x = 0) P(x = 1) = 1 e A(1 + A) (5.4) Given E = 1200, N = 100, R = 100, P(x > 1) is 0.2492. N-P relations are shown in Figure 5.8. Likewise, given P(x > 1), E and R, we can also nd N. As seen from the 43 gure, the network should have very high density to guarantee the probability of more than one node in the overlapping area above a certain threshold. Figure 5.8: The relation of P(x> 1) and N. 5.3 Epidemic Algorithm in Di usion In this section, we present a set of localized epidemic algorithms (without using neighbor information) for a modi ed directed di usion. The main purpose is to reduce interference during the exploratory data phase, make the interference level more similar to that during the actual data transmission phase and improve route selection. The key challenge for designing such a protocol is that probability-based schemes usually makes use of some basic understanding of the network topology to assign to a node a probability p to broadcast, which means the sender knows the IDs of potential receivers. However, directed di usion is a localized ID-free routing protocol, where no node knows its neighbors before interest ooding. (We assume this original property of directed di usion although in practice it may be possible for the sender to determine the MAC addresses of the receivers.) So we 44 Table 5.9: Pseudocode segment for epidemic Interest ooding (receiver side) 1 If it is a new interest packet 2 Set r = random() 3 If r> 1 p 4 Update gradient table 5 Else 6 Drop interest 7 Else 8 Execute original code have two choices here: receivers probabilistically drop interest or senders probabilistically send exploratory data since neighbor information is known by the sender. In both ways, we are taking the risk of losing candidates. There is a trade-o between the degree of interference level match and the completeness of the candidate pool. (Our results below show the optimal probability that will maximize throughput or minimize delay for each network con guration.) 5.3.1 Epidemic Interest Flooding Interest ooding is the rst phase of directed di usion. To adapt epidemic ooding to directed di usion, when a node receives an interest packet, it updates the gradient table with a probability of p, i.e. with a probably of 1 p, the node will not update its gradient table (Table 5.9). (We assume the sender has no knowledge about its neighbors.) Strictly speaking, interests are still forwarded through the network with a reduced rate. However, exploratory data are propagated selectively, which satis es our goal, since only parts of the gradients, with the percentage of p, are established in the earlier phase. In Figure 5.9, interests from Nodes 2 and 4 are probabilistically dropped by Node 1; thus only the interest from Node 3 is updated in Node 1s gradient table. In the next phase, 45 exploratory data ows from the other side to Node 1 and only Node 3 will be chosen as the downstream node. However, if Node 1 does not drop interests from Nodes 2 and 4, the exploratory data owing from Node 1 to Node 3 will su er from the interference coming from Node 2 and 4 since Node 1 is also sending exploratory data to them. Figure 5.9: Probabilistic interest dropping reduces interference level during exploratory data phase. The dotted circle is the interference range of Node 1. 5.3.2 Epidemic Exploratory Data Propagation Another way to limit exploratory data ooding is to drop exploratory data proba- bilistically during the exploratory data phase. The sender selects gradients from the table probabilistically as the downstream links. This is the direct implementation to reduce ooding during the exploratory data phase. Both GOSSIP and Fireworks algorithms can be used. Obviously, GOSSIP algorithm eliminates a variety of candidates, where the change in interference level may be very abrupt. In Figure 5.10, Node 1 discards the exploratory data completely while Node 1 randomly selects two neighbors (c = 2). Although GOSSIP reduces interference in this case, it also eliminates all candidates links from Node 1. Nodes 2 and 2 send to all nodes in the gradient table. Links in the transmission range of Node 2 has the same interference range as those in the transmission range of Node 2. The transmission 46 Table 5.10: Pseudocode segment for epidemic exploratory data propagation (sender side) 1) Gossip version 1 If it is exploratory data 2 Set r = random() 3 If r<= p 4 Send it to all nodes in gradient table 5 Else 6 Discard it 7 Else 8 Execute original code 2) Fireworks version 1 If it is exploratory data 2 Set r = random() 3 If r<= p 4 Send it to all nodes in gradient table 5 Else 6 Send to randomly selected c nodes in gradient table 7 Else 8 Execute original code of Node 1 rarely a ects that of Node 2 if Node 1 and 2 are beyond the interference range. The two transmissions in the transmission range of 1 cause limited interference with each other compared to full ooding. However, the advantage is that more candidate links are being considered. The combination of Table 5.9 and Table 5.10 above is worth considering. Intuitively, there will be less interference and fewer candidates than either scheme. We will not discuss the details here. 47 Figure 5.10: Comparison of two gossip-based algorithms. The left is GOSSIP and the right is Fireworks. 48 Chapter 6 Implementation 6.1 EDGE implementation We conducted both packet level simulation study [73] and NS2 simulation to demon- strate the e ectiveness of EDGE, with Costp metric, in achieving much higher throughput and lower delay relative to the conventional implementation of directed di usion. We eval- uate the performance on di erent topologies with lossy links. The following sub-sections describe our methodology and the evaluation metrics. 6.1.1 Simulation Methodology Our simulation setup consists of a sender, a receiver, and a tra c generator. Nodes are evenly distributed in a grid topology, in which the sender is at the bottom right corner and the receiver is at the top left corner. We simulate the algorithms using a modi cation of directed di usion release 3.2.0 in ns2.29. We use the IEEE 802.11b protocol in the MAC layer. The channel has a bandwidth of 2Mb/s. The transmission range is 250m and the interference range is 550m. The distance between the closest pair of nodes is 123m. The maximum number of link layer retransmis- sions is seven, after which the packet is dropped. Packets are sent as UDP packets in the transport layer. CBR tra c is generated to simulate video streams. Most encoding schemes are CBR- based algorithms, such as MPEG-2 TM5 or MPEG-4 VM Q2 [81]. Even if the encoder gener- ates VBR (variable-bit-rate) tra c, there are methods to optimize its transmission on CBR 49 channel [82]. Usually, it is di cult for sensor nodes to implement the sophisticated video coding techniques used in the MPEGx or H.26x series [83]. Encoding/compression schemes suitable in WMSNs are divided into three categories [34]: JPEG with Change/Di erence Coding, Distributed Source Coding and Multi-layer Coding with Wavelet Compression. We omit the encoder and the decoder in this simulation by only generating CBR packets with the size of 500 bytes (the packet size 533 bytes is discussed in earlier sections. We use 500 to make it simple) to simulate one frame so that we could design a generic protocol for video data transmission in WMSNs. The minimum tra c rate we are testing is 40 packets per second, which exceeds 15 packets per second, the afore-mentioned lowest throughput requirement of H.264. As de ned earlier, ETX is the predicted number of data transmissions required to send a packet over a given link. Thus ETX measures the link loss ratios, asymmetry in the loss ratios between the two directions of each link and interference among successive links of a path. Typical implementations like MintRoute, the standard routing protocol within TinyOs, use packet based snooping to compute the ratio of number of packets received to the total number of packets transmitted over a link and use this value to compute ETX. Since the quality of the link varies over time, ETX needs to be updated periodically and may take historical variations into account. In the current implementation, however, we assume ETX to be a little-varying value for a given link. In ns2, error model simulates link-level errors or loss and errors are generated from a simple model with packet error rate in our simulation. We insert an error model whose error rate follows uniform distribution with a certain ratio (from 0.2 to 0.7, step 0.1 in our simulation) over outgoing wireless channels to each node which are not in the top or right boundaries and keep incoming channels with no 50 error. Suppose we have a link composed of nodes A and B (A!B). TA and RA are the error rates of node As outgoing channel and incoming channel, respectively. TB and RB of node B are de ned the same as node A. Link delivery ratios can be computed as follows. df = (1 TA) (1 RB);dr = (1 TB) (1 RA) (6.1) Unlike traditional implementation of directed di usion where intermediate nodes select the rst link on which the exploratory data arrived, intermediate nodes in EDGE starts a timer on receiving the rst exploratory data packet. It then bu ers all incoming ex- ploratory data packets until the INTERVAL timer expires. On expiration of the timer, the node computes the cost for each exploratory packet received and selects the link from which the exploratory data with least cost arrived. It then forwards that packet to all the neighbours who had earlier expressed an interest for the named data. While forwarding the exploratory data, the node also updates the ETXp eld in the packet header. When the sink reinforces the link from which the exploratory data with least cost arrived, the rein- forcement propagates all the way back to the source through the least cost links recorded by all the intermediate nodes. Data from the source is then drawn towards the sink on this reinforced path. Periodically the source marks one of its data packets as exploratory and oods it to the sink, in order to discover a better path if it exists. Our algorithm is implemented without synchronization although its use could simplify the implementation. To do this, each node scales the time period between the rst and the last exploratory data within timeout. delayp is computed with a relative timestamp, which is an integer between an arbitrary number C0, such as 10, and INTERVAL. Suppose there are N ows reaching a certain node when the timer expires. The timestamps are T1, T2, 51 , TN respectively (T1 ). Streams + 1, + 2, , are multiplexed with Streams 1, 2, , respectively. The 1-description case is di erent from EDGE because it considers deadline when selecting the paths. Also, for the 1-path case, we do not reinforce one extra path at the sink side. As we can see from the curves, both the throughput and goodput improve much when the number of paths (descriptions) goes up. Goodput from the 2-path case to the 3-path case does not increase much because in some cycles only one or two paths can be found. 4-path case still gets high goodput because four paths can be found with a high probability according to our simu- lation results. In Figure 7.14, we show the number of packets and packets that meet the deadline received at the sink. The total numbers of packets sent at the source increase with more descriptions because overhead is added to each description, which only causes slight di erence as seen from both Figure 7.13 and Figure 7.14. The end-to-end delay (Figure 7.15) decreases when we use more paths since packets generated at the source are split up into more paths which lightens the tra c burden. Congestion is alleviated by using more paths although nding more paths increase overhead. 65 We also compare the energy consumption and routing overhead in the DCHT protocol with basic di usion and EDGE. Intuitively, our protocol may consume more energy since we are using more resources of the networks. In Figure 7.16, it is shown that the DCHT protocol does not consume additional energy, compared with basic di usion and EDGE (two single-path protocols). A single path does not have enough bandwidth, which leads to congestion in video streaming. This results in more retransmission which requires more energy consumption and end-to-end delay. Also, larger network consumes less energy, which is a surprising fact observed in our simulation. The reason might be that it is easier to build multiple paths in a larger network which helps disseminate the tra c. The in uence of di erent paths (descriptions) over energy consumption is a concave (Figure 7.17), which is better than linear increase. More energy consumption leads to the discovery of more paths, which transmit video data more e ciently. The only extra overhead in our protocol is the use of NEG RESPONSE in or- der to nd multiple disjoint paths (Figure 7.18). As we have estimated, it is harder to nd more paths, especially when we try to avoid the same node. So it requires more NEG RESPONSE messages to nd 4 paths, considering that each node only has 6 neigh- bours in our topology. When we have larger network sizes, we have higher probability to get multiple paths without sharing nodes with other paths. 7.2.2 Discussion The goodput of our protocol with 4 paths in 77-node network can reach is above 180 packets per second. The packet size is 128 bytes and foreman sequence nishes transmitting in 8 seconds. The corresponding data rate is 23 kbps, which barely meets 28 kbps, the data 66 rate of the low quality video. By sending video through more paths, the goodput could even be increased to meet the high quality video requirements. The average end-to-end delay of the 4-path case is about 120 ms, much smaller than the 200 ms deadline we set. 7.3 Epidemic ooding We run each setting, with di erent topology and percentage of nodes that do not drop interests, for 50 times and take the average of the metrics. In our discussions below, let p be the fraction of nodes that do not drop interests. We compare the throughput, end- to-end delay and directed di usion related metrics, such as, percentage of cases where no interest reaching the source, percentage of cases where no path was built (which includes the previous cases) and percentage of cases with zero throughput (which includes the previous two cases). Each run lasts for 300 seconds. 67 (a) Throughput with di erent network sizes (b) End-to-end delay with di erent network sizes Figure 7.1: Throughput and delay comparison between EDGE and directed di usion in grid topologies. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. 68 (a) Throughput with di erent delivery ratios of lossy links (b) End-to-end delay with di erent delivery ratios of lossy links Figure 7.2: Throughput and delay comparison between EDGE and directed di usion in 10-by-10 grid with di erent delivery ratios of the lossy links. Tra c rate is 40 packets per second. = 1, = 1 in Costp. Packet size is 500 bytes. 69 (a) Throughput with di erent tra c rates (b) End-to-end delay with di erent tra c rates Figure 7.3: Throughput and delay comparison between EDGE and directed di usion in 10- by-10 grid with di erent tra c rates. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. 70 Figure 7.4: Network delivery ratio comparison between EDGE and directed di usion in 10-by-10. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. 71 Figure 7.5: Jitter comparison between EDGE and directed di usion in 10-by-10 grid with di erent delivery ratios. = 1, = 1 in Costp. Tra c rate is 40 packets per second. Packet size is 500 bytes. 72 (a) Throughput with di erent tra c rates (b) End-to-end delay with di erent tra c rates Figure 7.6: Throughput and delay comparison between 3-hop EDGE and 5-hop EDGE in 10-by-10 grid with di erent tra c rates. The error rate of outgoing channels follows uniform distribution with 0.7. = 1, beta = 1 in Costp. Packet size is 500 bytes. 73 (a) (b) Figure 7.7: Throughput and delay comparison with di erent and values in Costp of EDGE in 10-by-10. The error rate of outgoing channels follows uniform distribution with average error rate of 0.7. = 1, = 1 in Costp. Packet size is 500 bytes. Tra c rate is 40 packets per second. 74 Figure 7.8: Throughput of DCHT, EDGE and basic di usion with di erent network sizes. Figure 7.9: Goodput of DCHT, EDGE and basic di usion with di erent network sizes. 75 Figure 7.10: End-to-end delay of DCHT, EDGE and basic di usion with di erent network sizes. Figure 7.11: Number of loss packets per frame in DCHT. There are 29 packets in a large video frame. 76 Figure 7.12: Number of loss packets per frame in EDGE. There are 29 packets in a large video frame. Figure 7.13: Delivery ratio and goodput ratio of DCHT with di erent numbers of descrip- tions/paths. The network size is 77 nodes. 77 Figure 7.14: Throughput and goodput of DCHT with di erent numbers of descrip- tions/paths. The network size is 77 nodes. Figure 7.15: End-to-end delay of DCHT with di erent numbers of descriptions/paths. The network size is 77 nodes. 78 Figure 7.16: Average energy consumption of a single node in the network of DCHT with 3 paths (descriptions), EDGE and basic di usion with di erent network sizes. Figure 7.17: Average energy consumption of a single node in the network of DCHT with di erent number of paths (descriptions). The network size is 77 nodes. 79 Figure 7.18: Extra routing overhead (we only consider NEG RESPONSE) of the whole network of DCHT with di erent number of paths (descriptions) in di erent network sizes. 80 Figure 7.19: Throughput of triangular tessellation topology with di erent sizes. Figure 7.20: End-to-end delay of triangular tessellation topology with di erent sizes. We rst run the application for the triangular tessellation with di erent network sizes as shown in Figure 6.3 and measure the throughput (Figure 7.19) and end-to-end delay (Figure 7.20). The throughput increases rapidly when p increase from 0.1 to 0.5. It achieves the highest throughput when 60% of the nodes do not drop interests. Beyond 60%, the throughput drops because of the extra interference during exploratory data phase when 81 more or all candidate gradients are considered (fewer or no node drop interests). Note that when p = 1:0, it becomes the original directed di usion algorithm and the throughput is lower than the peak, when p = 0:6, which is 20% higher than the original directed di usion. When many nodes drop interests, i.e. p is small, the throughput is lower because the number of candidates is very small. Network with smaller sizes achieves higher throughput since it su ers less from cumulative packet loss. Figure 7.20 shows that end-to-end delay goes up to 80 ms when p = 0:7 or p = 0:8 and drops down after that. The higher delay is due to high tra c when the throughput peaks. Larger networks have longer delay since there are more hops between the source and the sink. Trade-o between throughput and delay is also shown in these two gures. Although we do not have the highest delay when p = 0:7 where throughput is maximum, we believe they re ect the trend that there should be a magic percentage, between 60% and 70% (or 80%), for this topology. Figure 7.21: Percentage of zero throughput, no path built and no interest reaching source of triangular tessellation topology with 77 nodes. 82 One of the shortcomings of probabilistic forwarding is that in some cases no forwarding path for interest, exploratory data or application data, may be found. We analyze the above- mentioned probability phase by phase. In the rst phase, interests may fail to reach the source due to the epidemic ooding. We measure the percentage of such instances in Figure 7.21. If more nodes are updating the gradient table, the percentage of interests reaching the source is monotonically higher. Also, we compare the percentage of cases where no path was built, which includes the cases where no interest reaches the source. Another reason for this might be that interference causes exploratory data to be dropped half way even if interests can reach the source successfully. As a result, it is no surprise to nd that when p = 0:6, more paths are built than when p = 1 (original directed di usion). Percentage of cases with zero throughput (plotted in the same gure) includes the cases where no path is built. When p = 0:6 we not only achieves the highest throughput, but also achieve the highest percentage of successful delivery of application data. Figure 7.22: Throughput of grid topology with di erent sizes. 83 Figure 7.23: End-to-end delay of grid topology with di erent sizes. Figure 7.22 and Figure 7.23 show the throughput and delay in grid topology with di erent network sizes. Delay follows almost the same trend as in the previous topology although the magic percentage is 0.6 here. Throughput looks quite di erent in grid topology and it keeps increasing till all nodes update their gradient tables. The reason is that every node has only four neighbors, which is small and hard to guarantee connectivity. Compared to the previous topology with six neighbors, the product of 6 and 0.6 is approximately 4, which is evidence that a magic number, instead of magic percentage, does exist for the number of neighbors with di erent topologies. Hexagon tessellations with di erent sizes are compared in Figure 7.24 and Figure 7.25 in terms of throughput and end-to-end delay. Throughput keeps increasing with higher percentages of nodes that do not drop interests since the topology has only three neighbors, even smaller than grid topology. The peak of end-to-end delay is p = 0:7 or p = 0:8, which is higher than grid topology at 0.6. The highest delay is due to high tra c level. 84 Figure 7.24: Throughput of hexagon tessellation with 32, 50, 72 nodes. For throughput, p = 0:6 is a breakpoint, beyond which smaller network sizes have larger delay than larger network sizes. We explain this phenomenon as: the probability of larger networks having connectivity increases much more rapidly than that of smaller networks. Figure 7.25 shows that in all network sizes, the highest end-to-end delay occurs at p = 0:7 or p = 0:8 due to the high tra c level. We also test random topology with di erent network sizes (Figure 7.26 and Figure 7.27). Throughput always follows the up and down trend and the network with 60 nodes performs the best. The magic percentage varies between 0.3 and 0.8. Network size of 60 nodes achieves the highest throughput at a higher percentage than that of 80, 90, or 100 nodes because every node has fewer neighbors. The delay graph (Figure 7.27) also indicates the magic number. The delay of 80-node topology keeping increasing till p = 1. Smaller network achieve lower end-to-end delay than larger ones most of the time. Since nodes are uniformly distributed in this random topology, given the transmission range, area of the 85 Figure 7.25: End-to-end delay of hexagon tessellation with 32, 50, 72 nodes. network, and number of nodes, we calculate the average number of neighbors is 3.9 (almost 4) in the 80-node network and 2.9 (almost 3) in the 60-node network. We may give the same explanation as in Figure 7.22 or Figure 7.23 although that is for throughput. To show the magic number for di erent topologies, we put all four of them in the same gure (Figure 7.28 and Figure 7.29). We keep the hop count between the source and the sink the same for them. In Figure 7.28, hexagon tessellation performs the best and random topology the worst. Fewer neighbors cause less interference. Although the average number of neighbors of random topology is 4, the uneven deployment aggravates the side-e ects of interference. An interesting thing is that hexagon tessellation throughput exceeds that of the 7 by 7 grid at p = 0:6. The reason is that it is hard for the hexagonal tessellation topology to maintain connectivity with two few neighbors. Hexagon tessellation also performs best in end-to-end delay. To further test the detrimental e ect of full ooding, we put the throughput (end-to- end delay) of the three regular topologies with di erent sizes in the same gure (Figure 7.30 and Figure 7.31). We still make the hop count between the source and the sink the 86 Figure 7.26: Throughput of random topology with 60, 80, 90, 100 nodes. same for each point in the same column. Hexagon tessellation is a ected less than others in both throughput and end-to-end delay since it has the smallest number of neighbors. The grid topology has the best overall throughput and delay performance since it has the magic number of neighbors. 87 Figure 7.27: End-to-end delay of random topology with 60, 80, 90, 100 nodes. Figure 7.28: Throughput comparison of 4 topologies. 88 Figure 7.29: End-to-end delay comparison of 4 topologies. Figure 7.30: Throughput comparison of 3 topologies with full ooding. 89 Figure 7.31: End-to-end delay comparison of 3 topologies with full ooding. 90 Chapter 8 Conclusions and Future Work We have proposed, implemented, and evaluated three di usion-based protocols for wireless multimedia sensor networks. They improve throughput and maintain reasonably low delay. They select paths with high throughput, mitigate the e ects of interference, and support real-time tra c transmission. The main contributions of our work are listed below. Incorporation of a hybrid metric into directed di usion to increase throughput and maintain low day. Implementation of a multi-path routing protocol in sensor networks to achieve load balancing and error recovery with more accurate error model. Improvement on routing decision by limiting ooding and reducing interference. The protocols we implemented meet the overall goals of video sensor network. The throughput performance of EDGE is on the average 15% better, jitter is 8 times shorter and delay is 20% less than directed di usion for the scenarios we investigated. The main reason is EDGE has more chance of selecting routes with better links, which reduces retransmission (resulting in longer delay), packet dropping (giving rise to lower throughput) and link instability (related with jitter). Not only does EDGE provide better performance, the algorithm can also be easily implemented in the standard directed di usion software to support demanding applications, such as video sensor networks or WMSNs. 91 In DCHT, multiple disjoint paths can achieve high throughput and desirable delay and meet the QoS requirement of multimedia streaming. The use of Wus error model and related mathematical formulas allow us to simulate real-world wireless link loss properly. Our protocol gives twice as much throughput as EDGE and its goodput is even better than that of EDGE. The end-to-end delay of our protocol is 1/4 of that of EDGE in the best case. Basic di usion is not comparable at all since it can hardly receive any packet on time, especially in large networks. For the epidemic ooding algorithm, we observe that di erent topologies have di erent magic percentages of neighbors to achieve optimal routing decision (which is di erent from the connectivity problem). We also identify the magic number of neighbors that can be applied to di erent topologies for optimizing throughput and delay. For all the topologies we have tested, the optimal number of neighbors for achieving the best throughput is four. When the number of neighbors is greater than four, maximum throughput is achieved when some nodes drop interests, i.e. the percentage of nodes not dropping interest is less than 100%. In these cases, when more nodes drop interests, the level of interference is reduced and higher throughput is achieved in the resulting routes. As the number of neighbors de- creases, the optimal percentage of nodes that do not drop interests for achieving maximum throughput moves toward 100%. In most cases, delay is highest when the percentage of nodes not dropping interest is optimal. Random topologies perform worse than topologies with regular tessellation no matter what density we choose because of the uneven distribu- tion of nodes resulting in hotspots with high interference level and di culty for the routing algorithm to estimate interference characteristics. 92 There are many possibilities for the future research work in the area of routing protocols for video sensor networks. Inter- ow interference is hard to formulate and locally detect due to the irregular topology and unpredictable tra c patterns. In this way, interference caused by inter- ow interference is not accurately estimated. Another possibility is to test adapt our EDGE and DCHT protocols to random topologies to achieve equivalently desirable performance in regular topologies such as grid and tessellations. Besides, the incorporation of the epidemic ooding protocol into DCHT is worth investigating. 93 Bibliography [1] V.K. Goyal. Multiple description coding: compression meets the network. Signal Processing Magazine, IEEE, 18(5):74{93, Sep 2001. [2] 21 ideas for the 21st century. Business Week, pp. 78-167, August 1999. [3] Chee-Yee Chong and S.P. Kumar. Sensor networks: evolution, opportunities, and challenges. Proceedings of the IEEE, 91(8):1247{1256, Aug. 2003. [4] V. K Varadan J. W. Gardner. MEMS and Smart Devices. New York: Wiley, 2001. [5] S. Kumar and D. Shepherd. Sensit: Sensor information technology for the war ghter. In Proc. 4th Int. Conf. on Information Fusion, 2001. [6] T.; Chowdury K.R. Akyildiz, I.F.; Melodia. Wireless multimedia sensor networks: A survey. In Wireless Communications, IEEE [see also IEEE Personal Communications] , vol.14, no.6, pp.32-39, 2007. [7] H.264/mpeg-4 avc. http://en.wikipedia.org/wiki/H.264. [8] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva. Directed di usion for wireless sensor networking. IEEE/ACM Trans. Netw., 11(1):2{16, 2003. [9] A.C. Begen, Y. Altunbasak, and O. Ergun. Fast heuristics for multi-path selection for multiple description encoded video streaming. Multimedia and Expo, 2003. ICME ?03. Proceedings. 2003 International Conference on, 1:I{517{20 vol.1, 6-9 July 2003. [10] S. Mao, S.S. Panwar, and Y.T. Hou. On optimal partitioning of realtime tra c over multiple paths. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 4:2325{2336 vol. 4, 13-17 March 2005. [11] S.-J. Lee and M. Gerla. Split multipath routing with maximally disjoint paths in ad hoc networks. Communications, 2001. ICC 2001. IEEE International Conference on, 10:3201{3205 vol.10, 2001. [12] Marc R. Pearlman, Zygmunt J. Haas, Peter Sholander, and Siamak S. Tabrizi. On the impact of alternate path routing for load balancing in mobile ad hoc networks. In MobiHoc ?00: Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, pages 3{10, Piscataway, NJ, USA, 2000. IEEE Press. 94 [13] Deepinder Sidhu, Raj Nair, and Shukri Abdallah. Finding disjoint paths in networks. In SIGCOMM ?91: Proceedings of the conference on Communications architecture & protocols, pages 43{51, New York, NY, USA, 1991. ACM. [14] Shiwen Mao, Shunan Lin, S.S. Panwar, Yao Wang, and E. Celebi. Video transport over ad hoc networks: multistream coding with multipath transport. Selected Areas in Communications, IEEE Journal on, 21(10):1721{1737, Dec. 2003. [15] Yang Wang and Shunan Lin. Error resilient video coding using multiple description motion compensation. Multimedia Signal Processing, 2001 IEEE Fourth Workshop on, pages 441{446, 2001. [16] Wu Xiuchao. Simulate 802.11b channel within ns2. Technical report, SOC, NUS. [17] Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (lar) in mobile ad hoc networks. Wirel. Netw., 6(4):307{321, 2000. [18] Brad Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless networks. In MobiCom ?00: Proceedings of the 6th annual international conference on Mobile computing and networking, pages 243{254, New York, NY, USA, 2000. ACM. [19] Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, and Barry A. Woodward. A distance routing e ect algorithm for mobility (dream). In MobiCom ?98: Proceed- ings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, pages 76{84, New York, NY, USA, 1998. ACM. [20] David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353, 1996. [21] C.E. Perkins and E.M. Royer. Ad-hoc on-demand distance vector routing. Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA ?99. Second IEEE Workshop on, pages 90{100, 25-26 Feb 1999. [22] Zygmunt J. Haas and Marc R. Pearlman. The performance of query control schemes for the zone routing protocol. In SIGCOMM ?98: Proceedings of the ACM SIGCOMM ?98 conference on Applications, technologies, architectures, and protocols for computer communication, pages 167{177, New York, NY, USA, 1998. ACM. [23] Vincent D. Park and M. Scott Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. In INFOCOM ?97: Proceedings of the INFOCOM ?97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications So- cieties. Driving the Information Revolution, page 1405, Washington, DC, USA, 1997. IEEE Computer Society. [24] Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated 95 database maintenance. In PODC ?87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1{12, New York, NY, USA, 1987. ACM. [25] Zygmunt Haas, Joseph Y. Halpern, and Li Li. Gossip-based ad hoc routing. Technical report, Ithaca, NY, USA, 2001. [26] L. Orecchia, A. Panconesi, C. Petrioli, and A. Vitaletti. Localized techniques for broadcasting in wireless sensor networks. In DIALM-POMC ?04: Proceedings of the 2004 joint workshop on Foundations of mobile computing, pages 41{51, New York, NY, USA, 2004. ACM. [27] Ranveer Chandra, Venugopalan Ramasubramanian, and Kenneth Birman. Anonymous gossip: Improving multicast reliability in mobile ad-hoc networks. Technical report, Ithaca, NY, USA, 2001. [28] D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. An empirical study of epidemic algorithms in large scale multihop wireless networks, 2002. [29] K. Kar P. Chaporkar and S. Sarkar. Throughput guarantees through maximal schedul- ing in wireless networks. In Proc. 43rd Allerton Conf. on Commun., Control, and Comp., 2005. [30] Kamal Jain, Jitendra Padhye, Venkata N. Padmanabhan, and Lili Qiu. Impact of interference on multi-hop wireless network performance. In MobiCom ?03: Proceedings of the 9th annual international conference on Mobile computing and networking, pages 66{80, New York, NY, USA, 2003. ACM. [31] Joseph Polastre, Robert Szewczyk, and David Culler. Telos: enabling ultra-low power wireless research. In IPSN ?05: Proceedings of the 4th international symposium on Information processing in sensor networks, page 48, Piscataway, NJ, USA, 2005. IEEE Press. [32] Crossbow technology. http://www.xbow.com/. Accessed July 24, 2007. [33] Pc104.com. http://www.32.com/. Accessed July 24, 2007. [34] Martin Reisslein Satyajayant Mishra and Guoliang Xue. A survey of multimedia streaming in wireless sensor networks. under submission. [35] J. L. Wang D. Agathangelou, B. P. Lo and G.-Z. Yang. Self-con guring video-sensor networks. In Proceedings of the 3rd International Conference on Pervasive Computing, 2005. [36] M. Chu, J. Reich, and F. Zhao. Distributed attention in large scale video sensor networks. Intelligent Distributed Surveilliance Systems, IEE, pages 61{65, 23 Feb. 2004. 96 [37] Video sensor network laboratory at ucr receives federal funding. http://www.newsroom.ucr.edu/cgi-bin/display.cgi?id=1298. Accessed July 24, 2007. [38] Wu-chang Feng Calton Pu Wu-chi Feng, Jonathan Walpole. Moving towards massively scalable video-based sensor networks. In Workshop on New Visions for Large-Scale Networks: Research and Applications, 2001. [39] Maximizing the life of wireless video sensor networks. http://www.ece.vt.edu/news/ar04/video.html. Accessed July 24, 2007. [40] Blackburn M. Kogut, G. and H.R. Everett. Using video sensor networks to command and control unmanned ground vehicles. In AUVSI Unmanned Systems in International Security 2003 (USIS 03), 2003. [41] Wireless multimedia sensor networks. http://www.ece.osu.edu/ ekici/. Accessed July 24, 2007. [42] J. Konrad T.D.C. Little, P. Ishwar. A wireless video sensor network for autonomous coastal sensing. In Proc. Conference on Coastal Environmental Sensing Networks, (CESN 2007), 2007. [43] Quality of service(qos) for wireless sensor networks. http://cobweb.ecn.purdue.edu/RVL/Projects/SensorNetworksQoS/index.htm. [44] S. Kumar F. Hu. Multimedia query with qos considerations for wireless sensor networks in telemedicine. In Proc. of Society of Photo-Optical Insrumentation Engineers ?Intl. Conf. on Internet Multimedia Management Systems, 2003. [45] L. Savidge, Huang Lee, H. Aghajan, and A. Goldsmith. Qos-based geographic routing for event-driven image sensor networks. Broadband Networks, 2005 2nd International Conference on, pages 991{1000 Vol. 2, 3-7 Oct. 2005. [46] Chenyang Lu, Brian M. Blum, Tarek F. Abdelzaher, John A. Stankovic, and Tian He. Rap: A real-time communication architecture for large-scale wireless sensor networks. Technical report, Charlottesville, VA, USA, 2002. [47] A spatiotemporal communication protocol for wireless sensor networks. IEEE Trans. Parallel Distrib. Syst., 16(10):995{1006, 2005. Member-Tian He and Fellow-John A. Stankovic and Member-Chenyang Lu and Member-Tarek F. Abdelzaher. [48] Mmspeed: Multipath multi-speed protocol for qos guarantee of reliability and timeli- ness in wireless sensor networks. IEEE Transactions on Mobile Computing, 5(6):738{ 754, 2006. Student Member-Emad Felemban and Member-Chang-Gun Lee and Member-Eylem Ekici. 97 [49] Douglas S. J. De Couto, Daniel Aguayo, Benjamin A. Chambers, and Robert Morris. Performance of multihop wireless networks: shortest path is not enough. SIGCOMM Comput. Commun. Rev., 33(1):83{88, 2003. [50] Charles E. Perkins and Pravin Bhagwat. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In SIGCOMM ?94: Proceedings of the conference on Communications architectures, protocols and applications, pages 234{244, New York, NY, USA, 1994. ACM. [51] Richard Draves, Jitendra Padhye, and Brian Zill. Comparison of routing metrics for static multi-hop wireless networks. In SIGCOMM ?04: Proceedings of the 2004 confer- ence on Applications, technologies, architectures, and protocols for computer commu- nications, pages 133{144, New York, NY, USA, 2004. ACM. [52] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high- throughput path metric for multi-hop wireless routing. Wirel. Netw., 11(4):419{434, 2005. [53] Richard Draves, Jitendra Padhye, and Brian Zill. Routing in multi-radio, multi-hop wireless mesh networks. In MobiCom ?04: Proceedings of the 10th annual international conference on Mobile computing and networking, pages 114{128, New York, NY, USA, 2004. ACM. [54] J. Park and S. Kasera. Expected data rate: an accurate high-throughput path met- ric for multi-hop wireless routing. In Proc. of second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2005. [55] C. Chandler J. Tang, G. Xue. Interference-aware routing in multihop wireless networks using directional antennas. In Proceedings of IEEE INFOCOM, 2005. [56] Jian Tang, Guoliang Xue, and Christopher Chandler. Interference-aware routing and bandwidth allocation for qos provisioning in multihop wireless networks: Research articles. Wirel. Commun. Mob. Comput., 5(8):933{943, 2005. [57] Csaba D. Tth Yunhong Zhou Chiranjeeb Buragohain, Subhash Suri. Improved through- put bounds for interference-aware routing in wireless networks. In Proc. 13th Comput- ing and Combinatorics Conference, 2007. [58] G. Hiertz B. Walke E. Weiss, O. Klein. Capacity and interference aware ad hoc routing in multi-hop networks. In Proceedings of 12th European Wireless conference, 2006. [59] Fengguang An Liran Ma, Qian Zhang and Xiuzhen Cheng. Diar: A dynamic in- terference aware routing protocol for ieee 802.11-based mobile ad hoc networks. In International Conference on Mobile Ad-hoc and Sensor Networks (MSN) 2005, LNCS, 2005. 98 [60] H. Mahmood and C. Cornaniciu. Interference aware routing for cdma wireless ad hoc networks. Military Communications Conference, 2005. MILCOM 2005. IEEE, pages 1059{1063 Vol. 2, 17-20 Oct. 2005. [61] Tamer ElBatt and Timothy Andersen. Cross-layer interference-aware routing for wire- less multi-hop networks. In IWCMC ?06: Proceedings of the 2006 international con- ference on Wireless communications and mobile computing, pages 153{158, New York, NY, USA, 2006. ACM. [62] Dang-Quan Nguyen and Pascale Minet. Interference-aware qos olsr for mobile ad- hoc network routing. In SNPD-SAWN ?05: Proceedings of the Sixth International Conference on Software Engineering, Arti cial Intelligence, Networking and Paral- lel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Networks, pages 428{435, Washington, DC, USA, 2005. IEEE Computer So- ciety. [63] Ahmed Bader and Eylem Ekici. Throughput and delay optimization in interference- limited multihop networks. In MobiHoc ?06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, pages 274{285, New York, NY, USA, 2006. ACM. [64] Y. Fang and B. McDonald. Dynamic codeword routing (dcr): A cross-layer approach for performance enhancement of general multi-hop wireless routing. In 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks 2004 IEEE SECON 2004, 2004. [65] P. Gupta and P.R. Kumar. The capacity of wireless networks. Information Theory, IEEE Transactions on, 46(2):388{404, Mar 2000. [66] A.El. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-o in wireless networks. INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 1:{475, 7-11 March 2004. [67] Shunan Lin, Shiwen Mao, Yao Wang, and S. Panwar. A reference picture selection scheme for video transmission over ad-hoc networks using multiple paths. Multimedia and Expo, 2001. ICME 2001. IEEE International Conference on, pages 96{99, 22-25 Aug. 2001. [68] S. Panwar S. S. Wang Y. Mao, S. Lin. Reliable transmission of video over ad hoc net- works using automatic repeat request and multipath transport. In EEE VEHICULAR TECHNOLOGY CONFERENCE 2001, CONF 54; VOL 2, pages 615-619, 2001. [69] Rita Cucchiara. Multimedia surveillance systems. In VSSN ?05: Proceedings of the third ACM international workshop on Video surveillance & sensor networks, pages 3{10, New York, NY, USA, 2005. ACM. 99 [70] Alan Mainwaring, David Culler, Joseph Polastre, Robert Szewczyk, and John Ander- son. Wireless sensor networks for habitat monitoring. In WSNA ?02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pages 88{97, New York, NY, USA, 2002. ACM. [71] Jinyang Li, Charles Blake, Douglas S.J. De Couto, Hu Imm Lee, and Robert Morris. Capacity of ad hoc wireless networks. In MobiCom ?01: Proceedings of the 7th annual international conference on Mobile computing and networking, pages 61{69, New York, NY, USA, 2001. ACM. [72] J. J. Lemmon. Wireless link statistical bit error model. Technical report, NTIA Report 02-394, 2002. [73] Shuang Li, Alvin Lim, Santosh Kulkarni, and Cong Liu. Edge: A routing algorithm for maximizing throughput and minimizing delay in wireless sensor networks. Military Communications Conference, 2007. MILCOM 2007. IEEE, pages 1{7, 29-31 Oct. 2007. [74] Shiwen Mao, D. Bushmitch, S. Narayanan, and S.S. Panwar. Mrtp: a multi ow real- time transport protocol for ad hoc networks. Multimedia, IEEE Transactions on, 8(2):356{369, April 2006. [75] J. Kleinberg and E. Tardos. Algorithm Design. Pearson-Addison Wesley, 2005. [76] http://aima.cs.berkeley.edu/newchap05.pdf. [77] P. Norvig S. Russell. Arti cial Intelligence: A Modern Approach. Prentice Hall, 1995. [78] Gang Feng, K. Makki, N. Pissinou, and C. Douligeris. An e cient approximate al- gorithm for delay-cost-constrained qos routing. Computer Communications and Net- works, 2001. Proceedings. Tenth International Conference on, pages 395{400, 2001. [79] D.B. West. Introduction to Graph Theory. Prentice-Hall, 1996. [80] Z. Ye, S.V. Krishnamurthy, and S.K. Tripathi. A framework for reliable routing in mobile ad hoc networks. INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 1:270{280 vol.1, 30 March-3 April 2003. [81] Jun Sun, Wen Gao, and Qingming Huang. A novel fgs base-layer encoding model and weight-based rate adaptation for constant-quality streaming. In ICIG ?04: Proceed- ings of the Third International Conference on Image and Graphics, pages 373{376, Washington, DC, USA, 2004. IEEE Computer Society. [82] M.T. Ko R.I Chang, M. Chen and J.M. Ho. Optimizations of stored vbr video trans- mission on cbr channel. In SPIE VVDC, 1997. 100 [83] C.-F. Chiasserini and E. Magli. Energy consumption and image quality in wireless video-surveillance networks. Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on, 5:2357{2361 vol.5, 15-18 Sept. 2002. [84] D. Ferrari. Client requirements for real-time coomunication services. IEEE Communi- cations, 1990. [85] Zheng Wang and Jon Crowcroft. Analysis of burstiness and jitter in real-time communi- cations. In SIGCOMM ?93: Conference proceedings on Communications architectures, protocols and applications, pages 13{19, New York, NY, USA, 1993. ACM. [86] Seungjoon Lee, Bobby Bhattacharjee, and Suman Banerjee. E cient geographic rout- ing in multihop wireless networks. In MobiHoc ?05: Proceedings of the 6th ACM inter- national symposium on Mobile ad hoc networking and computing, pages 230{241, New York, NY, USA, 2005. ACM. [87] http://trace.eas.asu.edu/. [88] Yogesh Sankarasubramaniam, Ozg ur B. Akan, and Ian F. Akyildiz. Esrt: event-to- sink reliable transport in wireless sensor networks. In MobiHoc ?03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 177{188, New York, NY, USA, 2003. ACM. [89] A. La Corte, A. Lombardo, S. Palazzo, and G. Schembra. A feedback approach for jitter and skew enforcement in multimedia retrieval services. Global Telecommunications Conference, 1995. GLOBECOM ?95., IEEE, 2:790{794 vol.2, 14-16 Nov 1995. 101