Nghiên cứu giao thức đa truy cập ngẫu nhiên trong môi trường fading

Nội dung text: Nghiên cứu giao thức đa truy cập ngẫu nhiên trong môi trường fading

1. NGHIÊN CỨU GIAO THỨC ĐA TRUY CẬP NGẪU NHIÊN TRONG MÔI TRƯỜNG FADING RESEARCH MULTI ASSESS RANDOM PROTOCOL IN FADING ENVIRONMENT Trần Thanh Tôn Học viên cao học trường ĐHSPKT TPHCM TÓM TẮT Trong đề tài này tôi đã thực hiện mô phỏng và đánh giá giao thức đa truy cập ngẫu nhiên trong môi trường fading. Thuật toán truyền gồm có 2 phần: Một quyết định nhị phân dựa vào truyền dẫn và một điều chỉnh backoff kênh đoán trước. Trong quyết định nhị phân dựa vào truyền dẫn quyết định việc có nên truyền hay không phụ thuộc tuyệt đối vào điều kiện của kênh truyền hiện tại. Một điều chỉnh backoff kênh đoán trước được sử dụng để ưu tiên các nút với điều kiện kênh truyền tốt hơn. Các mô phỏng được thực hiện trên các kênh truyền không dây fading. Kết quả cho thấy rằng, thuật toán truyền dẫn của tôi tốt hơn so với các phương pháp hiện tại về hiệu quả năng lượng, qua đó tiếp tục kéo dài tuổi thọ mạng. Từ khóa: backoff, quyết định Markov, cứa sổ tranh chấp ABSTRACT In this work we simulate and evualate multi assess random protocol in fading environment. Our transmission algorithm consists of two components: a binary-decision based transmission and a channel-aware backoff adjustment. In the binary-decision based transmission, decision on whether to transmit or not is absolutely dependent on the current channel conditions. Specifically, transmission is initiated only when the channel quality exceeds a specified threshold, so that unsuccessful transmissions causing a waste of energy are avoided whenever possible. A channel- aware backoff adjustment, is introduced to favor nodes with better channel conditions. Numerical results show that our transmission algorithm outperforms the existing approaches in terms of energy efficiency, thereby further prolonging the network lifetime. Keyword: backoff, MDP, CW I. GIỚI THIỆU Trong các mạng cảm biến không dây (WSNs) một số nút cảm biến được triển khai để thu thập các dữ liệu với pin nhỏ, khó khăn để thay thế[1]. Khi WSN hoạt động, hiệu quả năng lượng là một vấn đề kỹ thuật quan trọng trong thiết kế WSN [2]- [4]. Đặt biệt, quản lý chặc chẽ nguồn tài nguyên năng lượng là cần thiết để tối đa hóa tuổi thọ của WSN [5].
2. Các nút hoạt động trên kênh truyền không dây thay đổi theo thời gian có chất lượng thay đổi đáng kể do fading và nhiễu. Như vậy đặc tính thay đổi theo thời gian của kênh truyền không dây áp đặc nhiều hạn chế trong việc thiết kế một chương trình truyền hiệu quả năng lượng. Ví dụ, một nổ lực truyền tải, khi kênh truyền không dây tạm thời ở trạng thái xấu, rất có khả năng bị thất bại và dẫn đến sự lãng phí năng lượng. Để tránh điều đó, bên gửi có thể đợi cho tới khi kênh truyền tốt hơn. Tuy nhiên, trì hoãn việc truyền cho tới khi kênh truyền tốt hơn có thể làm giảm thông lượng hay làm cho độ trễ lớn hơn. Đây là một vấn đề cân bằng giữa hiệu quả năng lượng và thông lượng. Vì vậy một kế hoạch truyền dẫn hiệu quả cho mạng WSN phải có khả năng thích ứng với các biến thể của kênh truyền không dây trong khi duy trì sự cân bằng tốt giữa hai yếu tố tương phản. Ý tưởng này được thực hiện trong 2 phần của giao thức MAC (Medium Access Control): một quyết định nhị phân dựa vào truyền dẫn (BDT) và một điều chỉnh backoff kênh truyền (CBA). Trong phương án BDT, dù để bắt đầu truyền dẫn hay không được xác định theo các điều kiện hiện tại của kênh truyền. Bằng cách trao đổi các thông điệp điều khiển như RTS và CTS trong chuẩn 802.11 cho các phép đo kênh truyền và phản hồi của nó, tương ứng, bên nhận có thể đo lường chất lượng kênh truyền và bên gửi có thể nhận lấy thông tin đó qua thông điệp trả về. Để tiếp tục giám sát điều kiện kênh truyền, thông điệp dữ liệu và thông điệp ACK được sử dụng để đo lường và chứa các thông tin kênh truyền. Ngoài ra thuật toán CBA được giới thiệu để ưu tiên các nút cảm biến có các điều kiện kênh truyền tốt hơn. Đối với các nút cảm biến nó thấy một kênh truyền tốt hơn gần đây, một cái CW ( contention window) nhỏ hơn được gán cho truy cập kênh nhanh hơn, trong khi một CW tương đối lớn được đưa ra cho các trường hợp ngược lại. MDP được sử dụng để có ngưỡng tối ưu cho truyền dẫn thành công. Hơn nữa, một đề án truyền luân phiên được gọi là truyền dẫn phân mãnh (FT) được xem xét để so sánh với đề án BDT. Trong đề án FT, nút cảm biến có thể thực hiện một hành động khác của truyền dẫn phân mảnh trong đó toàn bộ khung được truyền trong các khung phân mãnh một cách liên tục để tránh việc truyền dẫn thất bại. Các mô phỏng mở rộng được thực hiện với Ns-2 để xác minh hiệu suất đề nghị của chúng tôi trên các kênh truyền fading không dây. Các thuật toán truyền dẫn được áp dụng cho chuẩn IEEE 802.11 DCF với một số sửa đổi cần thiết. II. PHƯƠNG PHÁP NGHIÊN CỨU Để hoàn thành mục tiêu, tôi thực hiện đề tài tiến hành theo trình tự :  Đọc và nghiên cứu các tài liệu trong và ngoài nước về vấn đề chuẩn IEEE 802.11, quy trình quyết định Markov
3.  Cài đặt phần mềm NS 2 trên môi trường Ubuntu  Xây dựng quy trình quyết định Markov trên matlab, thực hiện mô phỏng chương trình trên NS 2, tiến hành phân tích, đánh giá kết quả thu được III. MÔ HÌNH KÊNH TRUYỀN Một mô hình kênh truyền Markov trạng thái hữu hạn (FSMC) để nắm bắt hành vi thay đổi theo thời gian của kênh truyền fading không dây. Tại = E[y], yi là ngưỡng của SNR nhận được 0 = y0 < y1 < y2 < < yK = ∞.Các kênh ở trạng thái gk, 0 ≤ k< K nếu SNR nhận được trong khoảng [yk, yk+1). Chúng ta giả sử rằng quá trình chuyển đổi trong mô hình FSMC xảy ra tại ranh giới của khe thời gian trong đó một khung có kích thước cố định được truyền đi và sự thay đổi chỉ diễn ra giữa các trạng thái gần nhau như hình 2.14. Hơn nữa, độ lợi kênh truyền là hằng số trong một khe thời gian của truyền dẫn. Các thông số của mô hình Markov có thể thu được băng cách sử dụng các kỹ thuật trong [12]. Pg(0,0) Pg(1,1) Pg(K-1,K-1) Pg(0,1) Pg(1,2) Pg(K-2,K-1) 0 1 K-1 P (1,0) P (2,1) P (K-1,K-2) g g g Hình 1 Mô hình kênh truyền Markov trạng thái hữu hạn Chúng ta ký hiệu N(y) là tỉ lệ vượt mức cho bởi: 2 y y N() y f e (1) m fm là tần số Dopler tối đa, xác xuất chuyển đổi trạng thái được cho bởi: Tf P( k , k 1) N ( y ) , 0 k K 2 gk 1 k (2) Tf Pgk( k , k 1) N ( y ) , 1 k K 1 k Tf là thời gian truyền của khung, k là xác xuất trạng thái ổn định được cho bởi: yk 1 ky f() y dy (3) yk Cho trường hợp BPSK, xác xuất cho lỗi ký tự Pb(gk) cho trạng thái gk được cho bởi:
4. kk 1 Pgbk() (4) k IV. QUYẾT ĐINH NHỊ PHÂN DỰA TRÊN TRUYỀN DẪN (BDT) Trong đề án này, các nút cảm biến thực hiện một trong hai hành động: truyền và hoãn, tương ứng với việc truyền dữ liệu và hoãn truyền dữ liệu. Như hình 3.1, kênh truyền không dây hiện tại được đo tại bên thu thông qua RTS hoặc khung dữ liệu và được phân loại vào một trong hai trạng thái là tốt và xấu dựa vào SNR thu được. Thông tin này được thông báo lại cho phía phát bằng cách nhúng nó trong khung trả lại, đó là CTS hoặc khung ACK. Ngưỡng SNR được sử dụng để phân loại các trạng thái kênh được xác định bằng cách sử dụng MDP, được giải thích chi tiết trong phần sau. time Bên phát ) ) ) d d G d o o R R ó a o o T T i B G ( G t S S ( ( i Hoãn quá trình truyền n S K S T T C C C A Bên thu a) Quyết định nhị phân dựa vào truyền dẫn Bên phát ) ) ) ) ) K ) K d d d G d d d h h o e e e R e R ó a R u u o T T i B n n T M M M M ( G S ( ( t S ( g g S ( ( i n S 2 Hoãn quá trình truyền K K K S 1 S T C C T C T C C A A A C Bên thu b) Truyền dẫn phân mảnh Hình 2: Quyết định nhị phân V. MDP CHO HỆ THỐNG TRUYỀN Trong phần này vấn đề tìm các ngưỡng tối ưu cho truyền dẫn thành công được xây dựng bằng cách sử dụng MDP. Cho cả BDT và FT, nguyên tắc thực hiện tối ưu liên quan đến hiệu quả năng lượng đạt được. Để việc phân tích dễ dàng, giả sử thời gian đó được chia thành các khe thời gian có chiều dài bằng nhau của Tf dây. Ngoài ra các khe thời gian được giả sử là đủ ngắn với lưu lượng nhỏ do đó một khung đến ở mỗi khe thời gian theo một phân phối Bernoulli với tham số . Để xem xét các ứng dụng nó đòi hỏi cập nhật dữ liệu cảm biến dưới truyền tải nhẹ. Chúng tôi giả sử rằng, bộ đệm sẽ giữ ít nhất ở một khung. Nó cũng giả định rằng kết quả của sự truyền dẫn là có sẵn ngay lập tức ở cuối sự truyền dẫn. a. Các trạng thái hệ thống
5. Biểu diễn tập các trạng thái có thể có của hệ thống bằng S, S là một tập hữu hạn trạng thái của hệ thống si tại khe thời gian i được cho bởi: si g i, t i (5) gi là trạng thái kênh truyền tại khe thời gian i, 0 ≤ gi < K, và ti là trạng thái của nút cảm biến tại khe thời gian i. Các trạng thái có thể của nút cảm biến bao gồm Idle và Active. Nút cảm biến được gọi là ở trạng thái Active(Hoạt động) khi một khung nằm trong bộ đệm chờ quá trình truyền và trạng thái Idle(Nhàn rỗi) khi không có khung ở hiện tại. b. Các hành động điều khiển Tùy thuộc vào trạng thái hệ thống si, nút cảm biến xác định việc truyền hay hoãn sự truyền dẫn. A(si) là tập hợp các hoạt động điều khiển có thể của nút cảm biến tại trạng thái si và ai là hành động điều khiển thực hiện tại khe thời gian i. Cho mỗi hành động trong A(si) tương ứng với các giá trị sau: 0, Defer ai 1, Transmit (6) c. Chi phí của các hành động Trong trạng thái Idle (Nhàn rỗi), các nút cảm biến không thực hiện hành động, chi phí của các hành động là 0. Trong trạng thái Active(Hoạt động), chi phí phát sinh tức thời tại khe thời gian i được xác định như : Csaiii(,)(,)(,) E ceiit LgaE  Lga dii (7) Với Ec và Et là năng lượng tiêu thụ mỗi bit cho việc gửi gói tin điều khiển và gói tin dữ liệu tương ứng, là yếu tố quan trọng, biểu thị tầm quan trọng của mất khung về tiêu thụ năng lượng. Le(gi, ai) là tỉ lệ lỗi khung dự kiến , Ld(gi , ai) là số lượng dự kiến khung bị mất do tràn bộ đệm. Le(gi, ai) được cho bởi : Le(,)() g i a i a i P f g i (8) Pf(gi) là tỉ lệ lỗi khung tại trạng thái kênh truyền gi. Giả sử không phụ thuộc vào các bit lỗi. Tỉ lệ lỗi khung Pf(gi) cho khung có kích thước L và trạng thái gi được cho bởi : L Pf( g i ) 1 1 P b ( g i ) (9) Tại Pb(gi) có được từ (1). Ld(gi, ai) được cho bởi: Ld( g i , a i )  (1 a i ) a i P f ( g i ) (10)
6. d. Các tính động hệ thống Cho trạng thái hệ thống si = gi, ti và một hành động điều khiển ai, xác xuất của trạng thái hệ thống là si+1 = gi+1, ti+1 trong khe thời gian tiếp theo là: Pr s g , t | s g , t , a a i 1 i 1 i 1 i i i i (11) Pg ( g i , g i 11 ) P t ( t i , t i , a ) Pg(gi, gi+1) là xác xuất truyền từ trạng thái gi tới gi+1 và Pt(ti, ti+1, a) là xác xuất truyền của trạng thái các nút cảm từ ti tới ti+1 dưới hành động điều khiển a. Hình 3.3 mô tả sơ đồ trạng thái của các hành vi của nút cảm biến xác xuất truyền Pt(ti, ti+1, a) và chi phí tương ứng cho các hành động được cung cấp: λ, C=0 1, C=E+λδ Defer IDLE ACTIVE d 1-λ, C=0 Conflict Transmit (1-d)(1-λ )(1-Pf), C=Ec d+λ +(1-λ(1-d))Pf, C=Ec+PfEt+δλPf Hình 3. Sơ đồ trạng thái của đề án BDT VI. KẾT QUẢ
7. Bảng 1. Các tham số mô phỏng Giá trị (mặc Tham số định) Số nút cảm biến 21 Thời gian truyền khung (Tf ) 1ms Phạm vi truyền của các nút cảm biến 75m Mô hình truyền dẫn của các nút cảm biến CBR Khoảng cách các gói tin 1s Kích thước gói tin (L) 128 (bytes) Kích thước gói tin điều khiển 10 (bytes) fm 10Hz  0.02 Yếu tố trọng số trong hàm chi phí () 0.5 Chi phí sự phân mảnh () 0.01 Số phân mảnh của một khung (n) 2 Thời gian mô phỏng 1000 a. Thông lượng và trễ end to end của BDTd so với BDT ban đầu Hình 4 thể hiện thông lượng của truyền dẫn: BDT cải tiến so với truyền dẫn BDT ban đầu. Như thể hiện trong hình ta có thể thấy được thông lượng của mô hình BDT cải tiến khi thêm thông số tỉ lệ xung đột (d) trong quá trình truyền trên mô hình Markov làm giảm thông lượng so với mô hình truyền dẫn BDT ban đầu. Chính vì yếu tố d làm hoãn các quá trình truyền dữ liệu khi điều kiện kênh truyền xấu, khả năng xung đột giữa các nut trong quá trình truyền xảy ra cao. Tuy nhiên sự suy giảm này không đáng kể.
8. 160 150 140 130 120 110 Throughtput(kbit/s) 100 BDT 90 BDTd 80 6 7 8 9 10 11 12 13 14 SNR (dB) Hình 4. Thông lượng của truyền dẫn BDTd cải tiến so với BDT ban đầu b.Độ trễ của truyền dẫn BDTd so với mô hình BDT ban đầu Hình 5 thể hiện độ trể của truyền dẫn: BDT cải tiến so với truyền dẫn BDT ban đầu. 0.16 0.14 0.12 0.1 0.08 latency(s) 0.06 BDT 0.04 BDTd 0.02 0 6 7 8 9 10 11 12 13 14 SNR (dB) Hình 5 Độ trể của truyền dẫn BDTd cải tiến so với BDT ban đầu c.Hiệu quả năng lượng của mô hình BDT cải tiến so với mô hình BDT ban đầu Hình 6 thể hiện các kết quả mô phỏng của hiệu quả năng lượng cho đề án truyền dẫn: BDT cải tiến với BDT ban đầu với giá trị SNR có phạm vi từ 6 tới 14dB. Ở đây hiệu quả năng lượng được xác định như tỉ lệ số truyền dẫn thành công trên tổng số truyền dẫn. Như thể hiện trong hình 6, truyền dẫn BDT cải tiến có hiệu quả năng lượng cải thiện đáng kể so với mặt bằng BDT ban đầu. Và sự hiệu quả năng lượng này xuất phát chủ yếu từ việc
9. giảm số lượng mất khung do lỗi truyền dẫn bằng cách hoãn quá trình truyền khi trạng thái kênh xấu như thể hiện ở trên tỉ lệ xung đột xảy ra cao. Nhưng cũng chính điều đó làm giảm thông lượng quá trình truyền. 0.84 0.835 0.83 0.825 0.82 0.815 energy Efficiencyenergy 0.81 data1 BDTd 0.805 0.8 6 7 8 9 10 11 12 13 14 SNR (dB) Hình 6. Hiệu quả năng lượng của truyền dẫn BDTd cải tiến so với BDT ban đầu VII. KẾT LUẬN Sau khi tiến hành khảo sát các yếu tố của hệ thống: - Thông lượng của hệ thống khi thực hiện truyền dẫn. - Độ trễ end to end của quá trình truyền dẫn. - Tính hiệu quả năng lượng của hệ thống trong suốt quá trình truyền. Đề tài chứng minh được tính hiệu quả năng lượng của kế hoạch được đề xuất, cân bằng được yếu tố hiệu quả năng lượng với thông lượng so với các đề xuất, công trình khác đã đề xuất. Đề tài đã đề xuất một kế hoạch truyền dẫn năng lượng hiệu quả trong mạng WANs hoạt động trong một mô trường hạn chế nghiêm ngặt. Các thuật toán đề xuất cải thiện đáng kể hiệu quả năng lượng mà không phức tạp. Thuật toán của chúng tôi gồm 2 thành phần BDT và CBA. Bằng cách kết hợp thông minh các thành phần thuật toán truyền đã đề xuất đạt hiệu quả năng lượng cao hơn so với các phương pháp hiện tại, do đó kéo dài tuổi thọ mạng.
10. Đề tài chỉ dừng lại ở việc sử dụng mô hình Markov với giả thiết khe thời gian cố đinh. Trong đề tài tiếp theo sẽ nghiên cứu và cải tiến mô hình Markov sử dụng các khe thời gian thay đổi và thay đổi các thông số của mô hình Markov để đạt được hiệu quả cao hơn. TÀI LIỆU THAM KHẢO [1] Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, Aug. 2002. [2] Ephremides, “Energy concerns in wireless networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 48–59, Aug. 2002. [3] W. Stark, H. Wang, A. Worthen, S. Lafortune, and D. Teneketzis, “Lowenergy wireless communication network design,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 60–72, Aug. 2002. [4] R. Min, M. Bhardwaj, S. H. Cho, N. Ickes, E. Shih, A. Sinha, A. Wang, and A. Chandrakasan, “Energy-centric enabling technologies for wireless sensor networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 28– 39, Aug. 2002. [5] J. Goldsmith and S. B. Wicker, “Design challenges for energy constrained ad hoc wireless networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 8–27, Aug. 2002. [6] S. Ci, H. Sharif, and K. Nuli, “Study of an adaptive frame size predictor to enhance energy conservation in wireless sensor networks,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 2, pp. 282– 292, Feb. 2005. [7] J. Wang, H. Zhai, and Y. Fang, “Opportunistic packet scheduling and media access control for wireless LANs and multi-hop ad hoc networks,” in Proc. IEEE Wireless Communications and Networking Conf. (WCNC’04), vol. 3, Mar. 2004, pp. 1234– 1239. [8] D. Hwang, H. Jeon, J. Ha and J. Choi, "Energy efficient transmission strategies for distributed detection in wireless sensor networks," Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), 2014 IEEE Ninth International Conference on, Singapore, 2014, pp. 1-5. [9] J. Pavon and S. Choi, “Link adaptation strategy for IEEE 802.11 WLAN via received signal strength measurement,” in Proc. IEEE Int. Conf. Commun. (ICC’03), vol. 2, May 2003, pp. 1108 – 1113. [10] G. Holland, N. H. Vaidya, and P. Bahl, “A rate-adaptive MAC protocol for multi- hop wireless networks,” in Proc. ACM/IEEE Int.l Conf. on Mobile Computing and Networking (MOBICOM’01), Jul. 2001, pp. 236–251.
11. [11] H. Jeon, J. Choi, H. Lee and J. Ha, "Channel-Aware Energy Efficient Transmission Strategies for Large Wireless Sensor Networks," in IEEE Signal Processing Letters, vol. 17, no. 7, pp. 643-646, July 2010. [12] H. Jeon, J. Choi, H. Lee and J. Ha, "Channel-Aware Energy Efficient Transmission Strategies for Large Wireless Sensor Networks," in IEEE Signal Processing Letters, vol. 17, no. 7, pp. 643-646, July 2010. [13] D. Hwang, H. Jeon, J. Ha and J. Choi, "Energy efficient transmission strategies for distributed detection in wireless sensor networks," Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP) [14] D. M. Pham and S. M. Aziz, "An energy efficient image compression scheme for Wireless Sensor Networks," Intelligent Sensors, Sensor Networks and Information Processing, 2013 IEEE Eighth International Conference on, Melbourne, VIC, 2013, pp. 260-264. [15] D. Luo, D. Zuo and X. Yang, "An Energy-Saving Routing Protocol for Wireless Sensor Networks," 2008 4th International Conference on Wireless Communications, Networking and Mobile Computing, Dalian, 2008, pp. 1-4. Thông tin liên hệ tác giả chính (người chịu trách nhiệm bài viết): Họ tên: Trần Thanh Tôn Đơn vị: Học viên cao học trường ĐHSPKT TPHCM Điện thoại: 01665 227 698 Email: thanhton0206@gmail.com
12. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn B n ti ng Vi t ©, T NG I H C S PH M K THU T TP. H CHÍ MINH và TÁC GI Bản quếy n táệc ph mRƯ ãỜ cĐ bẠ o hỌ b Ưi Lu tẠ xu t Ỹb n vàẬ Lu t S hỒ u trí tu Vi t Nam. NgẢhiêm c m m i hình th c xu t b n, sao ch p, phát tán n i dung khi c a có s ng ý c a tác gi và ả ng ề i h ẩ pđh đưm ợK thuả tộ TP.ở H ậChí Mấinh.ả ậ ở ữ ệ ệ ấ ọ ứ ấ ả ụ ộ hư ự đồ ủ ả Trườ Đạ ọCcÓ Sư BÀI BạÁO KHỹ OA ậH C T ồT, C N CHUNG TAY B O V TÁC QUY N! ĐỂ Ọ Ố Ầ Ả Ệ Ề Th c hi n theo MTCL & KHTHMTCL h c 2017-2018 c a T vi n ng i h c S ph m K thu t Tp. H Chí Minh. ự ệ Năm ọ ủ hư ệ Trườ Đạ ọ ư ạ ỹ ậ ồ