A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks

Ad Hoc无线网络中基于支配集的路由方案

• 批准号: 0073736
• 负责人: Jie Wu
• 金额: $ 18.2万
• 依托单位: Florida Atlantic University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-06-15 至 2005-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0073736&HistoricalAwards=false
• 关键词: Dominating; Set; Based; Routing; Scheme

Recent advances in technology have provided portable computers with wireless interfaces thatallow networked communication among mobile users. The resulting computing environment, whichis often referred to as mobile computing, no longer requires users to maintain a fixed and universallyknown position in the network and enables almost unrestricted mobility. An ad hoc wirelessnetwork is a special type of wireless mobile network in which a collection of mobile hosts withwireless network interfaces may form a temporary network, without the aid of any establishedinfrastructure or centralized administration. Efficient routing among a set of mobile hosts (also called nodes) is one of the most importantfunctions in ad hoc wireless networks. Routing based on a connected dominating set is a promisingapproach, where the search space for a route is reduced to the nodes in the set. A set is dominating ifall the nodes in the system are either in the set or are neighbors of nodes in the set. In this proposal,the researchers study a simple and efficient distributed algorithm for calculating a connected dominating setin an ad hoc wireless network, where connections of nodes are determined by their geographicaldistances and the corresponding graph is called a unit graph. A reduced graph is then inducedfrom the connected dominating set and the routing process is restricted to this reduced graph. The researcher's preliminary results on random unit graphs are very promising in generating a small reduced graph in a way faster than existing methods. The goals of the proposed research are: (1) Enhance the process (also called the markingprocess) of determining a connected dominating set of a unit graph. (2) Complete the update/re-calculation algorithm for the connected dominating set when the topology of the ad hoc wirelessnetwork changes dynamically. (3) Extend the proposed approach to a hierarchical structure, wherethe marking process is applied on the reduced graph to generate a reduced graph of the reducedgraph. The hierarchical structure is obtained by applying the marking process iteratively. (4) Selectan appropriate routing protocol for the reduced graph. This scheme could be a proactive routing(such as various extended link state and distance vector routing protocols), a reactive routing (alsocalled on demand), or a combination of both. (5) Explore the possibility of combining dominatingset information and location information provided by a Global Positioning System (GPS) to derivea better routing scheme. (6) Integrate different components and fine tune the system through anempirical study based on a set of well-defined quantitative performance metrics.

技术的最新进展已经为便携式计算机提供了允许移动的用户之间的联网通信的无线接口。 由此产生的计算环境，通常被称为移动的计算，不再需要用户在网络中保持一个固定的和普遍已知的位置，并使几乎不受限制的移动性。 adhoc无线网络是一种特殊类型的无线移动的网络，在这种网络中，具有无线网络接口的移动的主机的集合可以形成一个临时网络，而不需要任何已建立的基础设施或集中管理。 在一组移动的主机（也称为节点）之间进行有效的路由是adhoc无线网络中最重要的功能之一。 基于连通支配集的路由选择是一种很有前途的方法，它将路由的搜索空间缩减到支配集中的节点。 一个集合是支配的，如果系统中的所有节点要么在集合中，要么是集合中节点的邻居。 在这个提议中，研究人员研究了一种简单有效的分布式算法，用于计算ad hoc无线网络中的连通支配集，其中节点的连接由其地理距离确定，相应的图被称为单位图。 然后从连通支配集导出一个约简图，并将路由过程限制在这个约简图上。 研究人员的随机单位图的初步结果是非常有前途的生成一个小的减少图的方式比现有的方法更快。 本文的研究目标是：（1）改进确定单位图连通支配集的过程（也称为标记过程）。 (2)完成了adhoc网络拓扑结构动态变化时连通支配集的更新/重新计算算法。 (3)将所提出的方法扩展到一个层次结构，其中标记过程被应用于约简图，以生成约简图的约简图。 通过迭代地应用标记过程来获得分层结构。 (4)为简化图选择合适的路由协议。 该方案可以是主动路由（如各种扩展链路状态和距离矢量路由协议）、被动路由（也称为按需路由）或两者的组合。 (5)探索将全球定位系统（GPS）提供的主导集信息和位置信息相结合以得出更好的路由方案的可能性。 (6)通过基于一组定义明确的定量性能指标的实证研究，集成不同的组件并微调系统。