Routing in ad-hoc networks using minimum connected dominating sets Export

@proceedings{citeulike:3006294, abstract = {We impose a virtual backbone structure on the ad-hoc network, in order to support unicast, multicast, and fault-tolerant routing within the ad-hoc network. This virtual backbone differs from the wired backbone of cellular networks in two key ways: (a) it may change as nodes move, and (b) it is not used primarily for routing packets or flows, but only for computing and updating routes. The primary routes for packets and flows are still computed by a shortest-paths computation; the virtual backbone can, if necessary provide backup routes to handle interim failures. Because of the dynamic nature of the virtual backbone, our approach splits the routing problem into two levels: (a) find and update the virtual backbone, and (b) then find and update routes. The key contribution of this paper is to describe several alternatives for the first part of finding and updating the virtual backbone. To keep the virtual backbone as small as possible we use an approximation to the minimum connected dominating set (MCDS) of the ad-hoc network topology as the virtual backbone. The hosts in the MCDS maintain local copies of the global topology of the network, along with shortest paths between all pairs of nodes}, author = {Das, B. and Bharghavan, V.}, booktitle = {Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on}, citeulike-article-id = {3006294}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ICC.1997.605303}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=605303}, doi = {10.1109/ICC.1997.605303}, journal = {Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on}, keywords = {ecds-journal}, pages = {376--380 vol.1}, posted-at = {2008-07-15 17:22:06}, priority = {2}, title = {Routing in ad-hoc networks using minimum connected dominating sets}, url = {http://dx.doi.org/10.1109/ICC.1997.605303}, volume = {1}, year = {1997} }

TY - CONF ID - citeulike:3006294 L3 - citeulike-article-id:3006294 N2 - We impose a virtual backbone structure on the ad-hoc network, in order to support unicast, multicast, and fault-tolerant routing within the ad-hoc network. This virtual backbone differs from the wired backbone of cellular networks in two key ways: (a) it may change as nodes move, and (b) it is not used primarily for routing packets or flows, but only for computing and updating routes. The primary routes for packets and flows are still computed by a shortest-paths computation; the virtual backbone can, if necessary provide backup routes to handle interim failures. Because of the dynamic nature of the virtual backbone, our approach splits the routing problem into two levels: (a) find and update the virtual backbone, and (b) then find and update routes. The key contribution of this paper is to describe several alternatives for the first part of finding and updating the virtual backbone. To keep the virtual backbone as small as possible we use an approximation to the minimum connected dominating set (MCDS) of the ad-hoc network topology as the virtual backbone. The hosts in the MCDS maintain local copies of the global topology of the network, along with shortest paths between all pairs of nodes JF - Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on EP - 380 vol.1 TI - Routing in ad-hoc networks using minimum connected dominating sets VL - 1 T2 - Communications, 1997. ICC 97 Montreal, 'Towards the Knowledge Millennium'. 1997 IEEE International Conference on SP - 376 KW - ecds-journal AU - Das, B AU - Bharghavan, V PY - 1997/// UR - http://dx.doi.org/10.1109/ICC.1997.605303 ER -