Luận văn Nghiên cứu kỹ thuật định tuyến đa đường hiệu quả, tin cậy và tiết kiệm năng lượng trên cơ sở cải tiến giao thức Aomdv

OMDV Ngành: Khoa học máy tính Mã số: 9480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. NGUYỄN VĂN TAM Thái Nguyên - 2020 LỜI CẢM ƠN Sau thời gian học tập và rèn luyện tại Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, bằng sự biết ơn và kính trọng, tôi xin gửi lời cảm ơn chân thành đến Ban Giám hiệu, Phòng Đào tạo và Khoa Công nghệ thông tin thuộc Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên cùng các thầy, cô giáo đã nhiệt tình hướng dẫn, giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Văn Tam, người thầy đã trực tiếp hướng dẫn, giúp đỡ em trong quá trình thực hiện đề tài. Xin chân thành cảm ơn gia đình, bạn bè cùng đồng nghiệp đã tạo điều kiện sát, nghiên cứu để hoàn thành đề tài này. Tuy nhiên điều kiện về năng lực bản thân còn hạn chế, luận văn chắc chắn không tránh khỏi những thiếu sót. Kính mong nhận được sự đóng góp ý kiến của các thầy cô giáo, bạn bè và đồng nghiệp để luận văn của tôi được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày tháng . năm 2019 Học viên Nguyễn Kiên Giang MỤC LỤC DANH MỤC CÁC TỪ VIẾT TẮT ....................................................................... 1 MỞ ĐẦU ................................................................................................................ 3 CHƯƠNG 1. MẠNG AD HOC DI ĐỘNG VÀ ĐỊNH TUYẾN ĐA ĐƯỜNG .... 6 1.1. Tổng quan về mạng ad hoc di động ............................................................ 6 1.1.1. Định nghĩa mạng ad hoc di động ......................................................... 6 1.1.2. Đặc điểm của mạng ad hoc di động ..................................................... 7 1.1.3. Ứng dụng của mạng MANET .............................................................. 9 1.1.3.1. Ứng dụng trong quân đội .................................................................. 9 1.3.1.2. Các ứng dụng trong cuộc sống ........................................................ 10 1.3.1.3. Mạng cảm biến ................................................................................ 12 1.3.1.4. Mạng Rooftop ................................................................................. 12 1.3.1.5. Mở rộng phạm vi của điểm truy cập ............................................... 13 1.2. Giao thức định tuyến đa đường AOMDV ................................................. 14 1.2.1. Tổng quan về giao thức AOMDV...................................................... 14 1.2.2. Vấn đề chống định tuyến lặp ............................................................. 15 1.2.3. Các đường tách biệt ............................................................................ 18 1.2.4. Bảng định tuyến ................................................................................. 24 1.2.5. Thuật toán cập nhật đường ................................................................. 25 1.2.6. Tiến trình khám phá đường ................................................................ 27 1.2.7. Cơ chế bảo trì đường .......................................................................... 30 1.2.8. Cơ chế chuyển tiếp dữ liệu ................................................................. 31 1.3. Một số nghiên cứu cải tiến giao thức AOMDV ........................................ 31 1.5. Tổng kết chương 1 .................................................................................... 34 CHƯƠNG 2. KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƯỜNG HIỆU QUẢ, TIN CẬY VÀ TIẾT KIỆM NĂNG LƯỢNG CỦA GIAO THỨC ĐỊNH TUYẾN E2E- LREEMR .............................................................................................................. 36 2.1. Xây dựng độ đo định tuyến ....................................................................... 36 2.2. Cơ chế hoạt động ....................................................................................... 38 2.3. Xác định năng lượng còn lại và năng lượng còn lại tối thiểu ................... 39 2.4. Xác định năng lượng truyền dự kiến ......................................................... 41 2.5. Xác định tổng năng lượng truyền dự kiến ................................................ 42 2.6. Xác định số lần truyền dự kiến ................................................................. 43 2.7. Xác định tổng số lần truyền dự kiến ......................................................... 45 2.8. Chọn đường dựa trên CETX và CETE ..................................................... 45 2.9. Tổng kết Chương 2 ................................................................................... 48 CHƯƠNG 3. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC ........ 50 3.1. Thiết lập môi trường mô phỏng ................................................................ 50 3.2. Độ đo hiệu năng ........................................................................................ 51 3.3. Kết quả mô phỏng và đánh giá .................................................................. 53 3.3.1. Tỷ lệ mất gói ...................................................................................... 53 3.3.2. Chi phí định tuyến chuẩn hoá ............................................................ 54 3.3.3. Tổng năng lượng tiêu thụ ................................................................... 56 3.3.4. Thông lượng ....................................................................................... 57 3.3.5. Tỷ lệ truyền thành công ..................................................................... 58 3.3.6. Chi phí định tuyến .............................................................................. 59 3.3.7. Trễ đầu cuối trung bình ...................................................................... 60 3.4. Tổng kết Chương 3 ................................................................................... 62 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................................... 63 TÀI LIỆU THAM KHẢO .................................................................................... 65 1 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Nghĩa tiếng Việt ADSL Asymmetric Digital Đường thuê bao số bất đối Subscriber Line xứng AODV Ad hoc On demand Giao thức định tuyến theo yêu Distance Vector cầu dạng vector khoảng cách dành cho mạng ad hoc AOMDV Ad hoc On demand Giao thức định tuyến AODV đa Multipath Distance Vector đường CETE Cumulative Expected Tổng năng lượng truyền dự Transmission Energy kiến của đường CETX Cumulative Expected Tổng số lần truyền dự kiến của Transmission Count đường DA Destination Address Địa chỉ đích DoS Denial-of-Service Tấn công từ chối dịch vụ DSR Dynamic Source Routing Giao thức định tuyến nguồn động E2E- End-to-End Link Reliable Giao thức định tuyến đa đường LREEMR Energy Efficient Multipath có liên kết đầu cuối tin cậy và Routing tiết kiệm năng lượng ETE Expected Transmission Năng lượng truyền dự kiến Energy ETX Expected Transmission Số lần truyền dự kiến Count ISP Internet Serive Provider Nhà cung cấp dịch vụ Internet LET Link Expiration Time Thời gian hết hạn liên kết LPU Local Path Update Cập nhật đường nội bộ 2 LR-EE- Link Reliable Energy Giao thức định tuyến AOMDV AOMDV Efficient AOMDV cải tiến độ tin cậy liên kết và năng lượng sử dụng MANET Mobile Ad hoc Network Mạng ad hoc di động MDSDV Modified Destination- Giao thức định tuyến DSDV cải Sequenced Distance- tiến Vector MP-DSR Multipath Dynamic Giao thức định tuyến DSR đa Source Routing đường MP-OLSR Multipath Optimized Link Giao thức định tuyến OLSR đa State Routing Protocol đường MRE Minimal Residual Energy Năng lượng còn lại tối thiểu NS-2 Network Simulator Phần mềm mô phỏng mạng NS version 2 phiên bản 2 OLSR Optimized Link State Giao thức định tuyến tối ưu Routing Protocol trạng thái đường liên kết OMMRE- Optimized Minimal Giao thức định tuyến AOMDV AOMDV Maximal nodal Residual tối ưu năng lượng nút mạng Energy AOMDV QoS Quality of Service Chất lượng dịch vụ RREP Route Reply Gói tin trả lời đường RREQ Route Request Gói tin yêu cầu tìm đường RRER Route Error Gói tin báo lỗi đường RSSI Received Signal Strength Chỉ số độ mạnh tín hiệu nhận Indicators được SA Source Addrress Địa chỉ nguồn ZRP Zone Routing Protocol Giao thức định tuyến vùng 3 MỞ ĐẦU Mạng Ad hoc di động (MANET) là một nhóm thiết bị tự trị di động cung cấp khả năng truyền thông đa chặng qua việc sử dụng các liên kết không dây và hình thành cấu trúc liên kết động. Các mạng như vậy không có cơ sở hạ tầng vật lý đầy đủ như bộ định tuyến, máy chủ, điểm truy cập, cáp truyền dẫn hoặc cơ chế quản trị tập trung. Mỗi nút di động trong MANET hoạt động với cả hai vai trò là định tuyến và nút người dùng đầu cuối. Điều này khiến mạng MANET được kỳ vọng sẽ có những ứng dụng rộng rãi trong các khu vực chiến tranh, khắc phục thảm họa, hàng không và thông tin liên lạc hàng hải, công nghiệp, gia đình... Đối với mạng MANET, có nhiều vấn đề kỹ thuật cần phải được giải quyết như: (i) các tính chất không dự đoán được của liên kết dẫn tới xung đột dữ liệu và tín hiệu truyền, (ii) sự di động của các nút mạng dẫn đến cấu trúc mạng động, (iii) thời lượng pin hạn chế của các thiết bị di động, (iv) vấn đề trạm ẩn và trạm rõ xảy ra khi các tín hiệu của hai nút xung đột với nhau, (v) khó bảo trì đường do sự thay đổi của môi trường truyền và (vi) thiếu cơ chế bảo mật tạo cơ hội cho các tấn công như nghe lén thụ động, can thiệp chủ động và rò rỉ thông tin bí mật, giả mạo dữ liệu, phát lại thông điệp và tấn công từ chối dịch vụ (DoS). Định tuyến là một trong những vấn đề quan trọng nhất cần được xem xét trong số nhiều vấn đề cần giải quyết trong MANET. Các giao thức định tuyến đơn đường thường tìm thấy một đường tối ưu giữa một cặp nút nguồn và đích. Do đó, mỗi khi một con đường bị phá vỡ, một tiến trình khám phá đường mới lại được kích hoạt dẫn đến chi phí và độ trễ cao. Tuy nhiên, các giao thức định tuyến đa đường thiết lập một kênh truyền thông từ nguồn đến đích bằng cách có các đường 4 dự phòng. Khi đường chính bị lỗi trong quá trình truyền thông đầu cuối, các đường dự phòng được sử dụng để truyền tải dữ liệu một cách hiệu quả đến đích. Đã có nhiều giao thức định tuyến đa đường được đề xuất. Đối với các giao thức định tuyến đa đường sử dụng cơ chế tìm đường trước như giao thức MDSDV và giao thức MP-OLSR, việc cập nhật các bảng định tuyến thường xuyên dẫn đến việc tiêu thụ một lượng lớn bộ nhớ, băng thông và năng lượng. Để giải quyết vấn đề này, các giao thức định tuyến đa đường tìm đường theo yêu cầu đã được đề xuất. Những giao thức định tuyến đa đường tiêu biểu trong nhóm này là giao thức MP-DSR và giao thức AOMDV. Cũng đã có nhiều nghiên cứu đề xuất cải tiến giao thức AOMDV thành các giao thức mới để đạt được hiệu năng tốt hơn. Đó là giao thức MMNE-AOMDV và OMMNE-AOMDV với khả năng tiết kiệm năng lượng cao hơn; giao thức LL-EE-AOMDV với khả năng định tuyến đa đường hiệu quả qua các liên kết tin cậy và tiết kiệm năng lượng. Đây là giao thức có hiệu năng cao hơn giao thức OMMNE-AOMDV, MMNE-AOMDV và AOMDV. Do số lượng đường được giao thức LR-EE-AOMDV tạo ra rất hạn chế bởi cơ chế lựa chọn đường giữa bất kỳ cặp nguồn-đích nào bằng cách sử dụng kết hợp 3 độ đo đầu cuối nên độ trễ đầu cuối của giao thức này là rất cao khi số lượng kết nối hoặc lưu lượng dữ liệu mạng tăng lên. Mục tiêu chính đề tài này là nghiên cứu sâu về giao thức định tuyến đa đường mới là E2E-LREEMR trên cơ sở cải tiến giao thức định tuyến đa đường AOMDV. Giao thức này có khả năng tìm nhiều đường không lặp qua các liên kết tin cậy với và sử dụng năng lượng một cách hiệu quả theo điều kiện tài nguyên có sẵn để đáp ứng các yêu cầu Chất lượng dịch vụ (QoS) khác nhau của các ứng dụng. Mức độ cải tiến về hiệu năng của giao thức E2E-LREEMR so với giao thức AOMDV sẽ 5 được chứng minh qua các phân tích đánh giá các kết quả mô phỏng hai giao thức trên phần mềm mô phỏng NS-2. Luận văn có bố cục như sau: Sau phần mở đầu là nội dung giới thiệu tổng quan về mạng không dây di động ad hoc và định tuyến đa đường được trình bày trong Chương 1. Chi tiết của kỹ thuật định tuyến đa đường, hiệu quả, tin cậy và tiết kiệm năng lượng trong giao thức định tuyến E2E-LREEMR trên cơ sở cải tiến giao thức định tuyến AOMDV được trình bày trong Chương 2. Các kết quả mô phỏng, so sánh đánh giá hiệu năng của giao thức định tuyến E2E-LREEMR và giao thức định tuyến AOMDV được trình bày trong Chương 3. Cuối cùng là phần kết luận đưa ra những nội dung tổng kết và hướng phát triển của luận văn. 6 CHƯƠNG 1. MẠNG AD HOC DI ĐỘNG VÀ ĐỊNH TUYẾN ĐA ĐƯỜNG 1.1. Tổng quan về mạng ad hoc di động 1.1.1. Định nghĩa mạng ad hoc di động Mạng ad hoc di động (MANET) [3] là một mạng được hình thành bởi một tập các nút (máy/thiết bị) không dây, di động mà không hề có bất cứ sự trợ giúp nào của một trạm quản lý tập trung, một cơ sở hạ tầng truyền thông có trước hoặc sự can thiệp của người dùng. Việc truyền thông giữa các nút được thực hiện nếu như hai nút là đủ gần nhau để trao đổi các gói tin. Hình 1.1. Ví dụ về một mạng MANET Có thể hình dung mạng MANET như một đồ thị, trong đó các nút mạng được biểu diễn bởi các đỉnh của đồ thị. Nếu hai nút có thể truyền thông trực tiếp với nhau, liên kết đó được biểu diễn bởi đường nối giữa hai nút. Đồ thị biểu diễn này là một đồ thị tùy ý, có thể thay đổi hình dạng tại bất cứ thời điểm nào. Mạng MANET có thể là một mạng độc lập, hoặc cũng có thể được kết nối với một mạng khác lớn hơn, ví dụ mạng Internet. 7 Trong Hình 1.1 là một ví dụ về một mạng MANET gồm 7 nút. Phạm vi truyền thông của mỗi nút được biểu diễn bằng một hình tròn. Các nút nằm trong phạm vi truyền thông của nhau có thể truyền thông trực tiếp được với nhau. Kết nối giữa các nút mạng được đặc trưng bởi khoảng cách giữa các nút và tính sẵn sàng hợp tác để tạo thành mạng mặc dù là tạm thời. Các tính chất đặc trưng của kết nối trong mạng MANET bao gồm: (1) Khoảng cách giữa các nút: Khoảng cách giữa các nút hoặc trạng thái ở gần nhau của chúng định nghĩa ranh giới mạng. Chỉ cần hai hoặc nhiều nút chuyển động trong một bán kính nhất định là tạo thành một mạng ad-hoc. Chính sự chuyển động làm cho khoảng cách giữa các nút thay đổi gây ra bản chất đặc biệt (ad-hoc) của mạng. (2) Tính sẵn sàng hợp tác: (1) chỉ là điều kiện cần, chưa phải là điều kiện đủ để thành lập mạng ad-hoc. Các nút ở trong khoảng cách đủ gần phải sẵn sàng hợp tác để tạo thành mạng. Nói cách khác, tự bản thân nút quyết định “online” hay “offline”. (3) Mạng ngang hàng tạm thời: Tại bất cứ một thời điểm nào, mạng ad-hoc được xác định bởi các nút đang “online” và ở trong một khoảng cách nhất định. Một nút luôn có xu hướng tham gia hay biến mất khỏi mạng. Do đó, mạng được coi là tạm thời. Hơn nữa, do không có một cơ sở hạ tầng mạng cho trước, các nút trong mạng phải truyền thông theo kiểu ngang hàng (peer-to-peer). 1.1.2. Đặc điểm của mạng ad hoc di động Do ad hoc là một mạng không dây hoạt động không cần sự hỗ trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động vừa 8 đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng ad hoc di động còn có một số đặc điểm nổi bật sau [2]:  Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng có thể là một bộ cảm biến, một điện thoại thông minh hoặc một máy tính xách tay. Thông thường các thiết bị này có tài nguyên hạn chế so với các máy tính trong mạng có dây và không dây truyền thống về tốc độ xử lý, dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút.  Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông nhỏ hơn so với các liên kết có dây. Ngoài ra, do ảnh hưởng của cơ chế đa truy cập, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, băng thông thực của các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền tối đa theo lý thuyết của môi trường truyền không dây.  Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở những thời điểm không xác định trước. Trong khi thay đổi, cấu trúc của mạng có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một chiều.  Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với mạng có dây. Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật trong mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ triển khai trong mạng ad ho di động hơn là trong mạng có dây truyền thống. Có thể thấy những đặc điểm này là các yếu tố ảnh hưởng rất nhiều đến hiệu năng của mạng ad hoc di động. Để có thể triển khai được mạng ad hoc di động trong thực tế, các thiết kế mạng phải giải quyết được những thách thức sinh ra do 9 những đặc điểm đã nêu trên của mạng. Những thách thức này gồm các vấn đề kỹ thuật như khả năng truyền dữ liệu và định tuyến hiệu quả khi kích thước mạng thay đổi; đảm bảo chất lượng dịch vụ (QoS) cho các chương trình ứng dụng; cơ chế chuyển đổi một số dịch vụ từ mô hình client-server; tiết kiệm năng lượng pin để kéo dài thời gian hoạt động của các nút mạng riêng lẻ và của toàn mạng; đảm bảo an ninh mạng; khả năng hợp tác giữa các nút mạng và khả năng tự tổ chức của mạng; 1.1.3. Ứng dụng của mạng MANET Các công nghệ của mạng không dây kiểu không cấu trúc đem lại rất nhiều lợi ích so với các mạng truyền thống (cả không dây và có dây) trong những ngữ cảnh khó có thể triển khai được một cơ sở hạ tầng mạng cố định hoặc việc triển khai là không khả thi do những lý do về mặt thực hành (địa hình,) hoặc do những lý do về kinh tế (chi phí cáp trong một không gian lớn, chi phí thiết lập nhiều điểm truy cập). Phần dưới đây sẽ giới thiệu các ứng dụng của mạng MANET. 1.1.3.1. Ứng dụng trong quân đội Những thành tựu mới của công nghệ thông tin thường được áp dụng trong quân sự đầu tiên, và mạng không dây kiểu không cấu trúc cũng không phải là một ngoại lệ. Nhiều năm nay, quân đội đã sử dụng các mạng “packet radios” – một nguyên mẫu đầu tiên của mạng chuyển mạch gói không dây ngày nay. Giải pháp mạng MANET cho quân đội có những đặc điểm khác so với mạng MANET thuần túy [1] Mạng MANET thuần túy thường tuân theo một mô hình điểm ngẫu nhiên, các nút tự do di chuyển theo bất cứ hướng nào, với bất cứ tốc độ nào. Trong mô 10 hình mạng MANET cho quân đội, các nút phân nhóm theo bản chất tự nhiên của chúng khi chúng cùng thực hiện một nhiệm vụ cụ thể. Xu hướng di động ở đây là theo nhóm. Hình 1.2 minh hoạ sự khác nhau về mô hình di động của mạng MANET thuần tuý và mạng MANET trong quân đội. Mạng MANET thuần túy Mạng MANET quân đội Hình 1.2. Mô hình di động mạng MANET thuần túy và mạng MANET quân đội Do đó, nếu đưa ra được một mô hình chuyển động theo nhóm, các vấn đề của mạng MANET sẽ trở nên cụ thể hơn (ví dụ: định tuyến, sử dụng các ứng dụng thời gian thực như tiếng nói, video,), cho phép phát triển một giải pháp tối ưu. 1.3.1.2. Các ứng dụng trong cuộc sống Mạng MANET là rất lý tưởng trong các trường hợp không có sẵn một cơ sở hạ tầng thông tin, tuy nhiên lại cần phải thành lập một mạng tạm thời nhằm trao đổi thông tin và hợp tác cùng làm việc. Tại các vùng bị thiên tai, thảm họa, khó có thể có được một cơ sở hạ tầng về thông tin vững chắc. Hệ thống có trước đó rất có thể bị hỏng hoặc bị phá hủy hoàn toàn. 11 Tại vùng có thảm họa, tất cả các phương tiện và hệ thống truyền thông đều bị phá hủy hoàn toàn. Mỗi chiếc xe của cảnh sát, cứu hỏa, cứu thương, đều được trang bị như một thiết bị đầu cuối di động – là một phần của mạng ad-hoc. Mỗi nhân viên cũng mang theo một thiết bị đầu cuối di động. Các thiết bị đầu cuối này đều liên kết với nhau, hình thành nên một mạng tạm thời nhằm trao đổi thông tin. Cấu hình mạng thay đổi theo những thời điểm khác nhau. Ngoài ra, các thiết bị đầu cuối di động không chỉ cung cấp chức năng gửi và nhận thông tin mà còn có thể chuyển tiếp thông tin – đóng vai trò như router trên Internet. Đối với ứng dụng trong hội thảo, khác với cách làm truyền thống khi những người tham gia hội thảo muốn chia sẻ tài liệu cho nhau là gửi file đính kèm qua email hoặc sao chép qua các thiết bị lưu trữ thứ cấp có khả năng di động, tất cả những người tham dự hội thảo đều có thể sử dụng thiết bị di động để tạo thành một mạng ad-hoc trong suốt thời gian đó. Các thiết bị có thể truyền thông với nhau, truyền/nhận các tài liệu được sử dụng trong hội thảo. Khi hội thảo kết thúc, các thiết bị được tắt nguồn, mạng tự bị hủy bỏ. Mạng MANET cũng có thể ứng dụng trong cuộc sống. Chẳng hạn như mạng động được hình thành từ hai thiết bị cầm tay thông minh của các em học sinh để chơi game. Môi trường mạng ở đây là một mạng không dây kiểu không cấu trúc thuần túy, tức là không có cơ sở hạ tầng về cáp, các thiết bị đầu cuối tự cấu hình để thành lập mạng, mà không có sự quản lý tập trung. Mạng này có thể tự chia nhỏ thành các mạng con: một mạng riêng giữa em học sinh và bạn của em, một mạng “chung” được khởi tạo bởi người muốn chia sẻ các chương trình trò chơi điện tử trên máy của anh ta. Hai mạng này được trộn lẫn vào nhau một cách linh động. 12 1.3.1.3. Mạng cảm biến Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng lượng, có khả năng truyền thông không dây và xử lý cục bộ. Mạng cảm biến là mạng gồm các nút cảm biến (sensor) – các nút này hợp tác với nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường (không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám trong quân đội,... Trước đây mạng cảm biến thường bao gồm một lượng nhỏ các nút cảm biến được kết nối bằng cáp tới một trạm xử lý tập trung. Ngày nay, các nút mạng cảm biến thường là không dây, phân tán để vượt qua các trở ngại vật lý của môi trường, tiết kiệm năng lượng và do trong nhiều trường hợp không thể có được một hạ tầng có sẵn về năng lượng và truyền thông. Công nghệ mạng không dây kiểu không cấu trúc thường được áp dụng để triển khai mạng cảm biến do:  Các nút cảm biến được phân tán trong vùng không có sẵn cơ sở hạ tầng về truyền thông và năng lượng. Các nút phải tự hình thành kết nối.  Các nút phải tự tự cấu hình, tự hoạt động trong bất cứ trường hợp nào  Cấu hình mạng luôn có thể thay đổi (các nút cảm biến bị hỏng, các nút mới được thêm vào,), mạng cảm biến phải tự thích nghi với những thay đổi này. 1.3.1.4. Mạng Rooftop Là một công nghệ đang bùng nổ để cung cấp truy cập mạng băng thông rộng tới các gia đình, một cách để thay thế ADSL (Asymmetric Digital Subscriber Line) 13 và các công nghệ tương tự khác. Mạng rooftop sử dụng công nghệ mạng ad-hoc để mở rộng phạm vi của một số điểm truy cập – các điểm này được nối với nhà cung cấp dịch vụ Internet (ISP). Mỗi người truy cập được trang bị một router ad- hoc cho phép chuyển tiếp lưu lượng thay mặt những người truy cập khác. Từ khía cạnh ad-hoc, những mạng MANET như vậy là tương đối tĩnh – cấu hình của mạng hiếm khi thay đổi. Hình 1.3. Một ví dụ về mạng Rooftop 1.3.1.5. Mở rộng phạm vi của điểm truy cập Trong các mạng không dây được sử dụng rộng rãi ngày nay, các nút mạng di động được kết nối với các điểm truy cập theo cấu hình hình sao. Để được kết nối vào mạng, người sử dụng phải ở trong phạm vi truy cập của mạng. Do phạm vi truy cập này là giới hạn và cơ sở hạ tầng một chặng (one-hop) của cấu hình này, các điểm truy cập phải được trải rộng trong toàn bộ vùng, bao phủ khắp những nơi muốn kết nối với nhau. 14 Sử dụng mạng không dây kiểu không cấu trúc, nhu cầu cần các điểm truy cập sẽ giảm – người sử dụng bên ngoài phạm vi truy cập sẽ vẫn có thể được “tiếp sóng” thông qua một hoặc nhiều nút trung gian để truy cập được vào mạng. 1.2. Giao thức định tuyến đa đường AOMDV 1.2.1. Tổng quan về giao thức AOMDV Giao thức AOMDV [8] là giao thức định tuyến đa đường theo yêu cầu dạng vectơ khoảng cách được thiết kế dành cho mạng MANET. Nó được phát triển từ giao thức AODV trên cơ sở chia sẻ một số đặc điểm với giao thức AODV. Nó dựa trên khái niệm vectơ khoảng cách và sử dụng phương pháp định tuyến từng chặng. Hơn nữa, giao thức AOMDV cũng tìm thấy các đường theo yêu cầu bằng cách sử dụng tiến trình khám phá đường. Sự khác biệt chính giữa hai giao thức này nằm ở số lượng đường tìm được sau mỗi tiến trình khám phá tuyến. Trong giao thức AOMDV, việc truyền gói RREQ từ nguồn tới đích sẽ thiết lập nhiều đường dẫn ngược ở cả các nút trung gian cũng như nút đích. Nhiều gói RREP đi qua các đường nghịch hướng về nút nguồn để tạo thành nhiều đường thuận đến đích tại các nút nguồn và nút trung gian. Giao thức AOMDV cũng cung cấp cho các nút trung gian các đường dự phòng nhằm làm giảm tần suất khám phá đường. Vấn đề trọng tâm của giao thức AOMDV là vấn đề đảm bảo phát hiện được nhiều đường không lặp và phân tách trong tiến trình tìm đường hiệu quả bằng cách sử dụng tiến trình khám phá đường dựa vào kỹ thuật “làm ngập tràn” (flooding). Các quy tắc cập nhật đường của giao thức AOMDV được áp dụng cục bộ tại mỗi nút đóng vai trò chính trong việc duy trì các đường không lặp và phân tách. Các nội dung được trình bày trong chương này là các ý tưởng chính để đạt được hai thuộc tính này. Các phần tiếp sẽ trình bày cách đưa những ý tưởng đó vào giao 15 thức AOMDV bao gồm mô tả chi tiết các quy tắc cập nhật đường tại mỗi nút và tiến trình khám phá đa đường. Đề xuất thiết kế giao thức AOMDV tái sử dụng nhiều nhất có thể những thông tin định tuyến đã có sẵn trong giao thức AODV. Do đó, nó hạn chế chi phí phát sinh trong việc khám phá nhiều đường. Đặc biệt, nó không sử dụng thêm bất kỳ gói điều khiển đặc biệt nào. Trên thực tế, các gói RREP và RERR bổ sung để phát hiện và bảo trì đa đường cùng với một vài trường bổ sung trong các gói điều khiển định tuyến (RREQ, RREP và RERR) là chi phí bổ sung duy nhất trong giao thức AOMDV so với giao thức AODV. 1.2.2. Vấn đề chống định tuyến lặp Các quy tắc cập nhật tuyến của giao thức AODV giới hạn một nút chỉ tìm được tối đa một đường cho mỗi đích. Do đó, cần thiết phải sửa đổi các quy tắc cập nhật đường này để tại mỗi nút có nhiều hơn một đường cho mỗi đích. Tuy nhiên, những sửa đổi này cần được thực hiện để đảm bảo vấn đề tránh định tuyến lặp. Có hai vấn đề phát sinh khi tính toán nhiều đường dẫn không lặp tại một nút cho một đích. Một là, mỗi nút sẽ chọn đường nào trong nhiều đường để cung cấp hoặc quảng bá cho các nút khác? Do mỗi tuyến đường có thể có số chặng khác nhau nên việc lựa chọn một đường bất kỳ có thể tạo thành các đường lặp vòng. Hai là, một nút khi nhận được quảng bá đường có chấp nhận đường nhận được hay không? Việc chấp nhận tất cả các con đường có thể gây ra hiện tượng định tuyến lặp. Hình 1.4 minh họa vấn đề đường lặp vòng bằng các ví dụ đơn giản. Trong Hình 1.4(a), nút D là đích và nút I có hai đường đến D - một đường 5 chặng qua nút M (I –M –N –O–P –D) và một đường một chặng trực tiếp (I - D). Giả sử tuyến đường (I –M –N –O–P –D) được quảng bá đến nút J và tiếp theo tuyến đường (I – 16 D) được quảng bá đến nút K. Sau đó, cả J và K đều có đường đến nút D qua nút I, nhưng mỗi tuyến đường đều có chặng khác nhau. Nếu sau đó nút I nhận được một đường 4 chặng đến đích D từ nút L (L–K–I–D), nút I sẽ không thể xác định được L là nút trước hay nút sau nó trên con đường tới đích D vì chỉ có thông tin số chặng được đưa vào quảng bá đường. Vì vậy, tại nút I sẽ hình thành một tuyến đường tới nút đích D thông qua nút L làm dẫn đến một vòng lặp. Tình huống như vậy xảy ra do một nút (ở đây là nút I) quảng bá một đường ngắn hơn (I - D) trong khi nó đã có một đường dự phòng dài hơn (I –M –N –O–P –D). Hình 1.4. Ví dụ về các trường hợp có thể xảy ra định tuyến lặp Hình 1.4(b) cho thấy một tình huống tiềm năng khác xảy ra lặp vòng. Trong đó nút D là đích. Nút J có đường dẫn 3 chặng đến nút D thông qua nút (J–K–I–D). Nút L cũng có một đường 3 chặng đến nút D thông qua nút M (L - M - N - D). Giả sử nút I nhận được một đường dẫn 4 chặng đến nút D từ nút L. Trong trường hợp này, nút I không thể xác định được liệu nút L có phải là nút đứng trước hay không bởi vì nút J cũng có thể cung cấp một con đường 4 chặng tới nút D. Do đó, việc một nút chấp nhận một đường dài hơn sau khi nó đã quảng bá một đường ngắn hơn tới các nút láng giềng cũng có thể gây ra định tuyến lặp. 17 Tập các điều kiện chống định tuyến lặp đã được xây dựng cho giao thức AODV được phát biểu như sau: (i) Quy tắc số thứ tự: Chỉ duy trì các tuyến đường cho số thứ tự đích có giá trị cao nhất. Tại mỗi nút, nhiều tuyến đường có cùng số thứ tự đích được duy trì. Với quy tắc này, tính chất không lặp vòng của các tuyến đường có thể đạt được tương tự như giao thức AODV. Khi một nút nhận được quảng bá đường chứa số thứ tự đích cao hơn, tất cả các đường có số thứ tự cũ hơn tới đích tương ứng sẽ bị loại bỏ. Tuy nhiên, các nút khác nhau (trên cùng một tuyến đường) có thể có các số thứ tự khác nhau cho cùng một đích. (ii) Đối với cùng một số thứ tự đích, (a) Quy tắc quảng bá đường: Không quảng bá đường ngắn hơn đường đã được quảng bá trước đó. (b) Quy tắc nhận đường: Không nhận đường dài hơn đường đã được quảng bá trước ...g quá trình khám phá đường và sau đó các gói HELLO được sử dụng để xác định RSSI trong quá trình lựa chọn và bảo trì đường. Trong giao thức E2E-LREEMR, độ ổn định của liên kết giữa các nút trong quá trình khám phá đường được xác định thông qua việc tính giá trị của ETX và CETX theo các gói RREQ hoặc RREP. Trong giao thức E2E-LREEMR, ETX của một liên kết giữa các nút theo đường thuận và đường nghịch được tính tương ứng bằng cách sử dụng gói RREP và RREQ. Lượng năng lượng mà một nút cần để gửi một gói dữ liệu đến một nút khác qua một liên kết được ước lượng bằng một độ đô định tuyến theo nút gọi là “năng lượng truyền dự kiến (ETE)”. Tổng giá trị ETE của tất cả các nút thành phần của đường được gọi là “tổng năng lượng truyền dự kiến (CETE)” hay “ETE của đường” hoặc P-NEE. Giá trị nhỏ nhất của năng lượng còn lại của các nút thành phần của một đường được gọi là “năng lượng còn lại tối thiểu (MRE)”. Giá trị này được sử dụng làm ngưỡng cho CETE trong quá trình chọn đường. Đã có nhiều nghiên cứu sử dụng độ đo năng lượng còn lại tối thiểu và số chặng làm độ đo định tuyến để chọn đường trong các giao thức định tuyến. Lỗi tại nút sẽ xảy ra khi năng lượng còn lại tối thiểu của các nút trên đường không đáp ứng đủ cho năng lượng cần thiết để truyền dữ liệu. Mặc định, tất cả các giao thức định tuyến sử dụng “thời gian hết hạn liên kết (LET)” để đo độ ổn định của liên kết. Một liên kết giữa hai nút không thể truyền dữ liệu khi nó còn sống (LET của liên kết đó chưa hết hạn) nhưng nút nhận không nằm trong phạm vi truyền của nút gửi. Ngoài cơ chế LET, giao thức E2E-LREEMR thực hiện việc ước lượng giá trị động CETX để đảm bảo độ tin cậy của liên kết và ước lượng giá trị CETE nhằm đảm bảo tìm được các con đường có hiệu quả về năng lượng qua các liên kết tin 38 cậy để truyền dữ liệu. Giao thức E2E-LREEMR sử dụng độ đo định tuyến kết hợp giữa chất lượng liên kết thuộc đường P-LQE và năng lượng nút thuộc đường P- NEE để chọn nhiều đường có hiệu quả về năng lượng qua các liên kết tin cậy để truyền dữ liệu. Giao thức AOMDV sử dụng độ đo định tuyến truyền thống là số chặng để tìm nhiều đường và chọn đường có một số chặng nhỏ nhất trong đó để truyền dữ liệu. Do đó, quá trình truyền dữ liệu của giao thức AOMDV sẽ bị mất dữ liệu nếu một liên kết bất kỳ giữa các nút của đường đó đang sử dụng bị lỗi hoặc năng lượng của một nút bất kỳ thuộc đường hiện tại không đáp ứng yêu cầu truyền dữ liệu. Để giải quyết vấn đề này, giao thức định tuyến E2E-LREEMR đã được đề xuất trên cơ sở cải tiến giao thức định tuyến AOMDV qua việc sử dụng cả CETX và CETE làm độ đo định tuyến. 2.2. Cơ chế hoạt động Giao thức định tuyến E2E-LREEMR là một phiên bản cải tiến của giao thức định tuyến đa đường AOMDV. Nó sử dụng hai độ đo định tuyến là chất lượng liên kết thuộc đường P-LQE (còn gọi là CETX) và năng lượng nút thuộc đường P-NEE (còn gọi là CETE) để tìm nhiều nhiều con đường có hiệu quả năng lượng qua các liên kết tin cậy. Giao thức này giảm được chi phí định tuyến, tỷ lệ mất gói, chi phí định tuyến chuẩn hóa, độ trễ trung bình đầu cuối và mức tiêu thụ năng lượng. Đồng thời, nó cũng cải thiện tỷ lệ phân phối dữ liệu và thông lượng. Giao thức E2E-LREEMR bao gồm 6 thủ tục chính là: 1. Xác định năng lượng còn lại và năng lượng còn lại tối thiểu (RE & MRE) 2. Xác định năng lượng truyền dự kiến (ETE) 3. Xác định tổng năng lượng truyền dự kiến (CETE) 4. Xác định số lần truyền dự kiến (ETX) 39 5. Xác định tổng số lần truyền dự kiến (CETX) 6. Chọn đường dựa trên CETX và CETE Các thủ tục này được triển khai thông qua việc điều chỉnh cấu trúc một số gói tin và bảng định tuyến của giao thức định tuyến cũng như quy tắc cập nhật đường của thuật toán định tuyến được đưa ra trong Thuật toán 2. 2.3. Xác định năng lượng còn lại và năng lượng còn lại tối thiểu Để xác định năng lượng còn lại của mỗi nút trong giao thức E2E-LREEMR, mỗi gói tin RREQ và RREP được bổ sung trường re_energy chứa giá trị năng lượng còn lại của nút trên một con đường Định dạng mới của gói RREQ/RREP của giao thức E2E-LREEMR được minh hoạ trong Hình 2.1. SA DA Seq.No Expire pHop CETX CETE re_energy Hình 2.1. Định dạng gói tin RREQ/RREP của giao thức E2E-LREEMR Để xác định năng lượng còn lại tối thiểu của nút trên đường, bảng định tuyến của mỗi nút được bổ sung trường mre. Bảng 1 minh hoạ cấu trúc của một điểm truy cập (entry) trong bảng định tuyến của giao thức E2E-LREEMR. AOMDV E2E-LREEMR Địa chỉ đích (destination address) Địa chỉ đích (destination address) Số thứ tự (sequence number) Số thứ tự (sequence number) Danh sách đường (route list) Danh sách đường (route list) {(nexthop1, hopcount1), (nexthop2, {(nexthop1, cetx1, cete1, mre1), hopcount2),} (nexthop2, cetx2, cete2, mre2),} Thời gian quá hạn (expiration time out) Thời gian quá hạn (expiration time out) Bảng 2.1. Cấu trúc entry bảng định tuyến của giao thức AOMDV và E2E- LREEMR 40 Thuật toán 2: Quy tắc cập nhật đường của giao thức E2E-LREEMR Input: Thông tin quảng bá đường Output: Quy tắc cập nhật đường d d d 1 cetxj: cetx j etx j d d d 2 cetej: cete j ete j 3 re_:__ energyi initial energy i consumed energy i d 4 if (_re energyij mre ) then d 5 mreji:_ re energy 6 end if dd 7 if ()seqnumij seqnum then dd 8 seqnumij: seqnum 9 if ()id then dd 10 cetxij: cetx dd 11 ceteij: cete d 12 advertised_: hopcounti  13 else d 14 advertised_ hopcounti : 0 15 end if d 16 route_: listi  NULL d d d d d 17 insert (j , advertised _ hopcountj 1, cetx j , cete j , mre j ) into route_ listi dd dd 18 else if ()seqnumij seqnum and ((cetxij , i ) ( cetx , j )) dd and ((ceteij , i ) mre ) then 19 insert into // Chèn một đường dự phòng tách biệt mới vào bảng định tuyến d dd 20 if (___)num pathi  max num path and ((cetxji min( cetx , i )) 1.0) and then 21 insert into 22 23 41 24 end if 25 end if Việc xác định năng lượng còn lại và năng lượng còn lại tối thiểu được thể hiện từ dòng 3 đến dòng 6 trong Thuật toán 2. Trong đó, năng lượng còn lại của nút i (re_energyi) được tính trong dòng 3 bằng cách lấy năng lượng ban đầu của nút (initial_energyi) trừ đi năng lượng nút đó đã tiêu thụ (consumed_energyi). Các dòng 4 đến 6 của Thuật toán 2 được sử dụng để đảm bảo giá trị của trường mre trong bảng định tuyến của nút i là giá trị năng lượng còn lại nhỏ nhất của một nút trong số các nút thuộc đường d. Giá trị này được biểu diễn toán học bằng công thức (1). MREpath(,) S Dmin( RE i )  i  path ( S , D ) (1) trong đó MREpath(,) S D là năng lượng còn lại tối thiểu của một con đường từ nguồn S đến đích D. Nó được xác định bằng năng lượng còn lại ( REi ) nhỏ nhất của các nút i thuộc con đường này trong quá trình khám phá đường. 2.4. Xác định năng lượng truyền dự kiến Năng lượng tiêu thụ của một nút thành phần trong một con đường tách biệt theo nút để truyền các gói RREQ/RREP nhằm tìm đường nghịch/thuận được gọi là năng lượng truyền dự kiến (ETE) của nút đó. Độ đo định tuyến truyền thống là số chặng không được được sử dụng trong giao thức E2E-LREEMR để chọn nhiều đường giữa một cặp nút nguồn và đích bất kỳ. Thay vào đó, giao thức E2E- LREEMR sử dụng độ đo định tuyến kết hợp giữa CETX và CETE để tìm kiếm và lựa chọn các con đường tin cậy chứa các liên kết hiệu quả về năng lượng để truyền dữ liệu. Trong giai đoạn khám phá đường, giao thức E2E-LREEMR ước 42 lượng giá trị năng lượng truyền dự kiến ETEi path(,) S D của một nút i trên đường (S,D) theo công thức (2). ETEi path(,)(,) S D EC i path S D (2) trong đó ECi path(,) S D là lượng năng lượng tiêu thụ của nút i trong quá trình khám phá đường từ nút nguồn S đến nút đích D. 2.5. Xác định tổng năng lượng truyền dự kiến Trong giao thức E2E-LREEMR, mỗi gói tin RREQ và RREP mang một trường CETE được bổ sung thêm để chứa giá trị tổng năng lượng truyền dự kiến tích lũy (Hình 2.1). Khi một nút nguồn S bắt đầu truyền gói RREQ kiểu quảng bá tràn ngập, nó khởi tạo giá trị CETE trong gói RREQ của nó bằng 0. Tương tự, khi nút đích D gửi lại gói RREP, nó khởi tạo giá trị CETE trong gói RREP của nó bằng 0. Sau khi tính toán giá trị ETE của các nút thành phần trên con đường từ nút nguồn S đến nút đích D, giá trị tổng năng lượng truyền dự kiến CETE của đường được xác định bằng cách tính tổng năng lượng tiêu thụ của tất cả các nút trên đường theo công thức (3) và dòng 2 của Thuật toán 2. n (3) CETEpath(,) S D  ETE i i1, i path ( S , D ) trong đó CETEpath(,) S D là tổng năng lượng truyền dự kiến của đường giữa nút nguồn S và nút đích D. ETEi là năng lượng truyền dự kiến của nút thành phần i thuộc đường đó được xác định trong quá trình khám phá đường. 43 2.6. Xác định số lần truyền dự kiến Chất lượng của một liên kết giữa các nút thành phần trên một con đường được xác định theo số lượng gói RREQ hoặc RREP trong một khoảng thời gian được gọi là số lần truyền dự kiến (ETX). Giao thức E2E-LREEMR ước lượng các giá trị PRR forward(,) i j , PRRbackward(,) i j và ETX link(,) i j trong giai đoạn khám phá tuyến đường tương ứng theo các công thức (4), (5) và (6). ni PRR  generated (4) forward(,) i j w Tốc độ nhận gói (PRR) của một liên kết thuộc đường thuận giữa nút gửi i đến nút nhận j được kí hiệu là được ước lượng bằng cách đếm số gói i RREQ hoặc RREP do nút i gửi đi ( ngenerated ) trong khoảng thời gian w giây theo công thức (4). ni PRR  received (5) backward(,) i j w Tốc độ nhận gói của một liên kết thuộc đường nghịch giữa nút nhận j đến nút gửi i được kí hiệu là PRRbackward(,) i j được ước lượng bằng cách đếm số gói RREQ i hoặc RREP mà nút j nhận được (nreceived ) trong khoảng thời gian w giây theo công thức (5). 1 ETXlink(,) i j  (6) PRRforward(,)(,) i j PRR backward i j 44 Số lần truyền dự kiến ETX link(,) i j của liên kết giữa nút i và nút j được ước lượng theo giá trị tốc độ nhận gói của liên kết thuận PRR forward(,) i j và tốc độ nhận gói của liên kết nghịch PRRbackward(,) i j theo công thức (6) Các thành phần trong cấu trúc bảng định tuyến của các giao thức AOMDV và E2E-LREEMR được minh họa trong Bảng 1. Các kí hiệu và mô tả của chúng sử dụng trong chương này được trình bày trong Bảng 2.2. Kí hiệu Mô tả ETXlink(i,j) ETX của liên kết giữa nút i và nút j ETXpath(s,d) ETX của đường giữa nút nguồn s và nút đích d, còn gọi là CETX PRRforward(i,j) Tốc độ sinh gói điều khiển tại nút i của liên kết i->j PRRbackward(i,j) Tốc độ nhận gói điều khiển tại nút j của liên kết i->j MREpath(s,d) Năng lượng tối thiểu còn lại của đường s->d REi Năng lượng còn lại của nút i ETEi Năng lượng truyền dự kiến của nút i CETEpath(S,D) Tổng năng lượng truyền dự kiến của đường S->D pHop Nút đứng trước nút hiện tại trên một con đường i,j Các nút trung gian S,s Nút nguồn D,d Nút đích SA Địa chỉ nguồn DA Địa chỉ đích Bảng 2.2. Các kí hiệu được sử dụng 45 2.7. Xác định tổng số lần truyền dự kiến Trong giao thức E2E-LREEMR, mỗi gói tin RREQ và RREP được bổ sung một trường CETX để chứa giá trị tổng số lần truyền dự kiến. Khi nguồn S bắt đầu truyền quảng bá gói RREQ, nó khởi tạo CETX của RREQ bằng 0. Tương tự , khi đích D gửi lại RREP, nó khởi tạo CETX của RREP của nó bằng 0. Sau khi tính giá trị ETX của các liên kết giữa các nút dọc theo đường (S,D), giá trị CETX đường (S,D) được tính bằng cách lấy tổng giá trị ETX của tất cả các liên kết thuộc đường này theo công thức (7) và dòng 1 của Thuật toán 2. CETXpath(,)(,) S D  ETX link i j (7) link(,)(,) i j path S D Trong đó đường (S, D) là một tập hợp các liên kết liên tiếp trên đường từ nút nguồn S đến nút đích D được biểu diễn như sau: pathSD(,) SI ,1 ,, II 1 2 ,..., Ik 1 , I k , ID k ,  2.8. Chọn đường dựa trên CETX và CETE Trong giao thức E2E-LREEMR, mỗi gói RREQ và RREP được bổ sung thêm ba trường là: (i) Tổng số lần truyền dự kiến CETX của đường, (ii) Tổng năng lượng truyền dự kiến CETE của đường và (iii) năng lượng còn lại re_energy của nút (Hình 1). Tương tự như giao thức định tuyến AOMDV, trong giao thức E2E- LREEMR, khi một nút nhận được gói RREQ lần đầu tiên, nó sẽ quảng bá tiếp gói RREQ ngay lập tức. Giao thức E2E-LREEMR sử dụng các quy tắc cập nhật đường trong Thuật toán 2 để thiết lập các đường thuận cũng như đường đảo khi một nút i nhận được d một quảng bá đường đến đích d từ nút hàng xóm j. Các biến seqnumi , 46 d d d d d d advertised_ hopcounti , route_ listi , cetx j , cetej , re_ energy j và mrej tương ứng là số thứ tự, số chặng quảng bá, danh sách đường, tổng số lần truyền dự kiến, tổng năng lượng truyền dự kiến, năng lượng còn lại và năng lượng còn lại tối thiểu cho đích d tại nút i hoặc nút j tương ứng. Khi một nút nguồn S quảng bá kiểu ngập tràn toàn mạng gói RREQ đến nút đích D, nó khởi tạo giá trị các trường CETX và CETE của gói RREQ bằng 0, giá trị trường pHop (chặng đứng trước) của gói RREQ bằng chính định danh của mình (nút S), giá trị trường re_energy bằng lượng năng lượng hiện tại của nó (nút S). Tương tự, khi nút đích D gửi lại gói RREP cho nút nguồn S, nó khởi tạo giá trị các trường CETX và CETE của gói RREP bằng 0, giá trị trường pHop của gói RREP bằng địa chỉ của nó (nút D), giá trị trường re_energy bằng lượng năng lượng hiện tại của nó (nút D). Giá trị trường mre của điểm truy cập (entry) trong bảng định tuyến cũng được khởi tạo bằng năng lượng hiện tại của nút nguồn (trong quá trình thiết lập đường nghịch) hoặc bằng năng lượng hiện tại của nút đích (trong quá trình thiết lập đường thuận) trong quá trình khám phá đường. Khi nhận các gói RREQ hoặc RREP, mỗi nút trung gian sẽ tính giá trị ETX theo số lượng gói RREQ hoặc RREP qua hai nút đầu cuối của một liên kết và giá trị ETE theo năng lượng tiêu thụ của một nút phía bên kia của liên kết theo chiều con đường đang thiết lập. Giá trị CETX và CETE của giao thức E2E-LREEMR được cập nhật định kỳ bằng Thuật toán 2 với hai trường hợp chọn đường dựa trên hai độ đo CETX và CETE như sau: Trường hợp 1: Từ dòng 7 đến dòng 17 của Thuật toán 2, nút trung gian cập nhật các giá trị CETX và CETE trong bảng định tuyến của nó bằng các giá trị 47 CETX và CETE tương ứng của gói RREQ/RREP nó nhận được nếu số thứ tự của gói nhận được lớn hơn hơn số thứ tự của nút. Trường hợp 2: Từ dòng 18 đến dòng 25 của Thuật toán 2, nút trung gian cập nhật các giá trị CETX và CETE trong bảng định tuyến của nó bằng các giá trị CETX và CETE tương ứng của RREQ/RREP nó nhận được nếu thỏa mãn các điều kiện: (1) số thứ tự của gói nhận được bằng số thứ tự của nút, (2) giá trị CETX của gói RREQ/RREP nhận được lớn hơn giá trị CETX của nút và (3) giá trị CETE của gói RREQ/RREP nhận được nhỏ hơn giá trị MRE của đường. Hình 2.2. Ví dụ về tiến trình chọn đường của giao thức E2E-LREEMR Tiến trình chọn đường của giao thức E2E-LREEMR được minh họa bằng ví dụ ở Hình 2. Trong ví dụ này, giá trị số trong mỗi liên kết là giá trị ETX của liên kết, giá trị số trong mỗi hình chữ nhật là giá trị ETE của nút, giá trị số trong mỗi hình thoi là năng lượng còn lại của nút, S là nút nguồn và D là nút đích. Trong giao thức E2E-LREEMR, đường có giá trị CETX thỏa mãn 0 < CETX < 1 và giá trị CETE thỏa mãn CETE < MRE được chọn để truyền dữ liệu. Khi giá trị ETX 48 của một liên kết giữa hai nút bằng 0, nó được coi là một liên kết yếu không xem xét để truyền dữ liệu. Ví dụ: nếu nút F gửi 3 gói RREQ đến nút H trong 1 giây, ta có PRRforward(F,H) = 3. Nếu nút H chỉ nhận được 1 gói RREQ từ nút F trong 1 giây, ta có PRRbackward(F,H) = 1 và giá trị ETX của liên kết giữa nút F và H là 0,3. Đường S–C–G–D với CETX = 0,3, CETE = 16 và MRE = 70 được chọn làm đường chính để truyền dữ liệu và đường S–A–F–H–D với CETX = 0,6, CETE = 21 và MRE = 50 được chọn làm tuyến đường dự phòng. 2.9. Tổng kết Chương 2 Giao thức định tuyến E2E-LREEMR là một phiên bản cải tiến của giao thức định tuyến đa đường AOMDV. Nó sử dụng hai độ đo định tuyến là chất lượng liên kết thuộc đường P-LQE (còn gọi là CETX) và năng lượng nút thuộc đường P-NEE (còn gọi là CETE) để tìm nhiều nhiều con đường có hiệu quả năng lượng qua các liên kết tin cậy. Mục tiêu của giao thức này nâng cao hiệu năng định tuyến nhằm hỗ trợ giảm được chi phí định tuyến, tỷ lệ mất gói, chi phí định tuyến chuẩn hóa, độ trễ trung bình đầu cuối và mức tiêu thụ năng lượng. Ngoài ra, mục tiêu hỗ trợ cải thiện tỷ lệ phân phối dữ liệu và thông lượng cũng là những mục tiêu được hướng đến khi thiết kế giao thức định tuyến đa đường E2E-LREEMR. Để triển khai giao thức định tuyến đa đường E2E-LREEMR hướng tới các mục tiêu trên, đã có 6 thủ tục chính được thiết kế cho giao thức này bao gồm: (1) Xác định năng lượng còn lại và năng lượng còn lại tối thiểu, (2) Xác định năng lượng truyền dự kiến, (3) Xác định tổng năng lượng truyền dự kiến, (4) Xác định số lần truyền dự kiến, (5) Xác định tổng số lần truyền dự kiến và (6) Chọn đường dựa trên CETX và CETE. Các thủ tục này được triển khai thông qua việc điều chỉnh cấu trúc một số gói tin và bảng định tuyến của giao thức định tuyến cũng 49 như quy tắc cập nhật đường của thuật toán định tuyến được đưa ra trong Thuật toán 2 trên cơ sở cải tiến giao thức định tuyến AOMDV. 50 CHƯƠNG 3. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC 3.1. Thiết lập môi trường mô phỏng Hiệu suất của các giao thức định tuyến E2E-LREEMR và AOMDV được đánh giá theo mô hình điểm di động ngẫu nhiên bằng cách sử dụng phần mềm mô phỏng NS2.34 với sự thay đổi về số lượng kết nối (luồng dữ liệu) qua các kịch bản mô phỏng. Chi tiết của các thông số được sử dụng trong mô phỏng được trình bày trong Bảng 3.1. Tham số Giá trị Bộ mô phỏng NS-2.34 Tầng MAC 802.11 DCF Vùng mô phỏng 1500 m x 1500m Thời gian mô phỏng 300 giây Giao thức định tuyến AOMDV và E2E-LREEMR Kiểu lưu lượng dữ liệu CBR (UDP) Kích thước gói dữ liệu 512 bytes / gói Tải lưu lượng mạng 4 gói / giây Số lượng kết nối 1, 5, 10, 20, 30, 40 Năng lượng chờ 0,0001 W Năng lượng truyền 1,0 W Năng lượng nhận 1,0 W Năng lượng trạng thái ngủ 0,0001 W Năng lượng di chuyển 0,0002 W Thời gian di chuyển 0,0005 giây Năng lượng ban đầu 100 J Kích thước hàng đợi 50 51 Tham số Giá trị Số lượng nút 100 Thời gian tạm dừng 0 giây Tốc độ di chuyển 5 m/s Mô hình di động Ngẫu nhiên (Random Waypoint) Tần số 2,4 GHz Tốc độ dữ liệu 11,4 Mbps Phạm vi cảm nhận sóng mang 500 m Phạm vi nhận sóng mang 250 m Bảng 3.1. Các tham số của mô phỏng 3.2. Độ đo hiệu năng Độ đo hiệu năng là một tập hợp các độ đo định lượng được sử dụng để đánh giá các giao thức định tuyến trong mạng MANET theo chất lượng dịch vụ (QoS). Trong chương này, giao thức định tuyến E2E-LREEMR và AOMDV được so sánh và đánh giá hiệu năng theo 7 độ đo hiệu năng sau: 1. Tỷ lệ mất gói PLR (%): là tỷ lệ số gói dữ liệu không đến được nút đích trên tổng số gói dữ liệu sinh ra từ nút nguồn, được tính theo công thức (8). nn PLR sr100 (8) ns Trong đó, ns là tổng số gói được gửi đi từ nút nguồn, nr là tổng số gói nhận về tại nút đích. 2. Chi phí định tuyến chuẩn hoá NRO (%): là tỷ lệ số gói tin định tuyến trên tổng số gói dữ liệu truyền đến đích trong quá trình mô phỏng, được xác định theo công thức (9). 52 n NRO rt, 100 (9) ndr, với nrt, là tổng số gói điều khiển của giao thức định tuyến được truyền đi, ndr, là tổng số gói dữ liệu được nút đích nhận về. 3. Tổng năng lượng tiêu thụ E (J): là tổng năng lượng tiêu thụ của tất cả các nút trong môi trường mô phỏng, được xác định theo công thức (10). n EC EIii ER  (10) i1 Với EIi và ERi tương ứng là năng lượng ban đầu và năng lượng còn lại của nút i. 4. Thông lượng TP (Kbps): là lượng dữ liệu nhận được thành công trong thời gian mô phỏng, được xác định theo công thức (11). n 8 TP  r, bytes (11) Ts 1000 Với nr, bytes là số byte dữ liệu nhận được thành công tại nút đích, Ts là thời gian mô phỏng. 5. Tỷ lệ truyền thành công PDR (%): là tỷ lệ số gói tin dữ liệu nút đích nhận được trên tổng số gói dữ liệu được sinh ra tại nút nguồn, được xác định theo công thức (12). n PDR r 100 (12) ns 6. Chi phí định tuyến RO (số gói): là số gói tin điều khiển do giao thức định tuyến sinh ra trong quá trình mô phỏng. 53 7. Trễ đầu cuối trung bình E2ED (ms): là thời gian trung bình truyền thành công một gói tin dữ liệu từ nút nguồn đến nút đích, được xác định theo công thức (13). n TTRS E2 ED  i1 ii (13) n R S Với Ti là thời gian nút đích nhận thành công gói dữ liệu i và Ti là thời gian nút nguồn gửi gói dữ liệu i. 3.3. Kết quả mô phỏng và đánh giá 3.3.1. Tỷ lệ mất gói Kịch bản mô phỏng để đánh giá hiệu năng về tỉ lệ mất gói của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện với các giá trị các tham số mô phỏng trong Bảng 3.1 và số lượng luồng dữ liệu được thay đổi từ 1 đến 5, 10, 20, 30 và 40 luồng trong mỗi mô phỏng. Kết quả mô phỏng được đưa ra trong Bảng 3.2 và biểu đồ so sánh tỷ lệ mất gói của hai giao thức được biểu diễn trong Hình 3.1. Số Tỉ lệ mất gói (%) luồng dữ liệu AOMDV E2E-LREEMR 1 12,9 3,8 5 23,7 10,5 10 22,9 14,8 20 18,7 15,6 30 28,4 22,7 40 36,8 29,3 Bảng 3.2. Tỷ lệ mất gói của giao thức AOMDV và E2E-LREEMR 54 AOMDV E2E-LREEMR 40 35 30 25 20 15 Tỉ Tỉ mất gói lệ (%) 10 5 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.1. Tỷ lệ mất gói của giao thức theo số luồng dữ liệu Bảng 3.2 và Hình 3.1 cho thấy giao thức E2E-LREEMR có tỷ lệ mất gói thấp hơn so với giao thức AOMDV. Tính trung bình giữa các lần mô phỏng theo số lượng luồng dữ liệu khác nhau, giao thức E2E-LREEMR giảm tỷ lệ mất gói được xấp xỉ 32,7% so với giao thức AOMDV. 3.3.2. Chi phí định tuyến chuẩn hoá Kịch bản mô phỏng để đánh giá hiệu năng về chi phí định tuyến chuẩn hoá của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được đưa ra trong Bảng 3.3 và biểu đồ so sánh chi phí định tuyến chuẩn hoá của hai giao thức được biểu diễn trong Hình 3.2. 55 Số Chi phí định tuyến chuẩn hoá (%) luồng AOMDV E2E-LREEMR 1 28,9 24,3 5 9,8 7,1 10 5,3 4,3 20 3,1 2,8 30 4,2 3,4 40 4,7 3,5 Bảng 3.3. Chi phí định tuyến chuẩn hoá của AOMDV và E2E-LREEMR AOMDV E2E-LREEMR 35 30 25 20 15 10 5 Chi phí Chi định tuyến chuẩnhoá (%) 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.2. Chi phí định tuyến chuẩn hoá của giao thức theo số luồng dữ liệu Bảng 3.3 và Hình 3.2 cho thấy giao thức E2E-LREEMR có chi phí định tuyến chuẩn hoá thấp hơn so với giao thức AOMDV. Điều này có nghĩa là số lượng gói tin điều khiển của giao thức E2E-LREEMR ít hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E-LREEMR giảm được chi phí định tuyến chuẩn hoá xấp xỉ 18,8% so với giao thức AOMDV. 56 3.3.3. Tổng năng lượng tiêu thụ Kịch bản mô phỏng để đánh giá hiệu năng về chi phí định tuyến chuẩn hoá của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được đưa ra trong Bảng 3.4 và biểu đồ so sánh tổng năng lượng tiêu thụ của hai giao thức được biểu diễn trong Hình 3.3. Số Tổng năng lượng tiêu thụ (J) luồng AOMDV E2E-LREEMR 1 114,2 50,1 5 1307,2 649,5 10 3813,8 3054,7 20 9782,7 8979,4 30 16.272,9 14631,9 40 20110,9 17425,6 Bảng 3.4. Tổng năng lượng tiêu thụ của giao thức AOMDV và E2E-LREEMR AOMDV E2E-LREEMR 25 Nghìn 20 15 10 5 Tổngnăng lượng tiêu thụ (J) 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.3. Tổng năng lượng tiêu thụ của giao thức theo số luồng dữ liệu 57 Bảng 3.4 và Hình 3.3 cho thấy giao thức E2E-LREEMR có tổng năng lượng tiêu thụ thấp hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E- LREEMR giảm được tổng năng lượng tiêu thụ xấp xỉ 27,2% so với giao thức AOMDV. 3.3.4. Thông lượng Kịch bản mô phỏng để đánh giá hiệu năng về thông lượng của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được đưa ra trong Bảng 3.5 và biểu đồ so sánh thông lượng của hai giao thức được biểu diễn trong Hình 3.4. Số Thông lượng (kbps) luồng AOMDV E2E-LREEMR 1 14,3 15,6 5 50,8 59,2 10 105,1 117,0 20 205,5 212,5 30 239,5 254,0 40 261,5 279,4 Bảng 3.5. Thông lượng của giao thức AOMDV và E2E-LREEMR Bảng 3.5 và Hình 3.4 cho thấy giao thức E2E-LREEMR có thông lượng cao hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E-LREEMR có thông lượng cao hơn xấp xỉ 7% so với giao thức AOMDV. 58 AOMDV E2E-LREEMR 300 250 200 150 100 Thônglượng (kbps) 50 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.4. Thông lượng của giao thức theo số luồng dữ liệu 3.3.5. Tỷ lệ truyền thành công Kịch bản mô phỏng đánh giá tỷ lệ truyền thành công của giao thức E2E- LREEMR so với giao thức AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được đưa ra trong Bảng 3.6 và biểu đồ so sánh tỷ lệ truyền thành công của hai giao thức được biểu diễn trong Hình 3.5. Số Tỉ lệ truyền thành công (%) luồng AOMDV E2E-LREEMR 1 87,1 96,2 5 76,3 89,5 10 77,1 85,2 20 81,3 84,4 30 71,6 77,3 40 63,2 70,7 Bảng 3.6. Tỷ lệ truyền thành công của giao thức AOMDV và E2E-LREEMR 59 AOMDV E2E-LREEMR 120 100 80 60 40 20 Tỉ Tỉ truyền lệ thànhcông (%) 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.5. Tỷ lệ truyền thành công của giao thức theo số luồng dữ liệu Bảng 3.6 và Hình 3.5 cho thấy giao thức E2E-LREEMR có tỷ lệ truyền thành công cao hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E- LREEMR có tỷ lệ truyền thành công cao hơn xấp xỉ 10,3% so với giao thức AOMDV. 3.3.6. Chi phí định tuyến Số Chi phí định tuyến (số gói) luồng AOMDV E2E-LREEMR 1 88 60 5 85 60 10 79 57 20 71 53 30 85 59 40 88 61 Bảng 3.7. Chi phí định tuyến của giao thức AOMDV và E2E-LREEMR 60 Kịch bản mô phỏng để đánh giá hiệu năng về chi phí định tuyến của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được đưa ra trong Bảng 3.7 và biểu đồ so sánh chi phí định tuyến của hai giao thức được biểu diễn trong Hình 3.6. AOMDV E2E-LREEMR 100 90 80 70 60 50 40 30 20 Chi phí Chi định tuyến (sốgói) 10 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.6. Chi phí định tuyến của giao thức theo số luồng dữ liệu Bảng 3.7 và Hình 3.6 cho thấy giao thức E2E-LREEMR có chi phí định tuyến thấp hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E- LREEMR giảm được xấp xỉ 29,4% chi phí định tuyến so với giao thức AOMDV. 3.3.7. Trễ đầu cuối trung bình Kịch bản mô phỏng để đánh giá hiệu năng về trễ đầu cuối trung bình của giao thức định tuyến E2E-LREEMR so với giao thức định tuyến AOMDV được thực hiện tương tự như kịch bản đánh giá tỉ lệ mất gói. Kết quả mô phỏng được 61 đưa ra trong Bảng 3.8 và biểu đồ so sánh trễ đầu cuối trung bình của hai giao thức được biểu diễn trong Hình 3.7. Số Trễ đầu cuối trung bình (ms) luồng AOMDV E2E-LREEMR 1 1,478 1,093 5 1,906 1,32 10 2,148 1,913 20 3,284 3,096 30 6,769 4,438 40 17,697 11,296 Bảng 3.8. Trễ đầu cuối trung bình của giao thức AOMDV và E2E-LREEMR AOMDV E2E-LREEMR 20 18 16 14 12 10 8 6 4 Trễđầu trungcuối bình (ms) 2 0 1 5 10 20 30 40 Số luồng dữ liệu Hình 3.7. Trễ đầu cuối trung bình của giao thức theo số luồng dữ liệu Bảng 3.8 và Hình 3.7 cho thấy giao thức E2E-LREEMR có trễ đầu cuối trung bình thấp hơn so với giao thức AOMDV. Tính trung bình, giao thức E2E- LREEMR giảm được xấp xỉ 30,4% trễ đầu cuối trung bình so với AOMDV. 62 3.4. Tổng kết Chương 3 Chương 3 đã thực hiện việc cài đặt mô phỏng giao thức định tuyến E2E- LREEMR và giao thức định tuyến AOMDV trên phần mềm mô phỏng NS2. Có 7 độ đo hiệu năng đã được sử dụng để so sánh, đánh giá hiệu năng của hai giao thức này là tỷ lệ mất gói, chi phí định tuyến chuẩn hoá, tổng năng lượng tiêu thụ, thông lượng, tỷ lệ truyền thành công, chi phí định tuyến và trễ đầu cuối trung bình. Qua kết quả mô phỏng, có thể thấy rằng giao thức định tuyến E2E-LREEMR giảm được 32,7% tỷ lệ mất gói tin, 18,8% chi phí định tuyến chuẩn hóa, 27,2% tổng năng lượng tiêu thụ, 29,5% chi phí định tuyến và 30,4% trễ đầu cuối trung bình so với giao thức định tuyến AOMDV. Kết quả này là hoàn toàn hợp lý bởi vì giao thức định tuyến E2E-LREEMR chọn đường dựa trên giá trị giá trị CETX thỏa mãn 0 < CETX < 1 và giá trị CETE thỏa mãn CETE < MRE còn đối với giao thức định tuyến AOMDV, việc chọn đường chỉ dựa trên độ đo định tuyến là số chặng nên không đảm bảo độ tin cậy của các liên kết trên đường được chọn. Kết quả mô phỏng cũng cho thấy rằng giao thức định tuyến E2E-LREEMR cho hiệu năng cao hơn 7% thông lượng và 10,3% tỷ lệ phân phối gói tin so với giao thức định tuyến AOMDV. Kết quả này cũng hoàn toàn có thể giải thích do cơ chế chọn đường tin cậy của giao thức định tuyến E2E-LREEMR trên cơ sở độ đo định tuyến kết hợp giữa CETX và CETE và cơ chế chọn đường của giao thức định tuyến AOMDV theo độ đo định tuyến đơn giản là số chặng. 63 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Trọng tâm chính của đề tài này là nghiên cứu kỹ thuật định tuyến đa đường hiệu quả, tin cậy và tiết kiệm năng lượng của giao thức định tu