Hierarchical routing using k-SPR
MetadataShow full item record
The goal of our research is to create an improved routing protocol for Ad-Hoc Wireless networking. We began our research by studying a protocol developed by two Drake students, Tiffany Meredith and Jennifer Ehrlich, which they named k-SPR, and that standard is based loosely on AODV standards. Our protocol was developed using their framework as a basis for our changes and additions. We want to develop a protocol that will pick routers such that those routers are more likely to experience a lot of traffic and also to make router selection a hierarchical process. The method we use to determine the traffic density of any given node is to compute its covering number, which is the number of node pairs that node covers. A node pair in a k-SPR set is a pair of nodes that are k+1 hops apart, and a node covers that pair if it is along the shortest path between the node pair, hence the name Shortest Path Routing (SPR). A hierarchical system of choosing routers is then implemented by applying a similar method to the resulting set of nodes and selecting super routers based on similar criteria to those used for routers. During our research, we grappled with the issue of generalizing a hierarchical router selection algorithm. We decided that generalizing hierarchical router selection is complicated by the AODV packet header system and is also limited functionally by the number of nodes in the set, sometimes requiring an increase of millions or billions of nodes, in order to necessitate another tier in the hierarchy. Further research should include a close analysis of data resulting from our studies and strive towards a greater understanding of the ‘shape’ of the network that is developed when choosing routers.