پديد آورنده :
قياسيان، علي
عنوان :
بررسي زمان بندي لينك ها در شبكه هاي بي سيم با استفاده از نظريه گراف
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر
صفحه شمار :
نه،107ص:مصور،جدول نمودار
يادداشت :
ص.ع.به فارسي و انگليسي
استاد راهنما :
حسين سعيدي
استاد مشاور :
بهناز عمومي
توصيفگر ها :
تداخل , تطابق بيشين , تطابق , NP-سخت , گراف تداخل , توپولوژي شبكه , گراف خطي , عدد رنگي راسي , عدد رنگي يالي
تاريخ نمايه سازي :
17/11/91
استاد داور :
ناصر يزداني، ناصر موحدي نيا
دانشكده :
مهندسي برق و كامپيوتر
كد ايرانداك :
ID471 دكتري
چكيده فارسي :
به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي
چكيده انگليسي :
108 ghiasian@ec iut ac ir Date of Submission 2012 10 03 Department of Electrical and Computer Engineering Isfahan University of Technology 84156 83111 Isfahan Iran Supervisor Hossein Saidi hsaidi@cc iut ac ir Advisor Behnaz Omoomi bomoomi@cc iut ac ir Department Graduate Program Coordinator Masood Omoomi Isfahan University of Technology Abstract In single channel wireless networks concurrent transmission at different links may interfere with each other To improve system throughput a scheduling algorithm is necessary to choose a subset of links at each time slot for data transmission There are different network parameters which are affected by link scheduling algorithms such as throughput delay complexity and fairness A throughput optimal algorithm termed as maximum weight link scheduling MWS in such a wireless network is generally an NP hard problem We have investigated MWS and its approximation Basic Randomized Algorithm BRA in terms of complexity and delay We have developed a polynomial time algorithm for link scheduling problem provided that network conflict graph is line multigraph It was shown that how the derived conditions can be satisfied by network designers through topology control of the network by prohibiting the construction of seven forbidden graphs in the conflict graph We also study the relation between network topology and delay performance of the MWS algorithm by deriving two upper bound of delay which are related to topological parameters of the network We also analyze and improve the delay performance of BRA This algorithm is appropriate for distributed implementation We first introduce a novel concept the average hitting time and analyze its impact on the upper bound of the average delay It is then analytically shown that for two given randomized algorithms achieving the same throughput region the one with a smaller average hitting time has a much less average delay bound We also prove that by assigning traffic priorities in some specific applications the achievable throughput region delivered by the BRA algorithm remains intact This result is much valuable in the design of algorithms for some real time applications by prioritizing the traffic to reduce the average delay of those applications Simulation results confirm our analytical relations throughout the thesis Keywords Link Scheduling Matching Conflict Graph Line Graph Chromatic Number Network Topology
استاد راهنما :
حسين سعيدي
استاد مشاور :
بهناز عمومي
استاد داور :
ناصر يزداني، ناصر موحدي نيا
