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

2. مقدمات

            ما یک MTR WMN را همانند یک گراف جهت‌دار  G(V.E) مدل‌سازی می‌کنیم. مجموعه V شامل گره‌هایی است که با  b>1  جهت دار شده است. هر گره u دارای یک محدوده انتقال از r و b_u≥1 است. یال‌های جهت‌داری وجود دارند که گره u  و گره v را اگر در محدوده‌ی انتقال یکدیگر باشند به‌هم وصل کرده‌اند. لینکی که u و v را به هم متصل کرده با (u.v) نشان می‌دهیم. توجه داشته باشید که، در عمل، گره‌ها ممکن است طیف انتقال مختلفی داشته باشند. برای این منظور، گره مورد نیاز باید از لینک‌های ورودی و خروجی به هر یک از همسایه ‌ها اطمینان داشته باشد. این را می‌‎توان از طریق پیغام‌های سلام در فرایند کشف همسایه به دست آورد که به موجب آن گره شامل همسایگانی است که پیغام را دریافت کرده‌اند. از این رو، تابع Ft :E →R زمان اختصاص داده شده برای هر لینک است. بنابراین ft زمان انتقال مورد نیاز را  به‌منظور روبه رویی با بار ترافیک داده مدل‌سازی می‌کند. همه گره‌ها قادر به ارسال یا دریافت امواج به صورت همزمان در همه لینک‌ها هستند. هر لینک توسط یک رادیو پشتیبانی می‌شود و ما فرض می‌کنیم b_u≥|N(u)| برای هر گره است.

           دو تحقق اصلی در مورد MTR WMNS وجود دارد. این موضوع برای اولین بار در [9]، که در آن هر روتر با رادیو‌های متعدد متصل به یک آنتن مجهز است بیان شده است. تمام رادیوها در فرکانس یکسانی کار می‌کنند. گره‌ها حس حامل خود را برای اجازه انتقال همزمان غیرفعال کرده‌اند و انتقال کنترل قدرتکه برای اطمینان از لینک‌های ورودی استفاده می‌شود قدرت سیگنال کافی برای اطمینان از دریافت صحیح دارد. تحقق دوم در راستای تحقق چندکاربری، چندورودی و چندخروجی است (MU-MIMO)؛ برای جزئیات بیشتر به [15] و یا [16] مراجعه کنید. گره‌ها آنتن‌های متعدد دارند که می‌توانند برای انتقال مستقل داده‌ها استفاده شوند. علاوه بر این، گره دارای اطلاعات حالت کانال است (CSI). این فرض معقول است که گره در درجه اول ایستاتیک باشد و نمادها را می‌توان برای یادگیری CSI انتقال داد.  

            بعبارت دیگر، محدودیت Mix-TX-Rx به شرح زیر است: برای یک گره داده شده u، فرض کنید  IN(u.t)و OUT(u.t) مجموعه دریافت و انتقال لینک‌ها در زمان t باشند. این محدودیت برآورده می‌شود اگر هر دو  IN(u.t)و OUT(u.t) به طور همزمان در هر زمان t برای همه گره بزرگتر از صفر نباشند.

در مدل ما،  مفروضات به شرح زیر است:

• همه گره‌ها در سطح جهانی همزمان شده‌اند. با توجه به اینکه گره‌ها استاتیک هستند و می‌توانند از GPS برای همگام‌سازی زمان قفل استفاده کنند، این مسئله منطقی است.

• گره‌ها به تک فرکانس تنظیم شده‌اند. مطابق [9]، از دلایل اصلی برای به کارگیری یک کانال منفرد به شرح زیر است: (الف) استفاده از یک کانال برای پایه آن در حالی که از کانال‌های دیگر برای دسترسی محلی استفاده می‌کنیم راحت است، (ب) کانال‌های بیشتری استفاده می‌شود، هزینه‌های عملیاتی بالاتر به دلیل باندهای IEEE 802.11 است که برای استفاده در فضای باز در برخی از کشورهای در حال توسعه به مجوز نیاز دارد و (ج) برای جلوگیری از آلودگی RF همانگونه که بسیاری از شبکه ‌ای وای فای وجود دارد. همچنین توجه داشته باشید که قابلیت MTR گره‌ها می‌تواند با استفاده از MIMO [17] و یا توسط تجهیز گره با رادیو 60 گیگاهرتز به دست آید[18].

• همه گره‌ها در سطح جهانی همزمان شده‌اند. با توجه به اینکه گره‌ها استاتیک هستند و می‌توانند از GPS برای همگام‌سازی زمان قفل استفاده کنند، این مسئله منطقی است.

• گره‌ها به تک فرکانس تنظیم شده‌اند. مطابق [9]، از دلایل اصلی برای به کارگیری یک کانال منفرد به شرح زیر است: (الف) استفاده از یک کانال برای پایه آن در حالی که از کانال‌های دیگر برای دسترسی محلی استفاده می‌کنیم راحت است، (ب) کانال‌های بیشتری استفاده می‌شود، هزینه‌های عملیاتی بالاتر به دلیل باندهای IEEE 802.11 است که برای استفاده در فضای باز در برخی از کشورهای در حال توسعه به مجوز نیاز دارد و (ج) برای جلوگیری از آلودگی RF همانگونه که بسیاری از شبکه ‌ای وای فای وجود دارد. همچنین توجه داشته باشید که قابلیت MTR گره‌ها می‌تواند با استفاده از MIMO [17] و یا توسط تجهیز گره با رادیو 60 گیگاهرتز به دست آید[18].

• ما فرض می‌کنیم که بار ترافیک در هر لینک جمع شده است، به‌عنوان مثال، [14] را ببینید، و برای مقادیر غیر قابل اغماض ثابت باقی می‌ماند به‌عنوان مثال، هر ساعت. همچنین بدان معنی است که مسیریابی برای جفت مقصد منبع برای این دوره زمانی ثابت است. مورد مشترک در بهینه‌سازی مسیریابی و زمان‌بندی لینک را به‌عنوان کارهای آتی به آینده موکول می‌کنیم. 

• هر واحد زمانی‌می‌تواند به یک مقدار خاص از زمان مطابقت داشته باشد، به‌عنوان مثال، یک ثانیه، و یا مدت زمان لازم برای انتقال یک بسته. این مهم است که توجه داشته باشید که یک بار که زمان به یک لینک اختصاص داده شد، انتقال زمان‌بندی شده آن، برای زمان پیش از انتقال تضمین شده است.

          مشکل ما به شرح زیر است: با توجه به MTR WMN، به موجب آن که هر لینک دارای یک زمان مختلف است، طراحی الگوریتمی متمرکز که موجب کاهش طول superframe شود نیاز به فعال کردن حداقل یک بار و مطابق زمان لینک‌ها دارد. توجه داشته باشید، یک superframe را به‌صورت زیر تعریف می‌کنیم دنباله ({e_1.000.e_x }.t_1 )∪… ∪({e_y.000 .e_(|E|) }.t_(|E|))، که در آن e_i ϵE لینکی به زمان‌بندی در زمان ti است. به عنوان مثال، در شکل 2، داریم ({AB.AC}.0)∪({BA.CA}.10)∪({BC}.15)∪({CB}.24). مسئله یافتن superframe با حداقل مقدار t_(|E|)+f_t (e_(|E|)) بنا به محدودیت‌های Mix-Tx-Rx است (شکل 1) و هر لینک eϵE حداقل یک زمان دریافت می‌کند.

        توجه داشته باشید، اگر تمام لینک‌ها زمان یکسانی داشته باشند، مسئله مشابه کار انجام شده در [11] خواهد شد. به طور خاص، نویسندگان [11] نشان می‌دهند که استخراج حداکثر تعداد لینک در هر اسلات متناظر با حل مسئله NP-complete و مسئله برش ماکزیمم است. برای این منظور، در بخش بعدی، ما روش تکاملی حریصانه را با هدف تعیین کوتاه ترین  superframe امکان‌پذیر پیشنهاد می‌کنیم.

3. راه‌حل: A-TxRx

         ایده اصلی زمان‌بندی لینک‌های جدید با عدم تداخل به هنگام اتمام انتقال یک لینک است. در بخش. 3.1، ما نشان می‌دهیم که چگونه زمان‌بندی نتیجه شده می‌تواند با اضافه کردن لینک‌های به اصطلاح فرصت‌طلب بهبود یابد. علاوه براین، در بخش 3.2، ما یک گام با محاسبات سنگین را که برای محاسبه سیستم‌های مدیریت اطلاعات با یک گام حریصانه استفاده شده است با افزودن لینک‌های غیرمتضاد با توجه به زمان انتقال آنها ساده‌سازی می‌کنیم. 

           الگوریتم ما دارای مراحل کلیدی زیر است. در مرحله اول، یک گراف متضاد G^' (V^'.E^') براساس توپولوژی شبکه G^  (V^ .E^  ) ساخته می‌شود. در گراف متضاد، هر راس v^' ϵV^' نشان‌دهنده یک لینک در E است و یک تضاد بین دو لینک در E توسط یک e^' ϵE^' بین رئوس مربوطه بیان می‌شود؛ [19] را مشاهده کنید. که تمام مجموعه‌های مستقل و حداکثر را  (MISs) در G^'  نشان می‌دهد. به یاد داشته باشید که MIS زیرمجموعه‌ای از تمامی لینک‌ها در G^' است که می‌تواند در زمان یکسانی بدون دخالت فعال شود. توجه داشته باشید که یک لینک ممکن است به‌صورت متفاوت ظاهر شود. در مرحله سوم، MIS را با بیشترین لینک‌ها انتخاب کردیم، که توان بالا را تضمین می‌کند. ما همه لینک‌ها را در MIS انتخاب شده فعال می‌کنیم و آنها را با عنوان لینک‌های فعال برچسب می‌زنیم. ما همچنین زمان آن‌ها را ضبط می‌کنیم. در میان تمام لینک‌های فعال، آنهایی که حداقل زمان را دارند با عنوان لینک‌های پایان در نظر گرفته می‌شوند. سپس زمان این لینک‌های پایان را ضبط می‌کنیم. در چنین زمانی، آنها را از G^' حذف می‌کنیم. اگر G^' خالی نباشد و اگر هیچ لینک فعالی وجود نداشته باشد اولین بار مشخص می‌شوند. این لینک‌ها به عنوان لینک‌های باقی‌مانده مشخص می‌شوند. اگر هیچ لینک باقی‌مانده‌ای وجود نداشته باشد، یک MIS جدید به‌طور مستقیم از G^' به دست می‌آید. این MIS شامل لینک‌های جدیدی است که می‌تواند به superframe اضافه شود. با این حال، اگر لینک‌های باقی‌مانده‌ای وجود داشته باشد، ما چک می‌کنیم تا ببینیم که آیا می‌توانیم لینک‌های با عدم تداخل جدید اضافه کنیم. ابتدا یک گراف متضاد جدید G^'' از G^' می‌سازیم. به‌طورخاص، لینک‌های پایانی، تمام لینک‌های باقی‌مانده و همسایگان آن را حذف می‌کنیم. سپس یک MIS جدید از G^'' به دست می‌آید، که شامل جدیدترین لینک‌هایی است که با لینک‌های باقی‌مانده مداخله‌ای ندارد. مجموعه‌ی بعدی از لینک‌های پایانی تعیین می‌شود و فرآیند را تکرار می‌کنیم. وقتی G^' خالی است A-TxRx خاتمه می‌یابد (جدول 1). 

         ما نشان خواهیم داد که یک-TxRx چگونه کار می‌کند، الگوریتم 1 را ببینید، تعیین زمان‌بندی برای توپولوژی در شکل 2 نشان داده شده است. همان‌گونه که نشان داده شده است، آن یک WMN MTR با سه گره A، B او C متصل با لینک دو طرفه است. مقدار بعدی به هر یک از لینک‌ها نشان دهنده‌ی زمان اختصاص داده شده است.

Abstract

          A key advance in enabling higher wireless mesh network capacity is allowing routers to transmit or receive (MTR) from multiple neighbors simultaneously over the same frequency. Achieving this capacity, however, is predicated on a link scheduler that is able to capitalize on the MTR capability of nodes to activate the maximum number of active links, and also to derive the shortest schedule that ensures all links are activated at least once. To date, existing schedulers do not consider the transmission or air-time of packet(s). Henceforth, this paper fills this gap and propose to derive the shortest superframe length, defined as the end time of the last transmitting link. Our scheduler, called A-TxRx, greedily adds links whenever a link finishes its transmission. As a result, unlike previous schedulers, links can start transmitting/receiving as soon as there is no conflict. We have evaluated the performance of A-TxRx in various network configurations, and compared it against two state-of-the-art approaches: 2P and JazzyMAC. The results show A-TxRx outperforming these algorithms significantly, especially when the network becomes denser. Specifically, the superframe length of A-TxRx is typically less than half of 2P and JazzyMAC, with 60 % more concurrently transmitting links.

1 Introduction

          Wireless mesh networks (WMNs) have matured significantly over the past few years. In WMNs, nodes are connected to one another wirelessly and forward packets via multi-hop communications to each other or to gateways. WMNs can be deployed in both urban and rural areas to deliver video, voice and data in indoor and outdoor environments and have applications in home networking [1], enterprises [2], and metropolitan area networks [3]. In this respect, the Quality of Service (QoS) experienced by users is a critical consideration; see [4]. Recently, researchers have proposed Multi-Transmit-Receive (MTR) WMNs, whereby nodes are equipped with multiple Directional Antennas (DAs) or adaptive arrays in order to increase network capacity. This means all nodes can transmit or receive simultaneously from their respective neighbouring nodes; see Fig. 1(a, b). The resulting WMNs thus have a higher network capacity than those that use an omni-directional or a single directional antenna [5–7]. We note that the WMN under consideration is distinct from past works that assume nodes have multiple radios and multiple channels [8].

          As illustrated in Fig. 1(c), a key constraint is no MixTx-Rx, meaning a node operates in half duplex mode [9]. Consequently, any developed scheduler that aims to derive the shortest superframe length must adhere to this constraint. Note, a ‘superframe’ is defined as a sequence of transmission slots; hence, the shortest superframe denotes one that has the minimum number of slots. In [9], Raman et al. outlined a spatial time division multiple access (TDMA) medium access control (MAC), called 2 Phase (2P), that separates transmissions, called SynOp, at each node into two phases: SynTx and SynRx. However, this MAC can only be applied to MTR WMNs with a bipartite topology. This problem is solved by Chin et al. in [10] whereby they presented a novel scheduling algorithm called Algo-1 that schedules links in MTR WMNs with an arbitrary topology by recursively partitioning nodes into maximally connected bipartite sets. This algorithm is then improved in [11] to realize the maximal number of concurrent transmitting links.

         The said prior works, however, do no consider links with different weights. This is necessary because of two reasons. Firstly, in practice it is likely that links will have different loads. For example, links on shortest paths or a router may be serving an area with a large number of subscribers. Secondly, different data rates may be used by links in order to counter the vagaries of the wireless channel. For example, IEEE 802.11a supports data rates up to 54 Mbps. This means, for a given packet size, the airtime required to transmit said packet will vary depending on the data rate or channel condition as well as the number of packets to be transmitted.

          In [12, 13] and [14], the authors consider the weight of links. Dai et al. [13] propose two schedulers called HeavyWeight-First (HWF) and Max-Degree-First (MDF). As their name implies, links are either scheduled depending on their weight or the number of neighbors. However, the authors of [12] and [13] did not consider links that require different transmission times. This problem is tackled in [14] where the authors present an adaptive MAC called JazzyMAC. A node first monitors the volume of traffic on its outgoing links. It then dimensions the transmission slot of each link as per the observed traffic volume. To schedule transmission, a token exchange mechanism is used whereby a node only transmits whenever it has the token for all its links. This, however, precludes nodes from taking advantage of opportunistic links; see Sect. 3.1. Furthermore, it is sensitive to the initial token assignments. More importantly, although the transmission finishing time for all incident links to one node varies depending on actual traffic demand, the transmissions of the said links still start at the same time.

          Given the above discussions, we now show a key limitation of past solutions. Consider Fig. 2. We see a MTR WMN with three nodes connected in a clique. The number next to each link represents its required transmission or airtime. Also shown in Fig. 2 is the schedule for each link derived using 2P [9]. In this example, at time = 0, link AB and AC start to transmit simultaneously in the first slot for 10 units of time. Then at time = 10, the corresponding opposite links BA and CA are activated in the second slot for the duration of five units only after both AB and AC finish. At time = 15, the activation of link BC and link CB takes place in the third and fourth slot for a duration of nine and three time units respectively. Thus, for this example, 2P derives superframe that has length T ¼ 27, and schedules every link to be activated at least once for the period of its assigned air-time without conflict.

           In the aforementioned example, we see that a group of links is to remain active in SynTx or SynRx in one slot for the same slot duration regardless of the actual link weight. This situation leads to the following problem. Consider link AB and AC, which are activated simultaneously in slot 1. The slot length needs to be the longer air-time, which is 10. Notice that link AB finishes in one slot, causing 9/10 of the link capacity to be wasted, leading to a lower throughput. This is because no other links are scheduled until link AC finishes. In fact, if node B wants to transmit to C, it should be be able to initiate transmission at any time after the first 1/10 of slot. If link BC avoids having to wait until link AC finishes, throughput improves.

          In light of the above observations, we propose A-TxRx, a scheduler that activates link with different transmission or air-time in a MTR WMN. Unlike existing schedulers, A-TxRx aims to minimize the finishing time of the last transmitting link as well as maximize the number of links at any time instant. In a nutshell, our main contributions are:

• A-TxRx is the first centralized link scheduler for MTR WMNs that considers the assigned air-time of links in order to meet the underlying link demand. Our results show that A-TxRx has better performance in all considered scenarios, i.e., an average of 40 % shorter superframe length than 2P, especially when the network is fully connected. For example, as will be shown in Sect. 3, A-TxRx generates a superframe with length T ¼ 16 for the WMN of Fig. 2. In all experiments, the superframe length of A-TxRx is at most 70 % shorter than state-of-the-art approaches.

• We outline an improvement to A-TxRx, where we opportunistically add scheduled links to further increase network capacity. Our results show that the number of concurrent transmitting links when running A-TxRx to be 40 % more than JazzyMAC [14] on average.

• We analyze and prove that A-TxRx is a collision free scheduler for arbitrary topologies and has a running time of OðjVj 5 Þ for WMN with |V| nodes.

           The rest of the paper is structured as follows. Sect. 2 describes the network model of MTR WMNs and the formal definition of our problem. Section 3 outlines the details and analysis of A-TxRx. The research methodology is presented in Sect. 4. Section 5 presents our experiments and results. The paper concludes in Sect. 6.

1.مقدمه

2. مقدمات

3. راه‌حل: A-TxRx

3.1 لینک‌های فرصت طلب 

3.2 A-TxRx حریص 

3.3 تجزیه و تحلیل 

4. روش تحقیق 

5. نتایج 

5.1 تراکم گره 

5.2 شعاع انتقال 

5.3 درجه گره 

5.4 زمان محاسبه 

5.5 تاثیر انتخاب MIS مختلف برای A-TxRxGC 

6. نتیجه‌گیری 

1 Introduction

2 Preliminaries

3 The solution: A-TxRx

3.1 Opportunistic links

3.2 Greedy A-TxRx

3.3 Analysis

4 Research methodology

5 Results

5.1 Node density

5.2 Transmission radius

5.3 Node degree

5.4 Computation time

5.5 Impact of choosing different MIS for A-TxRxGC

6 Conclusion

References