Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet

Trong trường hợp mạng MANET có vùng diện tích rộng và mật độ nút cao, ảnh hưởng của các hiệu ứng vật lý xảy ra trên các lộ trình truyền dữ liệu đến chất lượng tín hiệu truyền dẫn là rất nghiêm trọng, làm suy giảm hiệu năng mạng. Bài báo tập trung nghiên cứu các thuật toán định tuyến dưới điều kiện ràng buộc ảnh hưởng của các hiệu ứng vật lý xảy ra trên đường truyền. Từ đó, chúng tôi cải tiến thuật toán DSR sử dụng kỹ thuật định tuyến xuyên lớp kết hợp với agent tĩnh nhằm giảm xác suất nghẽn mạng, giảm thiểu số gói tin điều khiển. Các hiệu ứng vật lý được xem xét bao gồm nhiễu tích lũy trên đường truyền, suy hao công suất tín hiệu qua môi trường truyền dẫn

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 1

Trang 1

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 2

Trang 2

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 3

Trang 3

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 4

Trang 4

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 5

Trang 5

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 6

Trang 6

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 7

Trang 7

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet trang 8

Trang 8

pdf 8 trang xuanhieu 1720
Bạn đang xem tài liệu "Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet

Một thuật toán định tuyến xuyên lớp đảm bảo QoT trong mạng manet
Với kỹ thuật điều chế DPSK (Differential Phase Shift Keying), nếu 
SNR của kênh truyền là 8dB, giá trị BER tương ứng là 10−3, nhưng nếu SNR tăng lên đến 10dB thì BER giảm xuống 
còn 2×10−5. Tương tự, với kỹ thuật điều chế QPSK (Quadrature Phase Shift Keying), giá trị BER giảm từ 2×10−4 xuống 
còn 4×10−6 khi SNR tăng từ 8dB đến 10dB. 
 Hình 1. Sự thay đổi của BER theo SNR đối với kỹ thuật điều chế DPSK, QPSK và QAM 
 Trong mạng MANET, khi dữ liệu truyền qua nhiều nút trung gian, công suất nhiễu tích lũy dọc theo đường 
truyền tăng dần, làm cho SNR giảm dần theo phương trình (2). Mặt khác, khi SNR càng giảm thì BER càng tăng lên 
như đã phân tích ở hình 1. Vì vậy, để đảm bảo QoT trong mạng MANET, điều kiện ràng buộc về SNR cần phải được 
xem xét trong các thuật toán định tuyến. Để phân tích sự suy giảm SNR khi dữ liệu truyền qua nhiều nút trung gian, 
chúng tôi xét một lộ trình truyền dữ liệu từ nguồn đến đích qua m nút (m-1 bước truyền) với cấu trúc như ở hình 2. Khi 
đó, SNR tại đầu thu của kênh truyền dữ liệu được xác định theo phương trình nghịch đảo sau đây [12]: 
 1 m 1 1
 (2) 
 SNR  SNR
 m i 1 hi
trong đó, SNRm là giá trị SNR tại nút đích (nút m), SNRhi là giá trị SNR của bước truyền thứ i. Để thấy rõ sự thay đổi 
SNR theo tổng số bước truyền mà gói dữ liệu đi qua trong mạng MANET theo phương trình (3), chúng tôi xét trường 
hợp mạng MANET có SNR trung bình trên mỗi bước truyền là 16dB. Từ kết quả tính toán trên hình 3 ta thấy rằng, giá 
trị SNR giảm dần khi dữ liệu truyền qua nhiều bước truyền. Nếu dữ liệu chỉ truyền qua 1 bước truyền (không đi qua 
nút trung gian nào) thì SNR là 16 dB, nhưng nếu truyền qua 2 bước truyền thì SNR giảm xuống còn 12.5dB. Giá trị 
này giảm xuống đến 6.5 dB nếu dữ liệu truyền qua 8 bước truyền. SNR càng giảm thì BER càng tăng như đã phân tích 
ở phần trên. Vì vậy, để đảm bảo chất lượng dịch vụ, điều kiện ràng buộc về SNR trên lộ trình truyền dữ liệu phải được 
xem xét trong thuật toán định tuyến. Trong phần tiếp theo dưới đây, chúng tôi phân tích các thuật toán định truyến có 
xem xét đến vấn đề này. 
482 MỘT THUẬT TOÁN ĐỊNH TUYẾN XUYÊN LỚP ĐẢM BẢO QoT TRONG MẠNG MANET 
 1 2 3 m 
 Hình 2. Mô hình phân tích SNR trên một lộ trình truyền dữ liệu trong mạng MANET 
 Hình 3. Sự thay đổi SNR theo tổng số bước truyền trong mạng MANET 
 III. ĐỊNH TUYẾN XUYÊN LỚP TRONG MẠNG MANET 
 Trong mô hình OSI, nguyên tắc phân lớp rõ ràng về mặt chức năng đã đóng một vai trò quan trọng trong lĩnh vực 
viễn thông/Internet. Đặc trưng của mô hình OSI là mỗi lớp thực hiện một số chức năng riêng biệt, chỉ các lớp cạnh 
nhau mới có thể trao đổi thông tin với nhau. Điều này gặp phải một số nhược điểm trong trường hợp các lớp không lân 
cận nhau muốn có được thông tin của nhau để thực thi các giao thức điều khiển nhằm nâng cao hiệu năng mạng. 
 (a) (b) 
 Hình 4. So sánh các mô hình: (a) OSI và (b) xuyên lớp 
Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam 483 
 Hình 5. Mối quan hệ giữa các lớp trong mô hình phân lớp [11] 
 Mô hình xuyên lớp (Cross-Layer) là mô hình cho phép các lớp không lân cận vẫn có thể trao đổi thông tin cho 
nhau như cho thấy ở hình 4(b). Tùy theo việc trao đổi thông tin giữa các lớp mà cho phép thực hiện một số chức năng 
để nâng cao hiệu năng mạng như minh họa ở hình 5. Trong bài báo này, chúng tôi tập trung vào kỹ thuật định tuyến 
xuyên lớp dựa trên việc trao đổi thông tin trực tiếp giữa lớp mạng và lớp vật lý. 
 IV. THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO QoT SỬ DỤNG TÁC TỬ 
 Để nâng cao chất lượng tín hiệu truyền dẫn trong mạng MANET, chúng tôi đề xuất một thuật toán định tuyến 
được đặt tên là QoT-A-DSR (Quality of Transmission using Agent in DSR). Thuật toán QoT-A-DSR được đề xuất dựa 
trên nguyên lý của thuật toán DSR, sử dụng tác tử (agent) để cập nhật thông tin về chất lượng tín hiệu truyền dẫn (QoT) 
ở lớp vật lý đến lớp mạng để thực hiện quá trình định tuyến. 
A. Cấu trúc nút mạng theo mô hình xuyên lớp sử dụng tác tử trong thuật toán QoT-A-DSR 
 Để có thể sử dụng các thông tin về chất lượng tín hiệu truyền dẫn làm tham số định tuyến, lớp mạng cần phải 
được trao đổi thông tin trực tiếp với lớp vật lý. Điều này chỉ có thể thực hiện thông qua mô hình xuyên lớp như đã phân 
tích ở phần III. Trong mô hình được đề xuất, chức năng trao đổi thông tin xuyên lớp được thực hiện thông qua tác tử 
với cấu trúc như ở hình 6, tác tử được sử dụng trong mô hình này là tác tử tĩnh (static agent). 
 Hình 6. Cấu trúc nút mạng MANET theo mô hình xuyên lớp sử dụng tác tử 
B. Thuật toán QoT-A-DSR 
 Với cấu trúc nút mạng như ở hình 6, thuật toán định tuyến QoT-A-DSR được thực hiện bằng cách tích hợp thêm 
một trường có tên QoT trong gói RREQ, trường QoT chứa các thông tin về chất lượng tín hiệu truyền dẫn được cập 
nhật từ lớp vật lý thông qua tác tử. Nguyên lý hoạt động của thuật toán QoT-A-DSR là khi mỗi nút trung gian nhận 
được gói tin yêu cầu khám phá lộ trình RREQ, tác tử trong nút sẽ tiến hành tính toán giá trị QoT từ nguồn đến nút hiện 
tại theo phương trình 2. Nếu thỏa mãn ngưỡng cho phép thì gói RREQ mới được phát quảng bá đến các nút láng giềng 
của nó. Ngược lại thì gói RREQ sẽ bị hủy bỏ. Thuật toán 1 mô tả chi tiết các bước thực hiện của thuật toán QoT-A-
DSR. 
 Điểm khác nhau cơ bản giữa thuật toán QoT-A-DSR và thuật toán DSR là quy trình xử lý gói tin RREQ của giai 
đoạn khám phá lộ trình. Cụ thể, với thuật toán DSR, khi một nút nhận được gói tin yêu cầu khám phá lộ trình mới 
(RREQ), nút đó sẽ tiến hành kiểm tra xem trước đó đã nhận được gói tin RREQ này chưa. Nếu đã nhận được thì loại bỏ 
gói RREQ và không xử lý gì thêm. Với thuật toán QoT-A-DSR, nếu gói RREQ đã được nhận trước đó thì gói này vẫn 
không bị loại bỏ. Thay vào đó là nút đang xử lý sẽ tính toán giá trị SNR từ nút nguồn đến nút đáng xét theo phương 
trình 2. Giá trị SNR này được tính toán và cập nhật vào gói RREQ nhờ agent tĩnh trong nút như đã mô tả ở hình 6. Nếu 
SNR tính được lớn hớn SNR đang lưu trữ trong router cache của nút thì quá trình xử lý gói RREQ vẫn được tiếp tục. 
Nút đang xét sẽ cập nhật thông tin gói RREQ mới thay cho RREQ đã nhận được trước đó. Quá trình xử lý gói RREQ sẽ 
484 MỘT THUẬT TOÁN ĐỊNH TUYẾN XUYÊN LỚP ĐẢM BẢO QoT TRONG MẠNG MANET 
tiếp tục như trường hợp nút này trước đó chưa nhận được gói RREQ. Một điểm khác biệt nữa giữa thuật toán QoT-A-
DSR và thuật toán DSR là tại mỗi nút trung gian, nếu giá trị SNR tính được nhờ agent tĩnh không đạt ngưỡng cho phép 
thì gói RREQ sẽ bị hủy bỏ, nghĩa là nút hiện tại không tiếp tục phát quảng bá gói RREQ đến các nút láng giềng của nó. 
Điều này sẽ làm giảm số gói RREQ trong giai đoạn khám phá lộ trình. 
 Thuật toán 1: Thuật toán định tuyến xuyên lớp đảm bảo QoT sử dụng tác tử: QoT-A-DSR 
 1: Phân tích yêu cầu khám phá lộ trình mới; 
 2: repeat 
 3: Phát quảng bá gói RREQ đến các nút láng giềng của nó; 
 4: Tại nút nhận gói RREQ: Tính SNR từ nguồn đến nút hiện tại thông qua agent tĩnh 
 (SNRc) theo phương trình 2; 
 5: if (SNRc > SNRth) then 
 6: if (Nút hiện tại là nút đích) then 
 7: if (Trước đó chưa nhận gói RREQ) then 
 8: Cập nhật thông tin định tuyến và giá trị SNRc vào Router cache; 
 9: Tạo gói RREP, gửi về nguồn theo lộ trình ngược lại của lộ trình 
 RREQ đã qua; 
 10: else 
 11: if (SNRc > SNR đang lưu trữ trong Router cache) then 
 12: Cập nhật thông tin định tuyến và giá trị SNRc vào Router 
 cache; 
 13: Tạo gói RREP, gửi về nguồn theo lộ trình ngược lại của 
 lộ trình RREQ đã qua; 
 14: else 
 15: Loại bỏ gói RREQ; 
 16: end if; 
 17: end if; 
 18: else 
 19: if (Trước đó chưa nhận gói RREQ) then 
 20: Cập nhật thông tin định tuyến và giá trị SNRc vào Router cache; 
 21: else 
 22: if (SNRc > SNR đang lưu trữ trong Router cache) then 
 23: Cập nhật thông tin định tuyến và giá trị SNRc vào Router 
 cache; 
 24: else 
 25: Loại bỏ gói RREQ; 
 26: end if; 
 27: end if; 
 28: end if; 
 29: else 
 30: Loại bỏ gói RREQ; 
 31: end if; 
 32: until (Nút nguồn nhận được gói RREP) or (Quá thời hạn cho phép) 
 V. KẾT QUẢ MÔ PHỎNG VÀ THẢO LUẬN 
 Hiệu quả thực thi của thuật toán định tuyến QoT-A-DSR được đánh giá bằng phương pháp mô phỏng, so sánh với 
thuật toán DSR. Các giả thiết mô phỏng được thiết lập như sau: 
 - Vùng diện tích mô phỏng: 1000m × 1000m, vùng phủ sóng của mỗi nút: 250m. 
 - Tổng số nút mạng: sử dụng 9 kịch bản mô phỏng khác nhau với tổng số nút mạng của mỗi kịch bản lần lượt 
 là: 10, 15, 20, 25, 30, 35, 40, 45 và 50 nút. 
 - Kỹ thuật điều chế: DPSK với sóng mang có tần số 2.4GHz. 
 - Tốc độ dữ liệu của mỗi kênh: 11Mbps. 
 - Công suất phát: 15.5dBm, độ nhạy thu của mỗi nút: -75dBm. 
 - Ngưỡng BER cho phép: 10−6, tương đương với SNR yêu cầu của mỗi lộ trình là 11dB. - Kích thước gói dữ 
 liệu trung bình: 500 bytes. 
 - Tốc độ di chuyển của mỗi nút thay đổi từ 0 m/s (tương đương với trường hợp đứng yên) đến 20 m/s, sử dụng 
 kịch bản di chuyển Ramdom WayPoint. 
Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam 485 
 Mô phỏng được triển khai trên phần mềm mô phỏng mạng đang được sử dụng phổ biến, đó là OMNeT++ 
(Objective Modular Network Testbed in C++) [8], giao diện chính của chương trình mô phỏng như ở hình 7. Đây là 
trường hợp tổng số nút mô phỏng là 40. 
 Hình 7. Giao diện chính của chương trình mô phỏng thuật toán định tuyến DSR và QoT-A-DSR 
 Kết quả mô phỏng trên hình 8 là xác suất hủy bỏ gói dữ liệu (PBP: Packet Blocking Probability) của các thuật 
toán QoT-A-DSR và DSR. PBP được xác định theo phương trình: 
 Tổng số gói hủy bỏ do lưu lượng + Tổng số gói hủy bỏ do không thỏa mãn SNR
 PBP ( 3) 
 Tổng số gói phát sinhtrên toàn mạng
 Từ các đồ thị trên hình 8 ta thấy rằng, thuật toán QoT-A-DSR cho giá trị PBP nhỏ hơn nhiều so với thuật toán 
DSR. Ví dụ, khi tải lưu lượng là 2 Mbit/s, BBP của thuật toán DSR là 0.118, trong khi đó, giá trị này của thuật toán 
QoT-A-DSR chỉ là 0.09, giảm 22.9%. Nguyên nhân làm cho thuật toán DSR có giá trị PBP cao là do thành phần bị loại 
bỏ do không đảm bảo QoT, mà cụ thể ở đây là SNR. Với thuật toán QoT-A-DSR, lộ trình truyền dữ liệu được chọn 
luôn có giá trị SNR tốt nhất. Vì vậy, thành phần gói dữ liệu bị hủy bỏ do không thỏa mãn điều kiện ràng buộc SNR 
giảm hẳn, kéo theo là PBP trong toàn mạng giảm. 
 Hình 8. So sánh xác suất gói tin bị hủy bỏ của các thuật toán DSR và QoT-A-DSR 
 486 MỘT THUẬT TOÁN ĐỊNH TUYẾN XUYÊN LỚP ĐẢM BẢO QoT TRONG MẠNG MANET 
 Hình 9. So sánh xác suất gói điều khiển (RREQ) của các thuật toán DSR và QoT-A-DSR 
 Một kết quả đáng chú ý khác là số gói RREQ trung bình trên mỗi lần khám phá lộ trình của thuật toán QoT-A-
DSR và DSR (Hình 9). Ta thấy rằng, với thuật toán QoT-A-DSR, tổng số gói RREQ trung bình cho mỗi lần khám phá 
lộ trình giảm một cách đáng kể, đặc biệt là trong trường hợp tổng số nút mạng lớn. 
 VI. KẾT LUẬN 
 Để nâng cao chất lượng dịch vụ khi truyền dữ liệu qua mạng MANET, việc xem xét các điều kiện ràng buộc về 
 ảnh hưởng của nhiễu truyền dẫn xảy ra trên các lộ trình truyền dữ liệu là điều cần thiết. Bài báo đã đề xuất thuật toán 
 định tuyến QoT-A-DSR có xem xét đến điều kiện ràng buộc ảnh hưởng của nhiễu xảy ra trên đường truyền, cải thiện 
 tham số tỷ lệ tín hiệu trên nhiễu (SNR). Thông qua mô phỏng, tác giả đã chứng minh rằng, thuật toán QoT-A-DSR 
 mang lại hiệu quả tốt hơn thuật toán DSR nếu xét về xác suất nghẽn mạng và tổng số gói điều khiển. Trong hướng 
 nghiên cứu tiếp theo, chúng tôi tiếp tục phân tích các hiệu ứng vật lý khác xảy ra trên các tuyến truyền dẫn trong các 
 mạng tùy biến, đồng thời xem xét thêm điều kiện ràng buộc về ảnh hưởng của SNR trong giai đoạn duy trì thông tin 
 định tuyến của thuật toán DSR. 
 VII. LỜI CẢM ƠN 
 Bài báo này được thực hiện dưới sự hỗ trợ của Đề tài Khoa học công nghệ cấp Bộ Giáo dục và Đào tạo có mã số 
B2016-DHH-21. 
 TÀI LIỆU THAM KHẢO 
 [1] Aradhna Yadav et al., “Cross-Layer Approach For Communication in Manet”, International Journal of Computer Science and 
 Mobile Computing, Vol.4, No.3, 2015, pp. 285-292. 
 [2] Bakhsh, H. and Abdullah, M. “ARPM: Agent-based Routing Protocol For MANET”, Int. J. Internet Protocol Technology, Vol. 
 3, No. 2, 2008, pp.136–146. 
 [3] Elis Kulla et al., “Investigation of AODV Throughput Considering RREQ, RREP and RERR Packets”, 27th International 
 Conference on Advanced Information Networking and Applications, Barceona, Spain, March 2013, pp.169-174. 
 [4] Hong Li, Chu Dan, Wang Min, Li Shurong, “Mobile agent based Congestion Control AODV Routing Protocol”, The 4th 
 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2008, pp.1-4. 
 [5] Fuad Alnajjar, “SNR/RP Aware Routing Model for MANETs”, Journal of Selected Areas in Telecommunications (JSAT), 
 2011, pp. 40-48. 
 [6] Mohamed E., Mohd F. M. F., Nidal K., Che M. N. C. I., “Weighted Signal-to-Noise Ratio Average Routing Metric for 
 Dynamic Sequence Distance Vector Routing Protocol in Mobile Ad-Hoc Networks”, IEEE 8th International Colloquium on 
 Signal Processing and its Applications (CSPA), 2012, pp. 329-334. 
 [7] Supriya Srivastava, A. K. Daniel, “An Efficient Routing Protocol under Noisy Environment for Mobile Ad Hoc Networks 
 using Fuzzy Logic”, International Journal of Advanced Research in Artificial Intelligence, Vol. 2, No. 6, 2013, pp.34-39. 
 [8] András Varga, OMNeT++ Discrete Event Simulation System, Release 4.6, 2015. [Online]. Available:  
 [9] Kaveh P. and Prashant K., Principles Wireless Networks, Prenpice-Hall, Inc., 2002. 
 [10] Shafiullah K., Al-Sakib K. P., and Nabil A. A., Wireless Sensor Networks - Current Status and Future Trends, CRC Press, 
 2012. 
Lê Hữu Bình, Võ Thanh Tú, Nguyễn Văn Tam 487 
[11] Nguyễn Trung Kiên, “Định tuyến xuyên lớp trong mạng Mobile Wireless”, [Online]. Available: 
 tuyen-xuyen-lop-trong-mang-mobile-wireless/. 
[12] Lê Hữu Bình, Võ Thanh Tú, “Đánh giá ảnh hưởng của nhiễu truyền dẫn trong mạng MANET dựa trên giao thức định tuyến 
 theo yêu cầu”, Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin - 
 FAIR’8, Hà Nội, 9 - 10/07/2015, NXB Khoa học tự nhiên và Công nghệ 2015, trang 119-126. 
 A CROSS LAYER ROUTING ALGORITHM GUARANTEED QoT IN MANET 
 Le Huu Binh, Vo Thanh Tu, Nguyen Van Tam 
ABSTRACT— In the case of MANET with the wide area and high node density, the impact of the physical effects that happen on the 
transmission routes to the quality of the transmission signal is very serious, decreasing network performance. In this paper, we 
focused on the studying the routing algorithm under the constraint of the physical effects occurring on the transmission routes. 
Thence, we improved DSR algorithm using cross layer routing techniques combined with static agent to reduce the congestion 
probability of network and minimizing the number of control packets. The physical effects are considered including the cumulative 
noise on the transmission routes, the signal power loss through the transmission medium. 

File đính kèm:

  • pdfmot_thuat_toan_dinh_tuyen_xuyen_lop_dam_bao_qot_trong_mang_m.pdf