دانلود مقاله ترجمه شده بررسی الگوریتم های مسیر یابی شبکه های مش و اد هاک بی سیم – مجله الزویر

بخشی از ترجمه:

امروزه تکنولوژی شبکه ی بی سیم، به عنوان یک جایگزین بسیار ارزان برای ایجاد شبکه های انجمنی و متحد مورد توسعه قرار گرفته است(در مقایسه با شبکه های مرسوم سیمی). علیرقم اینکه چنین شبکه هایی از نظر اقتصادی بسیار مقرون به صرفه هستند، بهره وری های عملیاتی متعددی را نیز اعم از قابلیت پویایی و راحتی برای کاربر نهایی ارائه می-دهد. یک شبکه ی بی سیم میتواند در هر دو مد Ad-Hoc و مد زیر ساختار عمل کند. در مد اول، کاربر حالت خود مدیرانه داشته و در مد دوم نیز از یک منبع معتبر برای مدیریت شبکه استفاده می شود، مانند روتر های بی سیم، نقاط دسترسی و ایستگاه های پایه. یک شبکه ی Ad-Hoc عموماٌ از مالتی هاپ نیز پشتیبانی می کند، به گونه ای که بسته ی داده ای میتواند از طریق چندین هاپ عبور کرده تا به مقصد برسد. از بین شبکه های مبتنی بر زیر ساختار، یک شبکه ی مِش بی سیم(به صورت مجموعه ای از روتر های بی سیم قرار گرفته شده در نقاط استراتژیک، به منظور فراهم کردن اتصالات کلی شبکه) نیز قابلیت انعطافی را برای این مالتی هاپ فراهم می سازد. بنابراین، اینکه بسته های چطور می توانند به صورت کارآمد از طریق شبکه ی بی سیم به مقصد برسند، مسئله ی بسیار مهم است.
یک سری روش های مسیریابی بی سیم تا به امروز پیشنهاد شده است. در این مقاله، مطالعه ای بر روی الگوریتم های مسیریابی پیشنهاد شده برای شبکه های بی سیم ارائه خواهد شد. بر خلاف مسیریابی در شبکه های سیمی، مسیریابی بی سیم با چالش هایی مانند تداخل در بین سایر انتقالات، مشخصه های متغیر کانال و … روبروست. در یک شبکه ی بی سیم، الگوریتم های مسیریابی ، به دسته بندی های متعددی اعم از الگوریتم های مسیریابی جغرافیایی، Geo-Casting، سلسله مراتبی، چند مسیری، مبتنی بر انرژی باقیمانده و هیبریدی(ترکیبی) تقسیم می شوند. به دلیل مطالعات زیادی که در زمینه ی این الگوریتم ها صورت گرفته است، ما یک سری محدودی از آنها را برای بازبینی انتخاب کرده ایم. در این مطالعه، به بررسی یک بازبینی جامعی از الگوریتم های مسیریابی در این دسته بندی ها پرداخته شده است.
در گام های اولیه ی توسعه ی شبکه های بی سیم، الگوریتم های پایه ای برای مسیریابی، مانند مسیریابی منبع پویا(DSR) ، مسیریابی بردار فاصله مبتنی بر تقاضا(AODV) ، با هدف کنترل ترافیک در شبکه طراحی شدند. اگرچه پژوهش ها نشان داد که بکار گیری این الگوریتم های ساده به صورت مستقیم بر روی چنین شبکه هایی، منجر به بروز مشکلاتی به صورت زیر خواهد شد:
• جریان زیاد در شبکه،
• مجموعه ی خالی از همسایه ها در روش ارسال حریصانه،
• آدرس دهی تخت،
• اطلاعات توزیع شده ی انبوه،
• مصرف زیاد انرژی،
• تداخل و ..
بنابراین یک سری الگوریتم هایی ارائه شدند که نوع توسعه یافته ای از این الگوریتم های اولیه بودند. از این رو قصد داریم به مطالعه ی این الگوریتم ها بپردازیم، که البته با محیط های بی سیم سازگاری داشته و می توانند بر مشکلات مطرح شده غلبه کنند.

بخشی از مقاله انگلیسی:

abstract Wireless networking technology is evolving as an inexpensive alternative for building federated and community networks (relative to the traditional wired networking approach). Besides its cost-effectiveness, a wireless network brings operational efficiencies, namely mobility and untethered convenience to the end user. A wireless network can operate in both the ‘‘Ad-Hoc’’ mode, where users are self-managed, and the ‘‘Infrastructure’’ mode, where an authority manages the network with some Infrastructure such as fixed wireless routers, base stations, access points, etc. An Ad-Hoc network generally supports multi-hopping, where a data packet may travel over multiple hops to reach its destination. Among the Infrastructure-based networks, a Wireless Mesh Network (with a set of wireless routers located at strategic points to provide overall network connectivity) also provides the flexibility of multi-hopping. Therefore, how to route packets efficiently in wireless networks is a very important problem. A variety of wireless routing solutions have been proposed in the literature. This paper presents a survey of the routing algorithms proposed for wireless networks. Unlike routing in a wired network, wireless routing introduces new paradigms and challenges such as interference from other transmissions, varying channel characteristics, etc. In a wireless network, routing algorithms are classified into various categories such as Geographical, Geo-casting, Hierarchical, Multi-path, Power-aware, and Hybrid routing algorithms. Due to the large number of surveys that study different routing-algorithm categories, we select a limited but representative number of these surveys to be reviewed in our work. This survey offers a comprehensive review of these categories of routing algorithms. In the early stages of development of wireless networks, basic routing algorithms, such as Dynamic Source Routing (DSR) and Ad-Hoc On-demand Distance Vector (AODV) routing, were designed to control traffic on the network. However, it was found that applying these basic routing algorithms directly on wireless networks could lead to some issues such as large area of flooding, Greedy Forwarding empty set of neighbors, flat addressing, widely-distributed information, large power consumption, interference, and load-balancing problems. Therefore, a number of routing algorithms have been proposed as extensions to these basic routing algorithms to enhance their performance in wireless networks. Hence, we study the features of routing algorithms, which are compatible with the wireless environment and which can overcome these problems. 2011 Elsevier B.V. All rights reserved. 1. Introduction 1.1. Wireless network Among the various access networking technologies, wireless networking has evolved as a cost-effective alternative to the traditional wired access networking approaches, 1389-1286/$ – see front matter 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.comnet.2011.10.011 ⇑ Corresponding author. Tel.: +1 530 752 5129; fax: +1 530 752 4767. E-mail addresses: emalotaibi@ucdavis.edu (E. Alotaibi), bmukherjee@ucdavis.edu (B. Mukherjee). Computer Networks 56 (2012) 940–965 Contents lists available at SciVerse ScienceDirect Computer Networks journal homepage: www.elsevier.com/locate/comnet e.g., Digital Subscriber Line (DSL) and cable modem (CM). Being an untethered medium, using a wireless network, wiring need not reach all the way to the end users; thus, a wireless network saves on the Infrastructure cost and offers user mobility. A wireless local area network (WLAN) can operate in both the ‘‘Ad-Hoc’’ and the ‘‘Infrastructure’’ modes. 1.2. Wireless Ad-Hoc Network Fig. 1 shows a wireless Ad-Hoc network, which is a decentralized network where each node (end-user node) is able to forward data packets for other nodes. The main objective of an Ad-Hoc network is to maintain the node’s connectivity and reliably transport the data packets. In addition, each node dynamically determines its next hop based on the network topology. One type of Ad-Hoc network is the Mobile Ad-Hoc Network (MANET). MANET is a self-configuring network of mobile nodes (also called routers), which can form a dynamic topology. The routers could move and organize themselves on-the-fly; thus, the topology of the wireless network may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the rest of the Internet. 1.3. Wireless Mesh Network (WMN) Fig. 2 shows an Infrastructure-based wireless network. Unlike the Ad-Hoc network, in an Infrastructure-based network, the end-user connectivity is managed by a special node, known as an access point (AP). Furthermore, an AP can coordinate between another AP and an end user. Among Infrastructure-based networks, Wireless Mesh Network (WMN) has gained considerable popularity in the past decade, especially due to its multi-hopping1 capability (similar to MANET). In a WMN, nodes assist one another in transporting a data packet through the wireless media. In principle, these networks can be extended to larger networks with greater number of nodes, and can still maintain the required end-to-end connectivity. The WMN consists of a number of Mesh Nodes (MN). There are two types of mesh nodes, namely routers and access points (APs). While the routers can perform data packet forwarding, APs are capable of both forwarding and serving the end users. Gateways form a subset of MN, which can connect either to the wired backbone network, or to a neighboring mesh network. 1.4. Routing in wireless Ad-Hoc and mesh networks The connectivity and routing in the Ad-Hoc and the Infrastructure-based networks depend largely on different aspects of the network functionalities. In addition to maintaining connectivity, the end user in the Ad-Hoc network can also perform routing. However, in a WMN, a mesh node is responsible for these functionalities. Hence, the end user in a WMN consumes significantly less energy and can run high-end applications compared to the end users in an Ad-Hoc network. Routing is a challenging problem in dynamic and mobile wireless networks. A good routing solution should have the characteristics of being decentralized, self-organizable, and self-healing. At the same time, a routing solution should adapt itself to the bandwidth limitation of the wireless spectrum, and exploit the multi-hopping property for better load balancing. Routing also needs to consider power awareness to provide an energy-efficient solution for wireless networks. The above concepts will be elaborated below. Routing is said to be decentralized when routing decisions are the responsibility of each node (router) separately, according to a certain pre-approved protocol between these nodes. In decentralized routing, there is no specific bottleneck central node at which routing decisions are made. Self-organization is a process of evolution where the development of a new and complex structure takes Fig. 1. Ad-Hoc network. Fig. 2. Wireless Mesh Network (WMN). 1 The concept of multi-hopping is very generic and applies to both wired network and wireless network (especially WMN). E. Alotaibi, B. Mukherjee / Computer Networks 56 (2012) 940–965 941 place primarily in and through the system itself. In a wireless network, if the network organizes itself to improve performance, or readjusts itself in case of a failure, then the network is self-organizing. Self-healing is a recovery process where routing could quickly overcome the negative effects of a failure; thus, self-healing improves the network’s fault tolerance. Bandwidth limitation, which is a result of the limited channel capacity, may occur because of the limited wireless spectrum, its shared medium nature, and due to concurrent transmissions. Being a shared medium, all wireless links have to share some common channels or frequencies.2 Thus, simultaneous transmissions on a single channel may lead to significant bandwidth reduction. Co-channel transmission, when two nodes use the same channel to transmit their data packets simultaneously, can also cause interference, if the nodes are close to each other, and this is an important issue to be considered when managing and designing the wireless network. This is because the more the interference among nodes, the more data loss occurs which leads to overall network-performance degradation. Multi-hopping means that one can setup a path over multiple nodes to reach the destination. In other words, the path between the source and the destination nodes goes through multiple intermediate nodes.Power awareness is crucial in a mobility-based wireless network, particularly in an Ad-Hoc network, where nodes need to reduce their power consumption to increase their battery lifetime if the nodes are not connected to a power outlet. In this case, the transmission power should be carefully chosen since the reduction in the transmission power level may lead to a reduction in the distance that the node can cover or what is called ‘‘transmission range’’. Hence, a node may not be able to directly connect to other distant nodes in the network, which reinforces the principle of multi-hopping in order to carry traffic among various pairs of nodes. 1.5. Dimensions of routing-algorithm categories The early routing algorithms (RA) for wireless networks are classified, similar to those for wired networks, according to centralized/distributed and proactive3 /reactive4 categories. We refer to this type of categorization as the classical dimensions of routing-algorithm categorization. However, in recent years, the wireless routing algorithms in the literature have evolved to encompass the unique challenges posed by wireless networks, which, in turn, introduce several novel routing categories, as shown in Fig. 3. These include Geographical, Multicasting, Geo-casting, Hierarchical, Flow-aware, Power-aware, Multi-path, Hybrid, and Mesh routing algorithms. The companion table (Table 1) expands on the acronyms of the RAs. The new method of categorizing the routing algorithms creates new and significant dimensions of wireless routing-algorithm categories compared to the wired-network routing-algorithm categories or the classical dimensions of routing-algorithm categorization. Multiple categories of routing algorithms can share some common properties. As a result, several routing algorithms can be placed into multiple categories. For instance, the Zone-based Hierarchical Link State (ZHLS) [62] algorithm is listed under two different categories: Geographical as well as Hybrid. All of these routing algorithms can also be categorized as centalized/distributed and proactive/reactive. 1.6. Wireless routing-algorithm issues Using basic routing algorithms in a wireless environment could lead to problems such as large area of flooding,5 empty set of neighbors (when Greedy Forwarding technique is used), flat addressing, widely-distributed information, large power consumption, interference, and loadbalancing problems. Therefore, several routing algorithms from different routing-algorithm categories were proposed to solve one or more of these issues