Presented by You-Ren Hsieh A General Interference-Aware Framework for Joint Routing and Link Scheduling in Wireless Mesh Networks Leonardo Badia and Alessandro Erta, IMT Lucca Institute for Advanced Studies Luciano Lenzini, University of Pisa Michele Zorzi, University of Padova IEEE Network January/February 2008 Presented by You-Ren Hsieh

Agenda Authors Abstract Introduction Wireless Transceiver Constraints Wireless Interference Constraint Performance Evaluation Conclusions 2019/1/17 NTU IM OPLAB

Authors

Authors Leonardo Badia received a Laurea degree (with honors) in electrical engineering and a Ph.D. in information engineering from the University of Ferrara, Italy, in 2000 and 2004, respectively In 2006, he joined the “Institutions, Markets, Technologies” (IMT) Lucca Institute for Advanced Studies, Lucca, Italy, where he is currently a research fellow 第一位作者是Leonardo Badia，他分別在2000年與2004年於義大利的費拉拿大學拿到了電機工程碩士學位與資訊工程博士學位，在2006年時加入位於義大利路卡市的一個IMT研究所，現在也是那邊的研究員。那他的研究領域主要包含以下幾個部份，energy-efficient ad hoc networks, transmission protocol modeling, admission control, economic modeling等等，那現在也很多與通訊相關期刊的reviewer。 His research interests include energy-efficient ad hoc networks, transmission protocol modeling, admission control, and economic modeling of radio resource management for wireless networks. He serves as a reviewer for several periodicals in communications 2019/1/17 NTU IM OPLAB

Authors (cont’d) Alessandro Erta graduated (cum laude) in computer systems engineering from the University of Pisa, Italy, in February 2005. He is currently a Ph.D. student at IMT Lucca Institute for Advanced Studies 第二位作者Alessandro Erta在2005年於義大利比薩大學的電腦系統工程畢業，目前是IMT的博士生，，他的研究興趣包括無線網路的QoS，MAC protocol的設計與performance評估，還有WMN的scheduling演算法。 His research interests include quality of service in wireless networks, design and performance evaluation of MAC protocols, and scheduling algorithms for wireless mesh networks 2019/1/17 NTU IM OPLAB

Authors (cont’d) Luciano Lenzini received a degree in physics from the University of Pisa. He joined the Centro Nazionale Universitario di Calcolo Elettronico (CNUCE), an institute of the Italian National Research Council (CNR), in 1970. In 1994 he joined the Department of Information Engineering of the University of Pisa as a full professor 第三位作者Luciano Lenzini在比薩大學得到物理系學位，於1970年時加入義大利國家研究委員會的一個研究所，CNUCE。之後1994年時進入比薩大學的資訊工程系擔任教授。他的研究興趣包括無線網路的MAC protocol設計與performance評估，mesh網路的結構與protocol以及服務網路的QoS提供。他現在是Computer Networks的editorial board中的一員，也是Journal of Communications and Networks的領域主編。 His current research interests include the design and performance evaluation of MAC protocols for wireless networks, architectures and protocols for mesh networks, and quality of service provision in integrated and differentiated services networks. He is currently on the editorial boards of Computer Networks and the Journal of Communications and Networks as area editor for wireless networks 2019/1/17 NTU IM OPLAB

Authors (cont’d) Michele Zorzi received a Laurea degree and a Ph.D. in electrical engineering from the University of Padova, Italy, in 1990 and 1994, respectively. In 1998, he joined the School of Engineering of the University Ferrara, Italy, where he became a professor in 2000 His present research interests include performance evaluation in mobile communications systems, random access in mobile radio networks, ad hoc and sensor networks, energy constrained communications protocols, and broadband wireless access. He is currently the Editor-In-Chief of IEEE Transactions on Communications, and serves on the editorial boards of IEEE Transactions on Wireless Communications, Wiley’s Journal of Wireless Communications and Mobile Computing, and ACM/URSI/Kluwer Journal of Wireless Networks. 第四位作者是Michele Zorzi，分別在1990年與1994年在義大利帕多瓦大學拿到電機碩士與博士學位。在1998年他加入費拉拿大學的工學院，並在2000年時成為教授。他的研究領域包含行動通訊網路的performance評估，還有行動無線網路、ad hoc、sensor network的random access，以及energy constrained通訊協定和寬頻無線存取等等。目前是IEEE Transactions on Communications的總編輯，也是IEEE Transactions on Wireless Communications等幾個期刊的editorial board中的一員。 2019/1/17 NTU IM OPLAB

Abstract

Abstract Joint design and optimization of traditionally independent problems become one of the leading research trends in wireless mesh networks Cross-layering is, in fact, expected to bring significant benefits from the network resource exploitation standpoint to achieve high system utilization In this article we propose a versatile framework for joint design of routing and link scheduling (JRS) introducing the notion of link activation constraints which are related to the transceiver capability and the broadcast nature of the wireless medium 對於像是routing與link scheduling這種傳統上的獨立問題的協同設計與最佳化，在近年來是一個在wireless mesh network上的研究趨勢。雖然有技術上的挑戰，但是cross-layer在網路資源的觀點上被認為是可以帶來顯著的幫助，以達到更高的系統使用。在這篇論文中，提案了一個在routing與link scheduling協同設計上，多方面適用的framework，並且介紹link activation constraint的概念。這個constraint是與無線傳輸媒介的transceiver capacity與broadcast種類相關的一些限制。 2019/1/17 NTU IM OPLAB

Abstract (cont’d) To this end, we introduce a taxonomy of wireless interference models to harmonize existing approaches presented in the literature We evaluate the impact on network capacity of the various interference models when optimal joint routing and link scheduling are employed 在結尾的部份，介紹wireless interference model的分類去協調其他文獻中提及的幾種方法。也評估當採用最佳的JRS時，在不同的interference model下對網路capacity帶來的影響。 2019/1/17 NTU IM OPLAB

Introduction

Introduction The end terminals, also referred to as mesh clients (MCs) are connected to special nodes, called mesh routers (MRs) can interact only with the MR to which it is connected Some MRs, called mesh access points (MAPs) can be provided with cabled connection act as gateways toward the Internet is also wirelessly interconnected to every other MR MRs form what is usually referred to as the backbone of the WMN can physically cover a large region using wireless multihop communication 對於終端的使用者，像是手機或筆記電腦等，稱為mesh client，這些mesh client都會連接到一個mesh router，並且也只能與所連接的mesh router互動。有一些mesh router稱為mesh access point，會透過cable的連線，如同一個gateway，來連接到Internet，同時也可以與其他的mesh router用無線方式連接。Mesh router是整個WMN的骨幹，可以大範圍的分布以作multihop communication。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) A possible realization of a WMN 下圖是WMN的一個架構，backbone的部分由MR組成，MAP則以有線方式對外連接，以及可以與MR互動的各個MC。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) This structure offers a good cost/benefit balance since it almost entirely avoids cable setup it is deemed applicable in rural areas as well as dense residential or business areas where the deployment of wireline networks may be too expensive or difficult because of physical obstacles The multihop communication among MRs is an open issue involves several challenges related to different layers of the protocol stack 這樣的結構提供了好的成本效益，因為幾乎完全不需要使用到線路，也視為可以應用在鄉村地區和密集的住宅區或商業區來使用，因為有線網路的建立，可能會因為一些實體障礙而比較昂貴和困難。而在mesh router之間的multihop communication一直都是open issue，並包含了很多與protocol stack的不同layer之間有關的一些challenge。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) The creation of low-interference high-rate paths to the MAPs is key to achieve good rates at each MR The link layer needs to schedule packets over multiple links in order to achieve good transmission parallelism possibly forward more data toward the MAPs at the same time Finding the optimal path toward an MAP and scheduling links so as to maximize the transmission parallelism are traditionally performed by the routing algorithm running at the network layer and by the medium access control (MAC) protocol at the link layer, respectively 那一方面呢，建立low-interference跟high-rate的path來連接到MAP是讓每個MR有更好的傳輸率的方法。而另一方面，link layer需要在multiple link中去schedule封包，以達到好的平行傳輸，並且儘可能在相同時間內傳送更多的data到MAP。傳統上要找出最佳的path到達MAP與schedule link來最大化平行傳輸的話，前者是藉由network layer的routing演算法，而後者則是藉由link layer中的MAC protocol來達成。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) However, in a multihop wireless network, the routing algorithm needs to deal with link scheduling If predefined routes (e.g., based on a shortest path criterion) are used, any scheduling algorithm will be forced to activate only the links belonging to that route The combined result may be suboptimal in the sense that not all available network resources are utilized 然而呢，在multihop無線網路的環境下，routing演算法必須去完成link scheduling的部份。如果使用shortest path的路由方式，任何的scheduling演算法將會被迫使去activate只屬於這個路徑中的每個link。這樣的結合結果並非是最佳化，也就是說所有可用的網路資源並沒有都被使用到。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) The authors addressed the question of combining optimal link scheduling with suboptimal routing and vice versa these tasks affect each other, and their optimality is strongly coupled This is mainly due to the broadcast nature of the wireless medium which combines the advantage of allowing each MR to communicate with multiple MRs through a single network interface with the disadvantage that simultaneous transmissions from different MRs may interfere with each other The main conclusion is that interference awareness available at the link layer must be exploited at the routing level 在另一篇論文中的作者定義了一個問題，就是結合最佳化的link scheduling與非最佳化的routing，而這樣的情況會互相影響，而且最佳性也是很強烈的結合在一起。這主要是因為無線傳輸媒介的broadcast種類有關，結合了一個優點與一個缺點，優點是讓每個mesh router與其它mesh router可以透過單一的network interface來聯繫，而缺點是不同mesh router的同時傳輸，彼此之間會互相干擾。所以在該篇論文最後的結論是說，要讓interference awareness在link layer可用的話，就必須在routing的部分去完成。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) Cross-layer design solves a joint routing and scheduling (JRS) optimization problem is thus considered very promising to fully exploit WMN capacity Recently, several papers have proposed solutions in this area The leitmotif of all the papers is that approaching a JRS problem requires the specification of an interference model defines whether or not simultaneous transmissions of different MRs can be correctly decoded at their receivers Cross-layer design跨層設計，可以解決JRS的最佳化問題，所以也被認為能夠完全去使用到WMN的capacity。在近年來有很多paper在這個領域提出一些solution，而這些paper主要都是在說，在處理JRS的問題時，都需要interference model的specification，來定義說不同mesh router的同時傳輸能不能被接收端正確的decode。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) The most widely used classification of interference models distinguishes between the so called physical and protocol interference models In the former, the feasibility of simultaneous link activations is determined by the signal-to-interference ratio (SIR) of all receivers being above a given threshold The latter instead imposes simpler interference conditions modeled through graph neighborhood relationships Interference model最普遍的分類為physical interference model跟protocol interference model。前者認為同時的link activation的可行性是由所有接收端在一個給定的threshold上的訊號干擾比率來決定的。後者則是利用由鄰近節點之間的關係來model interference的情形。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) The main problem of the existing approaches the proposed algorithms are strongly coupled with the interference model adopted Thus, they may turn out to be suboptimal if more realistic models are considered 現有方法的主要問題就在於所提案的演算法都與採用的interference model有強烈的相關。因此如果考慮到更多其他的model時將不會有最佳化的結果。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) In this article we present a general framework decouples the notions of transceiver capability and wireless interference from the JRS algorithms To study routing and scheduling under the graph formulation we use the language of constrained linear programming problems, as commonly done in related work 在這篇論文中介紹了一個general的framework，將transceiver的capacity與interference的概念從JRS演算法中分離開來。為了要研究在圖形化公式下的routing與scheduling，這裡使用在別篇論文中的一種用在constrained linear programming problem的語言來描述。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) We represent the backbone of a WMN as a directed graph G = (N, E) The nodes in set N are the MRs connected by directed edges belonging to set E, which are ordered pairs of nodes and thus represent the communication links of the backbone The link where a sender node i ∊ N transmits to a receiver j ∊ N is represented by (i, j), included in E only if node j can receive a transmission from i in the absence of any other interference source 將WMN的backbone表示成一個directed graph G=(N,E)，集合N為所包含的node也就是mesh router，這些node由directed edge所連接，這些edge為集合E，也就是backbone裡的各個link。當sender node i 要傳送給receiver node j 並且node j 在接收node i 的傳輸時沒有其他干擾的source，這個link的表示為(i, j)，當然也會包含於集合E。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) We also denote with Ri and Si the set of nodes that are possible receivers from and senders to node i, respectively the one-hop output and input neighbors of i Formally: Ri = {j ∊ N : (i, j) ∊ E}, Si = {j ∊ N : (j, i) ∊ E} We also consider a parameter gij corresponding to the wireless link gain when transmitting from i to j The rule for the inclusion of (i, j) in E can thus be that gij is above a given threshold 另外以R sub i 與S sub i 來分別表示從node i 送出而接收的節點的集合和傳送到node i 的節點的集合，也就是與node i 相鄰one-hop的鄰近節點，公式如下。還有一個參數為g sub ij，代表的是由node i 傳送給node j 時所得到的link。那g sub ij在一個給定的threshold之上時，就符合先前定義的集合E中的link (i, j)。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) Note that in realistic wireless scenarios, the performance of the forward and reverse links are not necessarily the same the existence of the reverse link (j, i) for every (i, j) ∊ E is not even guaranteed We speak of activation of link e = (i, j) at time t if i is transmitting to j at time t To this end, we use a binary indicator variable Xij(t) equal to 1 if (i, j) is active at time t and 0 otherwise The JRS problem corresponds to determining the pattern of link activations described by variables Xe(t) as time goes by 另外有一點值得注意的是，在實際的情況下，forward與reverse的link，他們的performance不見得會相同，而且link (i, j)不見得會存在reverse link (j, i)。接著提到了link的activation，指的是在時間點 t 時，node i 正在傳送給node j。最後使用了x sub ij of t，為0或1的變數，表示link是否為active。那JRS的problem呢，就是要隨著時間變化去決定x sub e of t這個變數的情形，也就是隨著時間決定哪些link是active的而哪些不是。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) To some extent, this addresses both scheduling and routing as the routes can be implicitly inferred by tracking subsequent link activations 在某些程度上，路徑的scheduling與routing可以藉由追蹤接連的link activation而推論出來。如下圖，封包要從A路由到F，可以藉由activate A到B的link，然後B到E的link，最後是E到F的link，在三個不同的時間點上。這些接連的activation便是封包的傳送時間。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) Constraints to describe any limitation imposed on the activation of links by MAC and physical layers the constraints that must be satisfied for multiple transmissions to be feasible their impact on network performance First, we talk about the constraints involving the physical capabilities of the radio transceiver is very general and independent of those due to wireless interference and confusion between the two concepts should be avoided 此外，這篇論文提到了constraint，用來描述任何MAC或physical layer對於link的activation所帶來的限制。並接著討論在滿足constraint下如何使得多個transmission是可行的，以及他們對網路performance的影響。這些constraint的分析分割為兩個部份。第一，是關於transceiver的physical capability，屬於比較general而且與interference是獨立開來的，並且避免兩者之間的混淆。 2019/1/17 NTU IM OPLAB

Introduction (cont’d) Second, we describe the constraints specifically related to interference also giving pointers to interference models present in the literature and referring to the MAC protocols specified in some common wireless interface standards that inspire the formulation of these constraints Finally, we provide numerical insights into the performance of JRS in WMNs when different interference models are employed 第二，描述的constraint則是與interference明確相關的，也提供一些pointer給其他文獻中的interference model，以及談論在wireless interface的標準中MAC protocol影響這個constraint的formulation的部分。最後，提供了觀察後的幾個見解，是關於JRS在WMN中採用不同的interference model時，performance的變化。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints

Wireless Transceiver Constraints The first constraint on link activation to solve JRS relates to the fact that the node capabilities for transmission and reception are limited We focus on WMNs operating with a single omnidirectional antenna on narrowband channels it is not possible to receive simultaneously from multiple sources Special techniques can improve this condition wideband code-division multiple access (WCDMA) multiple-input multiple- output (MIMO) channels 對於link activation的第一個constraint呢，是與node的capability有關的部份在傳送與接收上的限制。這裡focus在窄頻的channel上使用單一的全方向性天線，所以就不可能從多個來源同時接收資料。那當然有一些技術可以改善這種情形，像是WCDMA或MIMO等等。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints (cont’d) For simplicity, we do not investigate these issues the simple model analyzed here can easily be extended to also take these cases into account We assume that at most one signal can be decoded any other transmission the receiver is able to hear can only be regarded as interference The presence of interference at the receiver does not necessarily mean that the packet cannot be correctly decoded the interference model comes into play at this point 那為了簡化問題，這裡沒有去研究這些issue，不過這裡的simple model可以很容易的去加入這些情況作為考量。所以呢，這裡假設的是，最多只有一個signal可以被decode，其他的傳送對於接收者來說都視為interference。不過在receiver上存在interference，並非必然的表示說packet就不能被正確的decode。Interference model是在這一點上運作的。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints (cont’d) However, regardless of the interference model the maximum number of possible simultaneous successful receptions is one In particular, observe that we focus on unicast transmissions Thus, even though the wireless medium is broadcast therefore the same transmission can be heard by many receivers the message has only one intended destination multiple transmissions from the same node are not possible We assume that a node can serve as the transmitter on at most one active link 然而不管interference model為何，同時成功的接收最大都只會是一個。對於傳送端也有相同的情況，這裡focus在單點的傳輸，所以即使傳輸媒介是broadcast，也就是說同一個傳送，會有很多receiver可以接收到，但是目的地只會有一個。所以另一方面來說，multiple transmission就不可能出現在同一個node上。因此，這裡假設一個node最多只會在一個active的link上傳送。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints (cont’d) Not only can simultaneous transmissions and receptions at the same node be at most one, but also the wireless communication medium is intrinsically half-duplex a node cannot listen on the same channel on which it is transmitting at the same time the transmitted power signal will jam any packet reception Therefore, we impose the constraint of not activating more than one operation for each node 不僅同時的傳送跟接收在同一個node最多只有一個，而且無線傳輸媒介也是半雙工，也就是說一個node在傳送時，無法同時在同個channel上等待接收，或是傳送的signal將會阻擋其他packet的接收。因此，這裡在constraint加上每個node不會有超過一個的activating operation這個條件，代表不是傳送就是接收。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints (cont’d) Formally, this constraint translates into (1) The importance of constraint 1 is often underestimated when modeling multihop wireless networks In fact, even the need for such a constraint is rarely mentioned may be due to mistaking it for an interference condition it refers to a physical limitation that holds irrespective of the interference model. 這個constraint把它公式化如下，sigma j 屬於 S sub i X ji of t + sigma j 屬於 R sub i X sub ij of t 會小於等於1。前者指的是在時間點 t 時，node i 接收其他node j 的active狀態，後者則是node i 傳送給其他node j 的active狀態，那 X sub ij of t 是一個01變數，所以這個限制式代表的就是在時間點 t 時，node i 不論傳送或接收，都最多只有其中一個是active的，並且只會對於一個node有傳送或接收。在model multihop無線網路時，這個constraint的重要性常常會被低估，甚至這個constraint很少被提到，可能是因為把它誤認為是一個interference的condition，而把這個physical的限制當作與interference model無關。 2019/1/17 NTU IM OPLAB

Wireless Transceiver Constraints (cont’d) 那現在藉由以下的圖，來說明wireless transceiver constraint的觀點。首先，link A到B與link A到D無法同時activate，因為他們有同一個transmitter A，而link B到E與link D到E也無法同時activate，因為有相同的receiver E，另外link A到B與link B到E，因為node B不能同時傳送跟接收，所以也無法同時activate。不過constraint並沒有限制同時的link activation，像是link A到D與link B到E，以wireless transceiver constraint來說則是可以同時的，不過因為無線傳輸的broadcast的特性，即使不是目的地的receiver，一樣也會被reach到，像是A要傳送到D，但E也會reach到這個transmission，不過這樣的transmission將會被接下來要介紹的wireless interference constraint所限制。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint

Wireless Interference Constraint The usual classification of wireless interference models distinguishes between the protocol and the physical interference model The protocol interference model models interference as causing collision or the impossibility of correctly decoding a received packet if some neighboring nodes simultaneously exchange messages, disturbing the ongoing transmission The main advantage of an interference description conceptual simplicity the ease of mathematically formalizing 通常將interference model區分為protocol與physical interference model，而protocol interference model是在IEEE 802.11 MAC的基礎之上，所以將interference視為造成collision的狀況，或是如果一些鄰近的node同時有交換訊息而阻礙了transmission，使得收到的packet無法被正確的decode。那interference的描述主要的優點是他的概念簡單，以及比較容易用數學公式化。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) The rules of the protocol interference model impose the condition when certain transmissions are assumed to cause collision, they are simply forbidden to be simultaneously activated A way to formalize this constraint is to define associated with any edge e ∊ E, a conflicting set l(e) ⊆ E \ {e} The required condition is that if edge e is active, l(e) must contain no active edges (2) Protocol interference model的規則是，當有transmission被認為會造成collision的話，這些transmission就無法同時被activate。要formalize這個部份，定義了一個conflicting set l of e 包含於集合E並除了edge e以外，這個constraint的公式如下，意思是說，任一個edge e active的時候，在conflicting set l of e中的edge就不能active。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) Several possibilities have been presented to determine the set l(e) all generically called the protocol interference model but presenting subtle differences Our goal here is to propose a taxonomy identify as a class of interference models, since it actually encompasses several mathematical formulations Moreover, we aim to show the relationship, suggested by the name itself, with the MAC protocols possibly used in the WMN Conflicting set l of e 在其他文獻中有幾種方式可以決定，而這些一般都稱為protocol interference model可是都有些些微的不同。這裡主要的目標是將他們分類，所以identify了一些interference model，也包括一些數學公式。此外，這篇論文想要表示出可以用於WMN之中的MAC protocol之間的關係。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) As a first step, we intentionally introduce a very simple member of the protocol interference model class using the straightforward possibility l(e) = E \ {e} for all e ∊ E that is, at most one edge can be activated at any given time either exactly one edge is active, or no edge is active at all We refer to this version as the 01protocol model Even though it is quite oversimplified, this model can be useful as a theoretical term of comparison 首先，這裡先特別介紹一個非常簡單的protocol interference model，並使用最直接的可能的conflicting set l of e = 集合E except edge e，也就是說在任何給定的時間點最多只有一個edge可以被activate，換句話來說，如果不是只有一個edge是active的，就代表沒有任何edge是active的。這個版本的model稱為01protocol model，雖然這個model過於簡化，可是對於比較上是一個很有用的term。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) The 01protocol model takes the most conservative approach to interference protection so space diversity is not exploited to obtain transmission parallelism this situation necessarily occurs in certain special topologies Indeed, it is true that the 01protocol model holds here but the reason is not electromagnetic interference but rather that the topology is a star network Therefore, this situation is due to the wireless transceiver constraint, not to interference 01protocol model使用的是最保守的方式來避免interference，所以space diversity就沒有被採用而達到平行傳輸，而且實際上這種情形也只出現在特定的topology。事實上，01protocol model使用的原因並非是電磁的interference，而是因為topology是一個star的network，也就是每個node都會被access point所連接。因此呢，這樣的情形是由於上一個提到的wireless transceiver constraint，並不是因為interference的關係。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) Apart from the 01protocol model other versions rely on propagation aspects, described with simplified geometric approaches The idea is to define interference regions, areas of the physical space where ongoing transmissions interfere with each other and cannot coexist We also remark that most of the existing work takes a very simplified approach the interference region is modeled as a circular area with fixed range equal for all nodes Within these regions, the rationale of the 01protocol model is kept the limitation of having at most one active transmission is restricted to a smaller region translates to a different definition of the set l(e) 除了01protocol model之外，其他的protocol model都使用propagation的觀點，並由由簡化的幾何來描述這個部份。構想是定義interference的區域，ongoing的transmission彼此會互相干擾而且不可以共存。這裡也談論到一個非常簡化的方式，將所有node的interference的區域model成一個圓形的固定範圍。在這些區域裡，01protocol model還是有使用到，只是最多只有一個active transmission的這個限制只會在一個較小的區域當中，所以對於conflicting set l of e 也有不一樣的定義。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) In the following we implicitly assume that all propagation and interference aspects are again described through the graph G = (N, E) not only can node i ∊ N transmit to j ∊ N if and only if (i, j) ∊ E but also, i can disturb other transmissions intended for j from other nodes For simplicity we assume that the transmission range of a node equals its interference range additional virtual links not representing any real communication, just interference We call hereafter the 11protocol model, it is implicitly assumed that IEEE 802.11 MAC is employed 接下來的部份，仍然假設透過graph G=(N,E)來描述propagation與interference的觀點，如果link (i, j)存在的話不僅node i 可以傳送給node j ，而且node i 也會disturb其他node對node j 的傳輸。這裡假設一個node的傳輸範圍相等於他的interference範圍，藉由virtual的link來表示interference而非node間的communication。在接下來的部分稱為11protocol model，這個model假設採用了IEEE 802.11 MAC。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) Following IEEE 802.11 MAC, the 11protocol model dictates a transmission on (i, j) ∊ E is interference-free can therefore be activated only if there are no transmitters or receivers belonging to any active link that can disturb either i or j The reason for requiring the absence of interferers in both the receiver’s and transmitter’s disturbance area of both interfering transmitters and receivers is that the IEEE 802.11 standard forces the receiver to acknowledge request to send (RTS) and data packets with clear to send (CTS) and acknowledgments (ACKs), respectively 11protocol model規定說，link (i, j)上的transmission是interference-free而可以被activate，只有在沒有任何的transmitter跟receiver，是在active link下而會影響node i 或node j。那對於要求傳送與接收端在干擾區域內都不能有interferer存在的原因呢，是因為IEEE 802.11標準會要求receiver要acknowledge RTS與傳送CTS和ACK，而transmitter也需要回送ACK的關係。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) This also justifies the need for the existence of both forward and reverse links A possible definition of l(e) in the 11protocol model is thus (3) This condition can be relaxed if the IEEE 802.11 MAC protocol is not used between the handshake procedures of IEEE 802.11 and IEEE 802.16 那這也產生了forward與reverse link都存在的需求。以下是11protocol model內conflicting set l of e的定義，前半部是說當link (k, l)存在set E中，k, l 集合與i, j集合是沒有交集的，後半部是指i, j與R sub k 聯集 R sub l 的交集不為空集合。意思是指任何其他node無論是transmitter k 或receiver l 只要其中一個可以傳送給node i 或node j都會產生干擾，所以當link (i, j)是activate時，這些transmitter k 或receiver l 都不能activate link。而這個條件當不是使用IEEE 802.11 MAC時比較不用那麼嚴謹，例如像是使用IEEE 802.16的時候，不過他們的handshake過程不同，所以node之間的interference關係也會改變。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) We can then formulate a 16protocol interference model with the notable exception that collision occurs only when the designated receiver is interfered by another transmitter any other combination does not do any harm This formally results in (4) If the MAC protocol does not require acknowledgment the 16protocol model would be more appropriate 這裡接著介紹了一個16protocol interference model，與11protocol model進行的方式一樣，不同一點是，只有當指定的receiver被其他的transmitter干擾時才有collision的產生。其他像是目前的transmitter在別的會干擾的transmitter範圍之下，或是另一個receiver覆蓋到目前的receiver或transmitter等的情況都不會造成損害。他的conflicting set l of e 的公式如下，前半部與11protocol model相同，後半部則為node j 屬於 R sub k，意思是說，當link (i, j) activate時，其他可以傳送給node j 的transmitter k都不能有link被activate。 所以，當link不是雙向的而且MAC也不是IEEE 802.11的標準，就不需要使用11protocol model。而且如果MAC protocol不需要acknowledge的話，16protocol model將會比較合適。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) The protocol interference model is easy to implement offers several possibilities to both describe MAC aspects and employ the preferred mathematical model In fact, all versions of the protocol model are imperfect in capturing wireless interference the characterization of wireless propagation is not entirely realistic interference is not a binary relationship the problem is the joint effect of all of them conflict set l(e), which must be evaluated pairwise can be overcome by means of the physical interference model Protocol interference model在實行上很容易，也提供幾個描述MAC觀點與採用數學model的可能性。但事實上，所有的protocol model對於interference的capture都是不夠好的，首先，無線傳輸特性並非完全是實際的，其次，interference並不是一種二元的關係，因為沒有具體的link去造成interference，問題在於他們是共同的影響，所以conflict set l of e 就必須要兩兩去計算，也就會變的不適用，但這樣的問題可以藉由physical interference model來克服，那physical interference model的理論將在接下來會介紹。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) The packet error rate (PER) at the receiver is a monotonically increasing function of the signal-to-interference-plus-noise ratio (SINR) It is often reasonable to consider a simplified threshold approach a packet is correctly received with probability1 if the SINR is above a given threshold Receiver的packet error rate對於signal-to-interference-plus-noise ratio是一個單調遞增函數，在這邊考慮了一個threshold的approach，如果SINR超過一個給定的threshold時，就當作packet被正確接收到的機率為1。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) Formally, the following condition must hold (5) (i, j) is the link of interest the index k in the sum denotes a possible interferer Px is the power emitted by node x Nj is the receiver noise at node j γ, which defines the SINR threshold, equal for all nodes We neglect the noise terms, and we consider an equal power level P among all transmitting nodes the power level used by each node is constant over time any element gij can be replaced by g’ij = gijPi, thus omitting the power term 以下是這個threshold的算式，P sub i 乘上 g sun ij 除以 sigma k 不等於 i P sub k 乘上 g sub kj 加上 N sub j 會大於等於γ，其中(i, j)為目前要activate的link，用k來表示除了i以外可能干擾node j 的其他節點，視為interferer，P sub x 代表node x所發射的能量，N sub j 是node j 的noise，最後的gama則是所要給定的一個SINR值，對每個node都相等。因為這裡忽略了noise並假設每個node的power level都相同，也就是在任何時間點來說都為一個常數，所以每個g sub ij 都可以改寫為g’ sub ij 等於 g sub ij 乘上 P sub i，所以這裡將power的部份省略不計。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) In the context of our framework, which describes JRS through link activation patterns, the constraint can be formalized as follows (6) Reducing the PER function to a step function with transition value γ is indeed an approximation still much more accurate than the ones made under the protocol models it better takes into account physical propagation 這篇論文提到的framework，是藉由link的activation來描述JRS，因此physical interference model可以寫成如下的公式，if X sub ij of t 等於 1，then g sub ij 會大於等於 gama 乘上 sigma k 屬於 S sub j except i 的 g sub kj 再乘上 sigma l 屬於 R sub k except j X sub kl of t。所代表的意義是說，如果link (i, j)是active的時候，那麼代表link (i, j)的g sub ij的值，會大於等於其他除了node i 以外的其他transmitter k傳送給node j 的g sub kj的總和再乘上X sub kl的總和，雖然packet error rate是用gama去做近似值，但是準確性仍比任一個protocol model要來的高，因為physical interference model考量了實體的傳輸部分。 2019/1/17 NTU IM OPLAB

Wireless Interference Constraint (cont’d) Opposed to the collision assumption a correct packet reception is allowed even in the presence of interference and the cumulative character of interference is accounted for 此外，這個model與collision的假設有些不同，即使存在一些interference的情形下，packet還是可以被正確的接收，而且interference的計算是累加起來的。以下是對於每個interference model的數學化公式與理論的一個分類，我再稍微簡單綜合一下這幾個model的概念，protocol model的主要方式呢，是當link e active的時候，所有屬於conflicting set l of e 中的所有link都必須是inactive，而對於l of e 的定義有些不同，所以分成三個不同的protocol model，01protocl model限制最多，因為整個網路中一次只能有一個link是active的，11protocol model則是會使transmitter i 與receiver j 受到干擾的link才列入conflicting set，16protocol model的話限制最少，只有會干擾receiver j 的其他transmitter k 的link才屬於conflicting set，而physical model的方式則是當link e 是active時，這個link的SIR值就必須大於某個給定的threshold，相對來說，限制又更少了一些。不過protocol model的概念簡單，也提供比較簡單的方式去表示constraint，但在別篇論文中提到physical model在WMN中JRS的成效比protocol model要來的好，關於這個觀點，接下來會藉由幾個example來做探討。 2019/1/17 NTU IM OPLAB

Performance Evaluation

Performance Evaluation In this section we focus on the JRS problem satisfy all the constraints efficiently deliver traffic to the MAPs time slot is equal to the packet transmission time assumed, for simplicity, the same for all nodes We focus on the minimal time scheduling problem: to deliver a given amount of traffic from all non-gateway MRs to the MAPs in the shortest possible time 在這個section，focus JRS的problem在以下幾個部分上，定義link activation不僅要滿足所有的constraint，並可以傳送資料給mesh access point，還有對於所有node來說，time slot大小與packet transmission time相同，這個是為了簡化而作的假設。也focus在最小化scheduling的problem，也就是經過所有MR到MAP之間的最小傳送時間。 2019/1/17 NTU IM OPLAB

Performance Evaluation (cont’d) With minor modifications, our framework can work to solve other problems as well where the goal is throughput maximization or fairness and/or prioritization An interesting direction for future research take into account variations of the estimated traffic from each MR can also be envisaged We have implemented our framework to verify the transmissions’ compatibility providing support for all the interference models 這裡的framework只要做一些修改，也可以用來處理其他的問題，像是throughput的最大化，不同MR之間traffic的fairness和優先權等等，同時也提到了一點，就是將每個mesh router的traffic variation列入考量，也會是一個未來的研究方向。那為了要評估interference model在performance結果上的影響，這裡使用framework來證實transmission的相容性，並提供support給文中提及的那些interference model。 2019/1/17 NTU IM OPLAB

Performance Evaluation (cont’d) We stress that the derivation of efficient algorithms to solve the minimal time scheduling problem is out of the scope of this article We have computed within a simulator the optimal link schedule with an exhaustive search over all possible link activation patterns that are feasible according to the constraints We consider a grid topology consisting of 30 m × 30 m squares Nodes occupy the grid intersections in a contiguous manner We consider 2 × 3, 3 × 3, 3 × 4, and 4 × 4 grid placements of the nodes We assume that there is only one MAP in the network each of the other MRs has 12 packets to transmit toward the gateway 另外這裡強調了有效的演算法推衍來處理scheduling的最小化並非這篇論文的研究重點。那這篇論文呢，透過所有符合interference model中constraint的link在模擬器中計算最佳化的link schedule 。這裡考量一個900平方公尺的grid topology，每個node都在grid的交叉點上，並有2*3 3*3 3*4以及4*4這四種分佈方式，並假設只有一個MAP位在角落的位置，每個MR都有12個packet要傳送到MAP。 2019/1/17 NTU IM OPLAB

Performance Evaluation (cont’d) Wireless propagation is modeled by considering a simple path loss expression proportional to d–4 d is the sender-receiver distance A link (i, j) is included in E when its gain gij is higher than –60 dB with respect to the attenuation at 1 m all nodes can only communicate with their physical one-hop neighbors We stress that the validity of the conclusions holds for any scenario also when more complicated propagation models are used to determine gij 無線傳輸的path loss與d的負4次方成比例，d代表的是傳送與接收端之間的距離。那link (i, j)的g sub ij的值要高於負60dB，和1公尺的衰退才會include在集合E之中，這樣會導致所有的node都只能與相隔one-hop的鄰近節點通訊。那這篇論文也強調結論的有效性，對於其他的scenario以及不同的propagation model所定義的g sub ij，都可以有效適用。 2019/1/17 NTU IM OPLAB

Performance Evaluation (cont’d) We report the length of the optimal schedule computed when either protocol or physical interference models are adopted 01protocol model 01protocol model Γ=6 dB 下面兩張圖呢，左邊是interference model，右圖是physical model分別在計算最佳化的schedule所花費的時間。兩邊也都加入了01protocol model的結果，以及No interference的情況，no interference指的是只考慮在剛開始時第一個提到的wireless transceiver constraint的部份，不考慮interference constraint，所以SIR的threshold的gama值也就等於0。01protocol model在schedule length的圖形中是一個upper bound，沒有任何同時的transmission是被允許的，反之，no interference的情況則為圖形的lower bound，因為最大的平行傳輸是被認可的。在左圖也就是interference model的圖形可以看到，每種grid的case下，schedule length與node的數量幾乎是呈現性成長的，而斜率則取決於所採用的model而不同。那如同預期的一樣，限制越多的model，所對應的schedule length也就越長，從11protocol model與16protocol model在4*4的grid case下，有最大的gap，大約是30個slot。而右圖的physical model也有相同的情形，schedule length也隨node數增加而變長，此外，因為SIR值的增加會降低平行傳輸，而導致schedule length也會隨SIR值增加而變長。而有一點直得注意的是，physical model可以提供一種與no interference情形相近的結果，而且physical model可以得到比較大range的結果，只要藉由微調threshold的值，就會有不同的performance level，例如當threshold為6dB時，結果與16protocl model結果很相近，而當threshold為2dB時，則很接近no interference的performance。 Γ=2 dB No interference No interference 2019/1/17 NTU IM OPLAB

Performance Evaluation (cont’d) The most important consequence the physical interference model definitely allows a higher degree of tunability better capability of capturing wireless interference The trend shown for relatively higher network sizes exhibits a steeper increase of the schedule length for the protocol models because the cumulative character of the interference becomes more relevant Thus, using the physical model allows higher scalability more accurate evaluation of the schedule length when the number of nodes grows the protocol models further degrade the performance 那經過以上這些分析後，可以得到一個重要的結果，physical interference model在微調上允許有較高的degree，也有較好的能力去capture interference。此外，當network的size變大時，protocol model的schedule length也比physical model有較為急劇的增加，這仍然是因為interference的累加特性是更為相關的。因此，physical model可以有比較高的scalability，因為當node數增加時，physical model對於schedule length有比較準確的評估，然而protocol model卻會降低performance。 2019/1/17 NTU IM OPLAB

Conclusion

Conclusion The choice of the right interference model depends on many factors ease of implementation the possibility of obtaining realistic results no definitive choice among the models presented here The widespread use of protocol interference models adopts nonuniform notations that need to be harmonized our taxonomy aims to clarify the differences among the possible choices Moreover, all the protocol models lead to performance limitations they are very restrictive and obtain lower network parallelism silencing allegedly colliding connections 選擇正確的interference model有很多因素，包括implementation的難易程度，還有可以得到的實際效果，所以在這些model中並沒有一個決定性的選擇。這篇論文還談到，protocol interference model的普遍使用上都採用非制式的名稱，而需要去協調好，這裡提到的分類，目的是為了分辨在選擇上的不同之處。此外，所有的protocol model都讓performance受到限制，由於protocol model認為要消除會碰撞的connection所以constraint也比較嚴格，而使得網路的平行較低。 2019/1/17 NTU IM OPLAB

Conclusion (cont‘d) The more accurate characterization of the system obtained by utilizing the physical model reveals interesting behaviors may lead to reconsidering the design criteria of access protocols for WMN Although the mesh versions of both IEEE 802.11 and IEEE 802.16 take these aspects into account the protocol design of improved interference-aware JRS strategies is still an open research challenge 在使用physical model時，系統的特性可以更精確，而這樣的結果也許也可能使得WMN的access protocol的設計標準得以重新去考量。最後呢，雖然IEEE 802.11與802.16的mesh都有將這些觀點納入考量，不過interference-aware的JRS的protocol設計仍然是一個open的research challenge。 2019/1/17 NTU IM OPLAB

Thanks for you listening