Year of Publication

2008

Document Type

Dissertation

College

Engineering

Department

Computer Science

First Advisor

Mukesh Singhal

Abstract

In Mobile Ad Hoc Networks (MANETs), nodes depend on each other for routing and forwarding packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and may not be willing to help other nodes. Such selfish behavior poses a real threat to the proper functioning of MANETs. One way to foster node cooperation is to introduce punishment for selfish nodes. Based on neighbor-monitoring techniques, a fully distributed solution to detect, punish, and re-admit selfish nodes, is proposed here. This solution provides nodes the same opportunity to serve/and be served by others. A light-weight solution regarding battery status is also proposed here. This solution requires neighbor monitoring only when necessary, thereby saving nodes battery power. Another effective way to solve the selfish-node problem is to reward nodes for their service according to their cost. To force nodes to show their true cost, truthful protocols are needed. A low overhead truthful routing protocol to find optimal routes is proposed in this thesis. The most prominent feature of this protocol is the reduction of overhead from existing solutions O(n3) to O(n2). A light-weight scalable truthful routing protocol (LSTOP) is further proposed, which finds near-least-cost paths in dense networks. LSTOP reduces overhead to O(n) on average, and O(n2) in worst case scenarios. Multiple path routing protocols are an effective alternative to single path routing protocols. A generic mechanism that can turn any table-driven multipath routing protocol into a truthful one, is outlined here. A truthful multipath routing protocol (TMRP), based on well-known AOMDV protocol, is presented as an example. TMRP incurs an only 2n message overhead for a route discovery, and can also achieve load balancing without compromising truthfulness. To cope with the selfish-node problem in the area of position-based routing, a truthful geographic forwarding (TGF) algorithm is presented. TGF utilizes three auction-based forwarding schemes to stimulate node cooperation. The truthfulness of these schemes is proven, and their performance is evaluated through statistical analysis and simulation studies.

Share

COinS