臺灣博碩士論文加值系統

在無線網路，尤其是感知無線電網路(cognitive radio networks)及無線網狀網(wireless mesh networks)中因為傳輸比較不可靠使得網路整體效能降低。臨機路由(opportunistic routing)藉由動態調整傳輸路徑來解決因為固定傳輸路徑所造成的效能低落問題，在這樣的傳輸機制下，我們歸納其網路傳輸速率受限於傳給最後目標的封包是否對最後目標來說是新的。我們使用網絡編碼(network coding)的概念找出網路中的最小截流(min-cut)，以此來算網路的理論傳輸速率的界限。我們的分析結果顯示傳輸速率界線與網路中最多能夠同時傳輸的數量有關，並且傳輸的路徑數也會影響傳輸速率。
接著我們探討在多個具相關性的信源(correlated sources)時，路由機制該如何設計使得網路整體的傳輸量能夠最有效率。我們假設在無線網路中，信源能夠透過偷聽(overhearing)的方式做更有效率的傳輸，也就是說，信源能夠由偷聽到其他信源所傳送的訊息，判斷自身如何最有效率的傳輸。根據這個假設，我們最後想要透過路由的機制使得整體網路的傳輸量能最有效率。為了分布式的方式達到整體的最佳化，我們用吉布斯採樣提出一套路由機制。我們將我們所提出的演算法與貪心演算法做比較，模擬結果顯示我們的演算法比貪心演算法有著顯著的改善，改善的程度也與信源的相關程度有關。

In wireless network, the broadcast feature makes the transmission link unreliable in certain network, like cognitive radio network or wireless mesh network. The opportunistic routing is therefore been proposed to solve the problem. In opportunistic routing, the end-to-end transmission path is not pre-determined. Every node would be potential forwarder. In this routing mechanism, we conclude that the capacity is bound in the situation that whether the forwarders to destination have received an un-transmitted packet so that it can transmit to destination. To solve this problem we use the concept of network coding that we find the min-cut of network from source to those forwarders. Our analytical result shows that the capacity is related to the total transmission links within T time slots, and the capacity will also increase with the number of transmission paths.
The second part of our work does the multi-sources, single destination network while the sources are correlated, which is most likely the wireless sensor network. We use the overhearing information to improve traffic efficiency, i.e., every node can do data compression by the transmitting information message that it overhears from its neighboring nodes. We let each sensor choose its forwarder, and also do efficient transmission by the overhearing message of its possible forwarders. Our goal is to minimize the total transmitting information message from every source nodes and relay nodes. To obtain a distributed routing algorithm, we use the Gibbs sampler which theoretically can approach to global optimal by local information. We compare our algorithm with greedy approach, and the simulation result shows that our algorithm improves the total transmitting information message significantly. We also find that the improvement is related to how correlated of sources.

Abstract i
Contents iii
List of Figures vi
List of Tables viii
1 Introduction 1
1.1 Transmission Issue in Wireless Communication 1
1.1.1 Problem of Lossy Link in Wireless Network 2
1.1.2 Problem of Routing in Correlated Source Network 3
1.2 Organization 4
2 Preliminary 6
2.1 Opportunistic Routing and Network Coding 6
2.1.1 Opportunistic Routing 6
2.1.2 Network Coding 9
2.2 Optimal Rate of Correlated Source 11
2.3 System Model 13
2.3.1 Network Topology 14
2.3.2 MAC Mechanism 15
3 Capacity Bound in Opportunistic Routing 18
3.1 Problem Formulation 18
3.1.1 Problem Description 18
3.1.2 Transmission Cut 19
3.2 Bound of Capacity and Analytical Result 21
3.2.1 The Min Cut of Network 21
3.2.2 Problem Verification 23
3.2.3 Analytical Result 26
4 Routing Mechanism in Correlated Sources 29
4.1 Problem formulation 29
4.1.1 Problem Description 29
4.1.2 Flow Conservation Rule in Wireless Network 31
4.1.3 Optimization Formulation 33
4.2 Gibbs Sampler 38
4.2.1 Introduction to Gibbs Sampler 38
4.2.2 Modification and Proposed Algorithm 39
4.3 Simulation result 41
4.3.1 The Routing of Small Deterministic Network 41
4.3.2 Undirected Network 42
4.3.3 Directed Network 45
5 Conclusion and Future Work 47
5.1 Conclusion 47
5.2 Future Work 48
Bibliography 50

[1] S. Haykin, “Cognitive radio: brain-empowered wireless communications,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 2, pp. 201–220, Feb. 2005.
[2] K.-C. Chen, B. K. Cetin, Y.-C. Peng, N. Prasad, J. Wang, and S. Lee, “Routing for cognitive radio networks consisting of opportunistic links,” in Wireless Communications and Mobile Computing.
[3] M. Rodrig, C. Reis, R. Mahajan, D.Wetherall, and J. Zahorjan, “Measurementbased characterization of 802.11 in a hotspot setting,” in ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, 2005.
[4] H. Yu, D. Wu, and P. Mohapatra, “Experimental anatomy of packet losses in wireless mesh networks,” in IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON ’09. 6th Annual.
[5] P. Djukic and S. Valaee, “Reliable packet transmissions in multipath routed wireless networks,” IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 548–559, Aug. 2006.
[6] A. Tsirigos and Z. Haas, “Analysis of multipath routing-part i: The effect on the packet delivery ratio,” IEEE Transactions on Wireless Communications, vol. 3, no. 1, pp. 138–146, Jan. 2004.
[7] S. Biswas and R. Morris, “Exor: Opportunistic multi-hop routing for wireless networks,” in ACM SIGCOMM, 2005.
[8] K. Sohrabi, V. Gao, J.and Ailawadhi, and G. Pottie, “Protocols for selforganization of a wireless sensor network,” Personal Communications, IEEE, vol. 7, no. 5, pp. 16–27, Oct. 2000.
[9] J. Yuan and W. Yu, “Joint source coding, routing and power allocation in wireless sensor networks,” IEEE Transactions on Communications, vol. 56, no. 5, pp. 886–896, Jun. 2008.
[10] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19, pp. 471–480, Jul. 1973.
[11] S. Pradhan and K. Ramchandran, “Distributed source coding using syndromes (discus): Design and construction,” IEEE Transactions on Information Theory, vol. 49, no. 3, pp. 626–643, Mar. 2003.
[12] V. Stankovic, A. Liveris, Z. Xiong, and C. Georghiades, “On code design for the slepian-wolf problem and lossless multiterminal networks,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1495–1507, Apr. 2006.
[13] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading structure for randomness in wireless opportunistic routing,” in ACM SIGCOMM, 2007.
[14] T. Ho, M. Medard, R. Koetter, D. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” vol. 52, no. 10, Oct.
2006, pp. 4413–4430.
[15] D. S. J. De, D. S. J. Couto, D. Aguayo, R. Morris, and J. Bicket, “A highthroughput path metric for multi-hop wireless routing,” in IEEE Mobicom 03.
[16] X. Zhang and B. Li, “Optimized multipath network coding in lossy wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 5, pp. 622–634, Jun. 2009.
[17] Y. Li, Y. Jiang, D. Jin, L. Su, L. Zeng, and D. Wu, “Energy-efficient optimal opportunistic forwarding for delay-tolerant networks,” IEEE Transactions on Vehicular Technology, vol. 59, no. 9, pp. 1500–1512, Nov. 2010.
[18] R. Ahlswede, N. Cai, S.-Y. Li, and R. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, Jul.2000.
[19] R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782–795, Oct.2003.
[20] S.-Y. Li, R. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003.
[21] R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear coding in network information flow,” IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2745–2759, Aug. 2005.
[22] S. Katti, H. Rahul, D. K.W.Hu, M. Medard, and J. Crowcroft, “Xors in the air: Practical wireless network coding,” IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 497–510, Jun. 2008.
[23] J. Le, J. C. Lui, , and D. Chiu, “Dcar: Distributed coding-aware routing in wireless networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 4, pp. 596–608, Apr. 2010.
[24] Y. Lin, B. Li, and B. Liang, “Stochastic analysis of network coding in epidemic routing,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 5, pp. 794–808, Jun. 2008.
[25] T. M. Cover and J. A. Thomas, Elements of information theory. Wiley Interscience, 1991.
[26] S. Fujishige, “Algorithms for solving the independent-flow problems,” J. Operations Res. Soc. Japan, pp. 189–204, 1980.
[27] J. Liu, M. Adler, D. Towsley, and C. Zhang, “On optimal communication cost for gathering correlated data through wireless sensor networks,” in IEEE Mobicom 06.
[28] J. Barros and S. Servetto, “Network information flow with correlated sources,” IEEE Transactions on Information Theory, vol. 52, no. 1, pp. 155–170, Jan. 2006.
[29] A. Ramamoorthy, “Minimum cost distributed source coding over a network,” IEEE Transactions on Information Theory, vol. 57, no. 1, pp. 461–475, Jan. 2011.
[30] S. M. Cheng, W. C. Ao, F. M. Tseng, and K. C. Chen, “Downlink spectrum sharing of two-tier cohgnitive femto networks,” submitted to IEEE Transactions on Vehicular Technology.
[31] A. Ramamoorthy, J. Shi, and R. D. Wesel, “On the capacity of network coding for random networks,” IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2878–2885,, Aug. 2005.
[32] W. C. Ao and K. C. Chen, “Degree distribution in interference-limited heterogeneous wireless networks and its generalizations,” in IEEE ICC proceedings.
[33] W. C. Ao and K.-C. Chen, “Degree distribution in interference-limited heterogeneous wireless networks and its generalizations,” in IEEE ICC proceeding.
[34] D. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1439–1451, Aug. 2006.
[35] S. Gemana and D. Geman, “Stochastic relaxation, gibbs distributions and the bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, pp. 721–741, Nov. 1984.
[36] P. Bremaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, 1999.
[37] B. Karp and H. T. Kung, “Gpsr: greedy perimeter stateless routing for wireless networks,” in MobiCom ’00 Proceedings of the 6th annual international conference on Mobile computing and networking.
[38] C.-H. Chou, K.-F. Ssu, and H. Jiau, “Geographic forwarding with dead-end reduction in mobile ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 57, no. 4, pp. 2375–2386, Jul. 2008.
[39] C. Fenhua and J. Min, “Improved gpsr routing algorithm and its performance analysis,” in IEEE International Conference on Software Engineering and Service Sciences (ICSESS), 2010.
[40] J. Liu, D. Goeckel, and D. Towsley, “Bounds on the gain of network coding and broadcasting in wireless networks,” in IEEE INFOCOM proceeding.