Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer Ivan Stojmenovic ivan@site.uottawa.ca www.site.uottawa.ca/~ivan Abstract We present guidelines on how to design network layer protocols when the unit disk graph model is replaced with a more realistic physical layer model. Instead of merely using the transmission radius in the unit disk graph model, physical, MAC and network layers share the information about a bit and/or packet reception probability as a function of distance between nodes. We assume that all nodes use the same transmission power for sending messages, and that a packet is received when all its bits are correctly received. The MAC layer reacts to this probabilistic reception information by adjusting the number of acknowledgements and/or retransmissions. We observe that an optimal route discovery protocol cannot be based on a single retransmission by each node, as current AODV/DSR standard candidates suggest, because such a search may fail to reach the destination or fail to find the optimal path. Next, we discuss that gaining neighbour knowledge information with ?hello? packets is not a trivial protocol. We describe localized position based routing protocols which aim to minimize the expected hop count (in case of hop by hop acknowledgements and bit rate being independent from distance) or maximize the probability of delivery (when acknowledgements are not sent). We propose a guideline for the design of greedy position based routing protocols with known destination locations. The node currently holding the message will forward it to a neighbour (closer to the destination than itself) that minimizes the ratio of cost over progress, where the cost measure depends on the assumptions and metrics used, while the progress measures the difference in distances to the destination. This is a preliminary contribution toward the development of network layer protocols that will match the assumptions and criteria already used in simulators and ultimately in real equipment. Ivan Stojmenovic Short biography (November 2004) ivan@site.uottawa.ca www.site.uottawa.ca/~ivan Ivan Stojmenovic received Ph.D. degree in mathematics in 1985. He earned a third degree prize at International Mathematics Olympiad for high school students in 1976. He held regular or visiting positions in Serbia (Institute of Mathematics, University of Novi Sad, 1980-1987), Japan (Electrotechnical Laboratory, Tsukuba, 1985/86), USA (Washington State University, Pullman, WA, and University of Miami, FL, 1987/88), Canada (University of Ottawa, since 1988), France (Amiens 1998, Lille 2002, 2003) and Mexico (DISCA, IIMAS, Universidad Nacional Autonoma de Mexico, 2000/02). He is currently Full professor of computer science at the School of Information Technology and Engineering, University of Ottawa. He published over 200 different papers in referred journals and conferences, and edited ?Handbook of Wireless Networks and Mobile Computing? (Wiley, 2002), and co-edited ?Mobile Ad Hoc Networking? (IEEE Press, 2004). A list of his most significant publications can be seen at www.site.uottawa.ca/~ivan . He collaborated with over 80 co-authors with Ph.D. and a number of graduate students from 20 different countries. His past research interests include parallel computing, multiple-valued logic, evolutionary computing, neural networks, combinatorial algorithms, computational geometry, graph theory, computational chemistry, image processing, programming languages, and computer science education. His current research interests include wireless ad hoc, sensor and cellular networks. One of his articles, on broadcasting in ad hoc wireless networks, was recognized as *Fast Breaking Paper*, for October 2003 (as the only one for the entire computer science), by /Thomson ISI Essential Science Indicators http://esi-topics.com/fbp/fbp-october2003.html. /His article on localized broadcasting with directional antennas received *Best Paper Award*, at the 9th IFIP Int. Conference on Personal Wireless Communications PWC, September 21-23, 2004, Delft, The Netherlands. He presented several tutorials on ad hoc and sensor networks, and gave a number of invited talks. He was Director of Ottawa-Carleton Institute for Computer Science (2002-2004) and wrote an article ?Advice for writing theses and papers? (on his web site www.site.uottawa.ca/~ivan ), containing guidelines for writing and publishing research results. He is currently a managing editor of Journal of Multiple-Valued Logic and Soft Computing (received Certificate of Appreciation from IEEE Computer Society in 2002 for establishing and maintaining the journal), and editor of several journals including IEEE Transactions on Parallel and Distributed Systems, Parallel Processing Letters, International Journal of High Performance Computing and Networking (IJHPCN), International Journal of Wireless and Mobile Computing (IJWMC), and International Journal of Distributed Sensor Networks (IJDSN; Taylor and Francis). He guest edited recently special issues in several journals including IEEE Computer Magazine, IEEE Networks, Wireless Communications and Mobile Computing, Telecommunication Systems, Cluster Computing, International Journal of Foundations of Computer Science. He was also program vice-chair at IEEE MASS, program co-chair at IFIP WONS, workshop co-chair at IEEE ICDCS in 2003-2005; IEEE ICDCS 2003; HICSS, 2000, 2002, 2003; ICPDS, Taiwan, 2002; ICPP, Toronto, 2000; SSGRR, Italy, 2002, and was program committee member at a number of conferences, such as IEEE INFOCOM 2005, IEEE ICPCS 2004, IFIP Medhoc 2004, IEEE ICPADS 2004, IEEE IPSN 2004, IEEE ISCC 2004, IFIP PWC 2003, AdHocNow 2202-3; IFIP Networking 2002, 2004; IEEE ICPDS 2001; IEEE ICCCN 2000-3 and others and a number of workshops.