Luận văn Thạc sĩ Khoa học máy tính: Thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

15
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài này nghiên cứu về các thuật toán mới được đề xuất để dự đoán liên kết dựa trên thông tin quảng bá lại của các nút lân cận. Phương pháp phân cụm ảo cũng được nghiên cứu trong đề tài ngày để giảm thiểu chi phí định tuyến. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Lê Hồng Sơn THUẬT TOÁN QUẢNG BÁ LẠI THÔNG TIN ĐỊNH TUYẾN NHẰM TỐI THIỂU HOÁ CHI PHÍ ĐỊNH TUYẾN TRONG MẠNG AD HOC DI ĐỘNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Lê Hồng Sơn THUẬT TOÁN QUẢNG BÁ LẠI THÔNG TIN ĐỊNH TUYẾN NHẰM TỐI THIỂU HOÁ CHI PHÍ ĐỊNH TUYẾN TRONG MẠNG AD HOC DI ĐỘNG Ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. ĐỖ ĐÌNH CƯỜNG Thái Nguyên - 2020
LỜI CẢM ƠN Trong quá trình học tập, nghiên cứu đề tài luận văn: “Thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động” tôi đã nhận được sự giúp đỡ, chỉ bảo nhiệt tình của các thầy, cô giáo 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 để hoàn thành luận văn này. Với tình cảm chân thành, tôi xin bày tỏ lòng biết ơn đối với Ban giám hiệu, phòng Đào tạo, Khoa Công nghệ thông tin, các thầy giáo, cô giáo 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 đã tham gia quản lý, giảng dạy và giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu. Tôi xin bày tỏ sự biết ơn đặc biệt đến Thầy TS. Đỗ Đình Cường - người đã trực tiếp hướng dẫn, giúp đỡ về kiến thức, tài liệu và phương pháp để tôi hoàn thành đề tài luận văn thạc sĩ này. Tôi cũng xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, cổ vũ, khích lệ và giúp đỡ tôi trong suốt thời gian qua. Mặc dù đã có nhiều cố gắng trong suốt quá trình thực hiện đề tài, song có thể còn có những mặt hạn chế, thiếu sót. Tôi rất mong nhận được ý kiến đóng góp và sự chỉ dẫn của các thầy cô giáo và các bạn đồng nghiệp để luận văn được hoàn thiện. Thái Nguyên, ngày … tháng …. năm 2020 Học viên Lê Hồng Sơn
MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG ........... 3 1.1. Tổng quan về mạng ad hoc .................................................................... 3 1.1.1. Định nghĩa và đặc trưng của mạng ad hoc ...................................... 3 1.1.2. Đặc điểm của mạng ad hoc ............................................................. 5 1.1.3. Ứng dụng của mạng ad hoc............................................................. 6 1.2. Giao thức định tuyến AODV trong mạng ad hoc ................................ 10 1.2.1. Đặc điểm chung của giao thức định tuyến AODV ....................... 10 1.2.2. Cơ chế hoạt động của giao thức AODV ....................................... 12 1.3. Một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến ... 28 1.3.1. Vấn đề bão quảng bá của giao thức AODV .................................. 28 1.3.2. Phương pháp sử dụng các bộ đếm thời gian ................................. 28 1.3.3. Phương pháp khám phá đường theo xác suất ............................... 29 1.3.4. Phương pháp định tuyến đa đường ............................................... 29 1.3.5. Phương pháp lập lịch..................................................................... 30 1.3.6. Phương pháp quảng bá lại dựa trên thông tin từ các nút lân cận .. 31 1.4. Tổng kết Chương 1 .............................................................................. 31 CHƯƠNG 2. NGHIÊN CỨU THUẬT TOÁN CẢI TIẾN QUẢNG BÁ ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN TỪ CÁC NÚT LÂN CẬN ................... 33 2.1. Ý tưởng của phương pháp .................................................................... 33 2.2. Giao thức NKR..................................................................................... 34 2.3. Tính trễ quảng bá ................................................................................. 35 2.4. Tính xác suất quảng bá......................................................................... 36 2.5. Triển khai phân cụm ảo LVC ............................................................... 37 2.7. Chu kỳ hiệu lực của liên kết LEP......................................................... 39 2.6. Thuật toán quảng bá lại dựa trên thông tin nút lân cận........................ 41 2.8. Tổng kết Chương 2 .............................................................................. 46
CHƯƠNG 3. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU QUẢ ............................. 47 3.1. Các tham số mô phỏng và độ đo đánh giá hiệu năng .......................... 47 3.1.1. Các tham số mô phỏng .................................................................. 47 3.1.1. Các độ đo đánh giá hiệu năng ....................................................... 48 3.2. Đánh giá về tỉ lệ quảng bá .................................................................... 49 3.2.1. Tỉ lệ quảng bá theo lưu lượng mạng ............................................. 49 3.2.2. Tỉ lệ quảng bá theo số nút mạng ................................................... 50 3.2.3. Tỉ lệ quảng bá theo vận tốc di chuyển .......................................... 51 3.2.4. Tỉ lệ quảng bá theo băng thông yêu cầu ....................................... 52 3.3. Đánh giá về chi phí định tuyến ............................................................ 54 3.3.1. Chi phí định tuyến theo số nút mạng ............................................ 54 3.3.2. Chi phí định tuyến theo vận tốc di chuyển ................................... 55 3.4. Đánh giá về tỉ lệ tái liên kết ................................................................. 56 3.5. Tổng kết Chương 3 .............................................................................. 57 KẾT LUẬN ..................................................................................................... 59 TÀI LIỆU THAM KHẢO ............................................................................... 60
DANH MỤC BẢNG Bảng 2.1. Cường độ tín hiệu từ N1 đến các nút láng giềng ............................ 43 Bảng 3.1. Giá trị các tham số mô phỏng ......................................................... 47 Bảng 3.2. Dữ liệu về tỉ lệ quảng bá theo lưu lượng mạng .............................. 49 Bảng 3.3. Dữ liệu về tỉ lệ quảng bá theo số lượng nút mạng .......................... 50 Bảng 3.4. Dữ liệu về tỉ lệ quảng bá theo vận tốc di chuyển ........................... 51 Bảng 3.5. Dữ liệu về tỉ lệ quảng bá theo băng thông yêu cầu ........................ 53 Bảng 3.6. Dữ liệu về chi phí định tuyến theo số nút mạng ............................. 54 Bảng 3.7. Dữ liệu về chi phí định tuyến theo vận tốc di chuyển .................... 55 Bảng 3.8. Dữ liệu về tỉ lệ tái liên kết theo phạm vi truyền ............................. 56
DANH MỤC HÌNH Hình 1.1. Minh họa mạng ad hoc di động......................................................... 3 Hình 1.2. Ví dụ minh họa mạng ad hoc trên xe bus.......................................... 8 Hình 1.3. Một ví dụ của mạng Rooftop ............................................................ 9 Hình 1.4. Cấu trúc gói RREQ ......................................................................... 16 Hình 1.5. Cấu trúc gói RREP .......................................................................... 22 Hình 1.6. Cấu trúc gói RRER.......................................................................... 27 Hình 2.1. Sơ đồ ý tưởng của phương pháp ..................................................... 33 Hình 2.2. Tiến trình yêu cầu đường ................................................................ 36 Hình 2.3. Truyền dữ liệu trên cơ sở hệ số kết nối ........................................... 37 Hình 2.4. Quá trình truyền sử dụng LVC ....................................................... 38 Hình 2.5. Thủ tục truy vấn đường ................................................................... 43 Hình 2.6. Thủ tục trả lời đường....................................................................... 44 Hình 2.7. Hình trạng mạng cho thủ tục truy vấn và trả lời đường .................. 45 Hình 2.8. Lập lịch cho chu kỳ truyền dữ liệu ................................................. 45 Hình 3.1. Biểu đồ tỉ lệ quảng bá theo lưu lượng mạng ................................... 49 Hình 3.2. Biểu đồ tỉ lệ quảng bá theo số nút mạng ......................................... 51 Hình 3.3. Biểu đồ tỉ lệ quảng bá theo tốc độ di chuyển .................................. 52 Hình 3.4. Biểu đồ tỉ lệ quảng bá theo băng thông yêu cầu ............................. 53 Hình 3.5. Biểu đồ chi phí định tuyến theo số lượng nút mạng ....................... 54 Hình 3.6. Biểu đồ chi phí định tuyến theo vận tốc di chuyển di chuyển ........ 56 Hình 3.7. Biểu đồ tỉ lệ tái liên kết theo phạm vi truyền thông ........................ 57
1 MỞ ĐẦU Một mạng ad hoc di động là một tập hợp các nút không dây di động làm việc cùng nhau. Loại mạng này có thể hoạt động mà không cần cơ sở hạ tầng mạng để thực hiện kết nối và chúng có thể hoạt động theo kiểu tự quản. Do các nút là thiết bị di động nên việc các liên kết có thể bị phá vỡ tại bất kỳ thời điểm nào theo định hướng di chuyển trong không gian của các nút. Hai nút di động nằm ngoài phạm vi truyền thông vẫn có thể giao tiếp với nhau qua sự trợ giúp của các thiết bị khác trong phạm vi truyền thông của chúng. Mạng ad hoc di động cung cấp khả năng truyền thông cho các khu vực thiếu hoặc không có cơ sở hạ tầng truyền thông. Loại mạng này không sử dụng cơ sở hạ tầng mạng cố định. Nó sử dụng cơ chế định tuyến đa chặng để cung cấp kết nối mạng. Việc truyền thông trong mạng có thể được thực hiện khi sử dụng các giao thức định tuyến để để khám phá đường động. Khi đường truyền thông đã được thiết lập, dữ liệu sẽ được chuyển tiếp. Thủ tục bảo trì đường được sử dụng để thiết lập lại mạng cho môi trường động. Hiệu suất của mạng đối với người dùng là vấn đề quan trọng để duy trì chất lượng dịch vụ. Trong kịch bản truyền thông đa chặng, các gói dữ liệu xuất phát từ nút nguồn được các nút trung gian chuyển tiếp tới nút đích. Do tính di động của các nút trong mạng ad hoc di động, các tuyến đường có thể sẽ bị lỗi làm kích hoạt tiến trình khám phá đường. Điều này làm tăng trễ đầu cuối, giảm tỷ lệ phân phối thành công dữ liệu và quan trọng hơn là tăng chi phí hoạt động của các giao thức định tuyến. Do đó, việc giảm chi phí định tuyến trong quá trình khám phá đường là một yếu tố thiết yếu trong mạng ad hoc di động. Một số kỹ thuật định tuyến đa đường được sử dụng để giảm chi phí định tuyến trong ad hoc di động thông qua khả năng cân bằng tải, tăng thông lượng và các khả năng chịu lỗi. Vấn đề loại bỏ các điểm tắc cổ chai là vấn đề chính cần thực hiện nhằm tối
2 thiểu hoá tắc nghẽn. Phương pháp định tuyến đa đường chủ yếu được sử dụng để cải thiện chất lượng dịch vụ trong mạng. Mục đích của việc giảm chi phí định tuyến là để cải thiện hiệu quả của việc truyền thông điệp thành công. Bằng cách cải thiện tỉ lệ truyền thành công, các gói dữ liệu sẽ được truyền từ nút đầu tới nút cuối. Tuy nhiên, đối với các phương pháp định tuyến đa đường, chưa có nhiều phương pháp hiệu quả nhằm giảm thiểu chi phí định tuyến. Mục tiêu chính của đề tài này là nghiên cứu phương pháp giảm tải định tuyến trong mạng ad hoc di động trên cơ sở phân tích yêu cầu của các trung gian trong việc quá trình hình thành mạng. Điều này nhằm mục đích giảm lượng truy cập tài nguyên liên quan đến chất lượng dịch vụ. Việc thay đổi linh hoạt các thiết bị đầu cuối khả năng và tạo ra cơ chế định tuyến ổn định được thực hiện bằng cách tăng thời gian hoạt động của các nút mạng. Đề tài sẽ nghiên cứu về các thuật toán mới được đề xuất để dự đoán liên kết dựa trên thông tin quảng bá lại của các nút lân cận. Phương pháp phân cụm ảo cũng được nghiên cứu trong đề tài ngày để giảm thiểu chi phí định tuyến. Nó được sử dụng nhằm cải thiện cơ chế điều khiển cấu trúc mạng để tối thiểu hoá chi phí định tuyến và tăng thông lượng mạng bằng cách giảm tần suất lỗi của các liên kết. Cấu trúc luận văn được trình bày như sau: Chương 1 trình bày tổng quan về mạng ad hoc, giao thức định tuyến AODV và một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến của giao thức AODV. Phương pháp và thuật toán cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận sẽ được trình bày chi tiết trong Chương 2. Kết quả của việc mô phỏng, so sánh đánh giá hiệu năng của giao thức NKR – giao thức triển khai phương pháp cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận so với một số giao thức có liên quan được trình bày trong Chương 3. Cuối cùng là phần kết luận đưa ra những tổng kết và hướng phát triển của luận văn.
3 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG 1.1. Tổng quan về mạng ad hoc 1.1.1. Định nghĩa và đặc trưng của mạng ad hoc Theo định nghĩa của Tổ chức IETF (Internet Engineering Task Force), Mạng ad hoc không dây di động là một vùng tự trị (Autonomous System) của các bộ định tuyến được kết nối với nhau bằng liên kết không dây. Mỗi nút mạng vừa đóng vai trò là thiết bị đầu cuối vừa đóng vai trò là bộ định tuyến. Các nút có thể di chuyển một cách tự do làm cho kiến trúc của mạng thay đổi liên tục. Hình 1.1. Minh họa mạng ad hoc di động Như vậy có thể thấy mạng ad hoc di động bao gồm tập các nút không dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi truyền giới hạn, do đó chúng cần sự trợ giúp của các nút láng giềng để chuyển tiếp các gói dữ liệu. Hình 1.1 là một ví dụ minh họa cho một mạng ad hoc di động. Trong ví dụ này, các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là
4 một điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn. Vì vậy, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin từ nút nguồn tới nút đích. Để thực hiện được công việc này, các nút mạng phải sử dụng giao thức định tuyến phù hợp cho mạng ad hoc di động. Trong mạng ad hoc, liên kết 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. Để triển khai thành công được mạng ad hoc, thiết kế và công nghệ mạng phải đáp ứng được các yêu cầu sau:  Đảm bảo kết nối khi nút mạng di chuyển: 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.  Tính sẵn sàng hợp tác: 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”.  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).
5 1.1.2. Đặc điểm của mạng ad hoc 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 đó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 còn có một số đặc điểm nổi bật sau [11]:  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 ad hoc 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.  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ác nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng ad hoc 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.  Độ 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 hoc hơn là trong mạng có dây truyền thống.
6 1.1.3. Ứng dụng của mạng ad hoc Mạng ad hoc có rất nhiều ưu thế so với các mạng truyền thống về mặt ứng dụng trong những điều kiện 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)..  Ứ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. Mạng ad hoc 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ô hình mạng ad hoc 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. 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 ad hoc 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.  Các ứng dụng trong cuộc sống Mạng ad hoc 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.
7 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. 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 chia sẻ tài nguyên trong hội họp, 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ỏ. Đối với ứng dụng trong cuộc sống hàng ngày, môi trường mạng là mạng ad hoc 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. Ví dụ như 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.
8 Hình 1.2. Ví dụ minh họa mạng ad hoc trên xe bus  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.
9  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) 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ụ của mạng Rooftop  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
10 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. 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 AODV trong mạng ad hoc 1.2.1. Đặc điểm chung của giao thức định tuyến AODV AODV [2] là một giao thức định tuyến động, đa chặng và tự khởi động giữa các nút mạng di động tham gia vào mạng không dây kiểu không cấu trúc. AODV cho phép các nút mạng di động tìm được các con đường tới một nút đích nào đó một cách nhanh chóng và không yêu cầu các nút duy trì các con đường tới đích khi không truyền thông. AODV cho phép các nút di động làm việc được với sự thay đổi hình trạng của mạng hoặc liên kết bị đứt. Hoạt động của AODV là hoạt động tránh lặp vòng và cung cấp khả năng hội tụ nhanh khi hình trạng mạng thay đổi. Khi một liên kết bị đứt, AODV sẽ gây ra một hiệu ứng để báo cho tập các nút mạng di động biết rằng chúng có thể bỏ tính hiệu lực của các con đường sử dụng liên kết đã bị đứt. Một đặc điểm khác biệt quan trọng của AODV so với các thuật toán định tuyến truyền thống trong mạng có dây là nó sử dụng một số thứ tự đích cho mỗi một dòng trong bảng định tuyến. Số thứ tự đích được nút đích tạo ra được đưa vào cùng với các thông tin định tuyến khác và được gửi đi đến nút có yêu cầu. Nút yêu cầu sẽ lựa chọn một con đường có số thứ tự lớn nhất. Các thông điệp yêu cầu đường đi RREQ, đáp ứng đường đi RREP và lỗi đường đi RERR là các thông điệp được định nghĩa trong AODV. Các kiểu
11 thông điệp này được nhận về qua UDP và công việc xử lý IP header thông thường sẽ được áp dụng. Khi một nút muốn xác định một đường đi đến đích, nó sẽ quảng bá thông điệp RREQ. Một con đường có thể được xác định khi thông điệp RREQ đến được đích của nó hoặc một khi thông điệp RREQ đến được một nút trung gian có một con đường “đủ mới” đến đích. Một con đường “đủ mới” là một con đường tới đích hợp lệ trong bảng định tuyến có một số thứ tự ít nhất là bằng với số thứ tự chứa trong thông điệp RREQ. Nút chứa con đường này sẽ gửi thông điệp RREP dạng unicast tới nút yêu cầu đường đi. Mỗi một nút nhận thông điệp RREQ sẽ đưa vào bộ nhớ đệm để hình thành con đường quay trở lại cho thông điệp RREP. Thông điệp RREP quay trở lại qua các nút đã chuyển thông điệp RREQ cho đến khi tới được nút ban đầu yêu cầu đường đi. Các nút theo dõi trạng thái liên kết của các chặng tiếp theo trong các con đường hiện hành. Khi một liên kết bị đứt trong một con đường hiện hành được phát hiện, một thông điệp báo lỗi RERR sẽ được sử dụng để báo cho các nút khác biết rằng một liên kết đã bị đứt. Thông điệp RERR chỉ ra rằng các đích này không thể đi đến được nếu sử dụng liên kêt đã bị đứt. Để cho phép thực hiện được cơ chế báo cáo này, mỗi một nút phải giữ một “danh sách con trỏ trước”, danh sách này sẽ chứa địa chỉ IP của mỗi một nút hàng xóm được sử dụng để đi đến một đích xác định nào đó. AODV là một giao thức định tuyến và nó thực hiện công việc của mình bằng việc quản lý bảng định tuyến. Thông tin bảng định tuyến là các con đường có thời gian tồn tại ngắn, chẳng hạn một con đường tạm được tạo ra để lưu trữ đường trở lại các nút phát ra thông điệp RREQ. AODV sử dụng các trường sau cho mỗi một dòng trong bảng định tuyến:  Địa chỉ IP đích
12  Số thứ thự đích  Cờ số thứ tự đích hợp lệ  Các cờ trạng thái và cờ định tuyến khác (chẳng hạn như hợp lệ, không hợp lệ, đã được sửa, đang được sửa).  Network Interface  Số chặng  Chặng tiếp theo  Danh sách các con trỏ trước.  Thời gian sống Việc quản lý số thứ tự là một công việc thiết yếu để tránh định tuyến vòng, thậm chí khi các liên kết đã bị đứt và một nút không còn cung cấp các thông tin của nó về số thứ tự nữa. Một nút đích sẽ trở thành không tới được khi một liên kết bị đứt hoặc không hiện hành. Khi những điều kiện này xảy ra, một con đường sẽ bị mất hiệu lực bằng thao tác gán số thứ tự và đánh dấu con đường đó trong bảng định tuyến là con đường không hợp lệ. 1.2.2. Cơ chế hoạt động của giao thức AODV  Duy trì các số thứ tự Mọi bảng định tuyến trong mọi nút di động trong mạng không dây kiểu không cấu trúc phải chứa các thông tin mới nhất về số thứ tự cho địa chỉ IP của nút đích đối với mỗi một dòng trong bảng định tuyến khi các nút duy trì bảng định tuyến của mình. Số thứ tự này được gọi là “số thứ tự đích”. Nó được cập nhật khi một nút nhận được thông tin mới về số thứ tự từ các thông điệp RREQ, RREP hoặc RERR liên quan đến đích. AODV phụ thuộc vào mỗi nút trong
13 mạng khi nút này duy trì các số thứ tự đích của nó nhằm đảm bảo tránh khỏi việc định tuyến lặp vòng cho mọi con đường đi ra từ nút đó. Một nút đích sẽ tăng số thứ tự của nó trong hai tình huống: Trước khi một nút bắt đầu việc khám phá một con đường mới, nó phải tăng số thứ tự của mình. Điều này nhằm ngăn cản sự xung đột với các con đường trước đó đã được hình thành khi quay trở lại chính nó bằng thông điệp RREQ. Trước khi một nút đích khởi tạo một thông điệp RREP để trả lời thông điệp RREQ mà nó nhận được, nó phải cập nhật số thứ tự của nó bằng một số thứ tự hiện tại lớn nhất và số thứ tự đích có trong gói tin RREQ. Khi một nút đích tăng số thứ tự của nó, số thứ tự mới phải là số thứ tự chưa được sử dụng lần nào. Nếu số thứ tự hiện đang sử dụng đã là số lớn nhất (chẳng hạn bằng 4294967295 với 32 bit số nguyên không dấu), số thứ tự tiếp theo sẽ quay về bằng 0. Nói cách khác, nếu một số thứ tự hiện tại có giá trị là 2147483647 là số dương lớn nhất có thể, nếu phép toán lấy phần bù của 2 được áp dụng với số nguyên 32 bit, giá trị tiếp theo sẽ là 2147483648 là giá trị âm lớn nhất có thể trong cùng một hệ thống số. Việc biểu diễn các số âm không liên quan đến việc tăng các số thứ tự AODV. Đây là sự tương phản trong dạng so sánh kết quả của 2 số thứ tự AODV. Để khẳng định rằng thông tin về một đích thông tin mới, một nút phải so sánh giá trị số thứ tự hiện tại của nó với số thứ tự trong các thông điệp AODV mà nó nhận được. Việc so sánh này phải được hoàn tất bằng phép toán số học có dấu. Điều này là cần thiết vì quá trình gán số thứ tự là quá trình quay vòng. Nếu hiệu của số thứ tự nhận được trừ đi số thứ tự hiện tại được lưu trữ là một số âm thì thông tin liên quan đến đích trong thông điệp AODV sẽ bị bỏ qua.