טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentDrabkin Vadim
SubjectDependable Communication Protocols in Ad-Hoc
Networks
DepartmentDepartment of Computer Science
Supervisor Professor Roy Friedman
Full Thesis textFull thesis text - English Version


Abstract

Mobile Ad-Hoc Networks (MANETs) are networks of mobile devices that are formed in an ad-hoc manner. The devices that participate in such networks have wireless communication capabilities with limited range transmitters, and thus can directly communicate with other devices that are within their range. Some of the devices occasionally volunteer to forward some of the messages they receive, or in other words, act as routers, thereby forming a multi-hop network with a wider reach. Yet, there is no fixed infrastructure, the network is continuously changing, and routers are elected on demand. In other words, the networking issues are handled in an ad-hoc manner.


Unlike infrastructure based networks in which routers are usually considered to be trusted entities, in ad-hoc networks routing is performed by the devices themselves. Thus, there is a high risk that some of the nodes of an ad-hoc network would not respect the networking protocols. Therefore, the possibility of having faulty nodes in the system motivates the development of reliable broadcast protocols for ad-hoc networks.


Group communication systems have proven themselves as powerful middleware for building reliable networked applications in wired environments. These systems relieve programmers from many complex issues involved in designing such applications, allowing them to focus on the essential aspects of the application being developed, resulting in faster development time and fewer bugs.


In this thesis we present a novel ReliAble ProbabIlistic Dissemination protocol, called RAPID, for mobile wireless ad-hoc networks, which tolerates message omissions, node crashes, and selfish behavior. The protocol employs a combination of probabilistic forwarding with deterministic corrective measures. Since the protocol only relies on local computations and probability, it is highly resilient to mobility and failures. By adding authentication, it can even be made malicious tolerant.


As additional contribution, we present an efficient overlay based reliable broadcast protocol for ad hoc networks. The use of an overlay results in a significant reduction in the number of messages. The protocol overcomes different types of nodes failures by combining digital signatures, gossiping of message signatures, and failure detectors.


Last, we present and explore a reliable group communication system in wireless mobile ad-hoc networks. The objective is to enable easy, efficient, and correct development of applications in this environment. The main challenge was to develop protocols that are resilient to attacks by malicious nodes, yet are scalable, robust and efficient. This included adapting several existing protocols as well as developing new membership maintenance mechanisms, followed by a thorough benchmarking of the system.