綠色無線接取網路之通訊協定設計與實作

Protocol Design and Implementation for Green Wireless Access Networks

劉文俊(Wen-Jiunn Liu)

指導教授 ： 方凱田

國立交通大學/電機學院/電信工程系所/博士(2010年)

https://doi.org/10.6842/NCTU.2010.01060

摘要

近年來由於節能省電與環境友善議題發酵，綠色觀念 (Green Concept) 得到了很多方面的注意。如何設計一個綠色無線接取網路也已經在通訊領域變成一個相當熱門的主題。在網路系統設計方面，通訊堆疊最重要的部分通常為網路層(Network Layer)、資料連結層 (Data Link Layer) 和實體層 (Physical Layer)，因為這三層最被通訊端點與通訊中介點所使用。然而實體層通常與所存取的媒介體相關，因為不同的媒介體會有不同的訊號產生與調變方式。因此在設計與媒介體獨立的演算法或通訊協定方面，網路層和資料連結層吸引了更多的注意。於是為了要建立一個綠色無線接取網路，本論文在網路層和資料連結層上提出了一系列的節能通訊協定設計與相關的實作方式。
在網路層通訊協定設計方面，基於貪婪選徑演算法 (Greedy Forwarding, GF)，本論文分別為二維平面與三維空間，提出貪婪抗無效問題選徑演算法 (Greedy Anti-void Routing, GAR) 和三維貪婪抗無效問題選徑演算法 (Three-Dimensional Greedy Anti-void Routing, 3D-GAR) 作為低通訊消耗且保證到達的單播演算法 (Unicast)。對於低通訊消耗多播演算法 (Multicast) 設計方面，本論文也提出了一個節能省電多播選徑演算法 (Energy Conserving Multicast Routing, ECMR)，用以減少多播樹 (Multicast Tree) 通訊中介點的個數。此演算法可以顯著的降低非必要的通訊花費。此外，本論文基於 Linux 嵌入式系統提出了元件導向選徑實作平台 (Component-based Routing Platform, CRP) 用以實現這些所提出的選徑演算法。以上所提出的網路層通訊協定可以直接使無線接取網路更省電綠化，因為通訊花費的節省可以直接降低能源的消耗。
在資料連結層通訊協定設計方面，依同樣能源消耗下，系統吞吐量的加強可以視為一種非直接的方式實現綠色無線接取網路，因為平均傳輸每單位資料所消耗的能源可以被降低。因此本論文提出了一種貪婪快速移動區塊確認演算法(Greedy Fast-Shift Block Acknowledgement, GFS)，透過減少傳統區塊確認演算法中緩慢移動確認窗(Acknowledgement Window) 所帶來的負面效應，最後加強整個系統的吞吐量。除了加強系統吞吐量這種非直接方式，另外還有一種直接的方式，即：透過節能省電排程演算法可以直接達成節能省電的目的。節能省電排程演算法可以透過適當的封包傳輸安排，減少最終的總能源消耗量。因此本論文對於此直接省電的分類，也提出了一種訊框聚集節能省電排程演算法 (Frame Aggregation-based Power-Saving Scheduling Algorithm, FAPS)，此演算法可以將數個未填滿的訊框合併成為一個填滿的訊框，進而達到節能省電的目的。另外值得注意的是本訊框聚集節能省電排程演算法仍然可以維持住每個封包的服務品質 (Quality-of-Service, QoS)。此外，訊框聚集節能省電排程演算法在輸入皆為階梯狀允許空間 (Stepwise Grant Space Set) 的條件之下，也可以產生最少的聆聽訊框 (Listen Frame)。相關的正確性證明皆整理並提供於本論文之內。最後多數的系統訊框皆可以處於在睡眠模式之下，睡眠模式可以消耗相對於正常模式還少的能源，因此可以達成節能省電的目的。透過本論文所提出在網路層與資料連結層上的軟體通訊協定設計與實作，綠色無線接取網路將可以被廣泛的建立與使用。

關鍵字

綠色無線網路 ； HASH(0x9f7e9e0) ； 通訊協定設計 ； HASH(0x9f7fab4) ； 通訊協定實作

並列摘要

In recent years, the green concept has received more attention due to the energy efficient and environmentally friendly issues. How to develop the green wireless access network also has become a hot topic in the communications society. In terms of the network system design, the most important parts of the communication stacks are in general the network layer, the data link layer, and the physical layer since these three layers are utilized mostly in the terminal hosts and the intermediate nodes. However, the physical layer is usually medium dependent for signaling different transmission media. As a result, the network layer and the data link layer will gain more attraction in designing the medium independent algorithms and protocols. Therefore, in order to achieve the green wireless access networks, the protocol design and implementation on the network layer and the data link layer are collectively proposed in this dissertation.
In the network layer protocol design, a greedy anti-void routing (GAR) protocol and the three-dimensional greedy anti-void routing (3D-GAR) protocol for both two-dimensional and three-dimensional environments are proposed as the low-overhead delivery-guaranteed unicast routing protocols based on the well-known greedy forwarding (GF) algorithm. In the low-overhead multicast routing protocol design, an energy conserving multicast routing (ECMR) protocol is also proposed to reduce the total number of relaying nodes for the construction of a multicast tree, which can significantly eliminate the unnecessary communication overheads. Moreover, based on the Linux embedded systems, the associated component-based routing platform (CRP) for implementing routing protocols is also introduced. These proposed network layer protocols can make the wireless access networks greener directly since the reduction of the communication overheads can effectively suppress the energy expenses.
On the other hand, in the data link layer protocol design, the system throughput enhancement under the same power consumption can be considered an indirect way to realize the green wireless access networks since the power expenses can be degraded for transmitting the same amount of information. As a result, the greedy fast-shift block acknowledgement (GFS) mechanism is proposed for enhancing the system throughput by reducing the inefficiency caused by the slow sliding of the conventional acknowledgement window. Thanks to the fast shifting property of the acknowledgement window in our proposed GFS scheme, significant throughput enhancement can therefore be observed. In addition to the indirect method of enhancing the system throughput, the direct method for achieving the green concept should be the power-saving scheduling algorithm, which can arrange the packets with the proper transmission schedules, suppressing the total energy consumption. The frame aggregation-based power-saving (FAPS) scheduling algorithm is therefore proposed for this type of direct methods by aggregating several under-utilized frames into fully-utilized ones. The quality-of-service (QoS) of each data packet can still be maintained in our proposed FAPS algorithm. In addition, the optimality on the minimum number of listen frames in the proposed FAPS algorithm is also provided under the stepwise grant space set and further verified via the correctness proof. Finally, more number of system frames can be in the sleep mode, which consumes less energy compared to the active mode. With our proposed software protocol design and implementation in the network layer and the data link layer, the green wireless access networks can therefore be achieved.

並列關鍵字

Green Wireless Network ； HASH(0x9f7fc1c) ； Protocol Design ； HASH(0x9f7fce8) ； Protocol Implementation

參考文獻

[3] S. Vadgama, “Trends in Green Wireless Access,” Fujitsu Sci. Tech. J., vol. 45, no. 4, pp. 404-408, Oct. 2009.

[5] B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in Proc ACM/IEEE Int. Conf. Mobile Computing and Networking (MobiCom'00), Aug. 2000, pp. 243-254.

[6] F.K. Hwang, D.S. Richards, and P. Winter, The Steiner Tree Problem. Elsevier, North-Holland, 1992.

[8] I. Stojmenovi’c and X. Lin, “Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks,” IEEE Trans. Parallel Distrib. Syst., vol. 12, no. 10, pp. 1023-1032, Oct. 2001.

[9] R. Jain, A. Puri, and R. Sengupta, “Geographical Routing Using Partial Information for Wireless Ad Hoc Networks,” IEEE Pers. Commun. Mag., vol. 8, no. 1, pp. 48-57, Feb. 2001.