Efficient composition and dissemination of link state information for proactive routing through energy cost based beta-skeletons

Proactive routing protocols are especially appropriate for mission-critical systems, including those employed for military purposes. However, such protocols are prone to excessive exchange of connectivity information (CI) in mobile ad hoc networks, potentially monopolizing communication channels and throttling application traffic. There are two factors that determine the traffic load created by CI exchange - its content and the dissemination strategy. Several methods exist to restrain the latter with little additional computation or communication overhead; these include MPR/OLSR, HSLS, and FSR. Controlling content however is a more difficult problem, traditionally solved by clustering or hierarchical routing methods that sacrifice path optimality and often require considerable coordination among nodes, resulting in high communication overhead. We propose a mechanism that restrains both CI content and dissemination with insignificant overhead. It is based on b-skeletons, a class of spanners that can be constructed based on restricted local information, while guaranteeing global connectivity with a bounded edge complexity and spanning ratio. The main contributions of this work are: (J) a localized and distributed method for constructing b-skeletons based on the energy cost of network links: (2) the derivation of bounds on the edge complexity and energy spanning ratio of such b-skeletons; (3) a CI exchange protocol that utilizes b-skeletons to restrains CI content and disseminate it efficiently, while preserving the energy-optimal routes. The protocol is shown to result in considerable efficiency gains over a wide range of operating conditions including variable node mobility, network size, and node density.