Chương 1 của luận văn đã giới thiệu khái quát về mạng vô tuyến cũng như mạng con của nó là mạng cảm biến vô tuyến (WSNs) và vấn đề định tuyến trong mạng WSN là vấn đề đáng quan tâm để định hướng cho việc nghiên cứu trong các chương tiếp theo. TIEU LUAN MOI download : skknchat@gmail.com 15 CHƢƠNG 2: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN VÔ TUYẾN Nội dung chương bao gồm những phần chính sau: - Trình bày về các giao thức định tuyến trong mạng WSN - Trình bày về các thuật toán định tuyến trong mạng WSN 2. Giao thức định tuyến [5]-[6]-[10]-[13] Thông thường, việc định tuyến trong WSN có thể được chia thành định tuyến phẳng (flat-based), phân cấp (hierarchical-based), và dựa trên vị trí (location-based) phụ thuộc vào cấu trúc của mạng. Trong định tuyến phẳng, mọi nút thường được gán các vai trò hay chức năng như nhau.
Trong định tuyến phân cấp, các nút sẽ thực hiện các vai trò khác nhau trong mạng. Trong định tuyến dựa trên vị trí, các vị trí của các nút cảm biến được khai thác để định tuyến dữ liệu trong mạng. Hơn nữa, các giao thức định tuyến này có thể được chia lớp thành các loại như: đa đường (multipath-based), theo yêu cầu (query-based), thỏa thuận (negotiation-based), chất lượng dịch vụ (QoS-based), hay chặt chẽ (coherent-based routing techniques) phụ thuộc vào hoạt động của giao thức. Thêm vào đó, các giao thức định tuyến có thể được chia thành ba loại là proactive, reactive và hybrid phụ thuộc vào nút nguồn tìm ra đường tới đích như thế nào.
Trong các giao thức proactive, mọi đường đi được tính toán trước khi chúng thực sự được cần đến, trong khi đối với giao thức reactive, các đường đi được tính toán theo yêu cầu. Các giao thức hybrid sử dụng một tổ hợp ý tưởng của hai giao thức trên. Khi mọi nút cảm biến là tĩnh, việc sử dụng các giao thức định tuyến điều khiển bằng bảng sẽ dễ dàng hơn là sử dụng các giao thức phản ứng. Một lượng lớn năng lượng được sử dụng trong việc phát hiện và thiết lập đường đi của các giao thức phản ứng.
Các lớp giao thức định tuyến khác được gọi là các giao thức định tuyến cộng tác (cooperative). Trong việc định tuyến cộng tác, các nút gửi dữ liệu tới một nút trung tâm nơi mà dữ liệu có thể được kết tập lại và có thể được đưa tới việc xử lý cao hơn, do đó chi phí định tuyến sẽ giảm và việc sử dụng năng lượng cũng giảm. Nhiều giao thức khác trông cậy vào thông tin thời gian và thông tin vị trí. Hình dưới đây mô tả sự phân lớp các giao thức định tuyến trong mạng cảm biến vô tuyến.
TIEU LUAN MOI download : skknchat@gmail.com 16 Các giao thức định tuyến trong mạng WSN Cấu trúc mạng Thao tác giao thức Định Định Định Định Định Định Định Định tuyến tuyến tuyến tuyến tuyến tuyến tuyến tuyến các các dựa dựa dựa dựa dựa dựa trên mạng mạng vào vị trên trên đa trên trên sự liên phẳng phân cấp trí sự đường truy QoS kết chặt điều vấn chẽ chỉnh Hình 5: Sự phân lớp các giao thức định tuyến trong mạng cảm biến vô tuyến Kiến trúc phẳng có một vài lợi ích bao gồm số lượng mào đầu tối thiểu để duy trì cơ sở hạ tầng, và có khả năng khám phá ra nhiều đường giữa các nút truyền dẫn để chống lại lỗi. Đối với kiến trúc thứ hai là kiến trúc phân cấp theo cụm, lợi dụng cấu trúc của mạng để đạt được hiệu quả về năng lượng, sự ổn định, sự mở rộng. Trong loại giao thức này các nút mạng tự tổ chức thành các cụm trong đó một nút có mức năng lượng cao hơn các nút khác và đóng vai trò là nút chủ. Nút chủ thực hiện phối hợp hoạt động trong cụm và chuyển tiếp thông tin giữa các cụm với nhau.
Việc tạo thành các cụm có khả năng làm giảm tiêu thụ năng lượng và tăng thời gian sống của mạng. Còn loại kiến trúc thứ ba sử dụng phương pháp trung tâm dữ liệu nhằm phân bố yêu cầu (interest) bên trong mạng. Phương pháp này sử dụng thuộc tính dựa trên tên do đó một nút nguồn truy vấn một thuộc tính của sự kiện/hiện tượng hơn là một nút riêng lẻ. Một giao thức khác có thể truyền sự quan tâm tới các nút bao gồm quảng bá, các thuộc tính dựa trên mutilcasting, geo-casting.
Loại giao thức thứ tư là dựa vào vị trí để đánh địa chỉ cho các nút cảm biến. Loại giao thức này rất có ích cho những ứng dụng nơi mà vị trí của các nút cảm biến trong vùng địa lý được bao phủ bởi mạng liên quan đến truy vấn được đưa ra bởi nút nguồn. TIEU LUAN MOI download : skknchat@gmail. Các giao thức định tuyến dựa trên cấu trúc mạng [5]-[6] 2.
Định tuyến các mạng phẳng Loại giao thức định tuyến đầu tiên là các giao thức định tuyến phẳng multihop. Trong các mạng phẳng, thông thường mỗi nút đóng vai trò như nhau và các nút cảm biến cộng tác cùng với nhau để thực thi các tác vụ cảm nhận. Vì có rất nhiều nút cho nên không thể gán cho từng nút các định danh toàn cục, do vậy cần phải định tuyến theo trung tâm dữ liệu (data centric). Việc định tuyến này sử dụng trạm cơ sở (BS – base station) gửi yêu cầu tới các vùng xác định và chờ dữ liệu đến từ các cảm biến nằm trong vùng đã chọn đó.
Khi dữ liệu được yêu cầu thông qua các truy vấn, việc đặt tên theo thuộc tính rất cần thiết để xác định các thuộc tính của dữ liệu. Chúng ta sẽ xem xét một số giao thức và ưu điểm cũng như hiệu năng của chúng. Giao thức trung tâm dữ liệu: Flooding và Gossiping Flooding là kỹ thuật chung thường được sử dụng để tìm ra đường và truyền thông tin trong mạng adhoc vô tuyến và hữu tuyến. Chiến lược định tuyến này rất đơn giản và không phụ thuộc vào cấu hình mạng và các giải thuật định tuyến phức tạp.
Phát tràn sử dụng phương pháp reactive nhờ đó mỗi nút nhận dữ liệu hoặc điều khiển dữ liệu để gửi các gói tới các nút lân cận. Sau khi truyền, một gói sẽ được truyền trên tất cả các đường có thể. Trừ khi mạng bị ngắt không thì các gói sẽ truyền đến đích Hình 6: Các mô hình RandomWalk, Flooding, Gossiping Hơn nữa khi cấu hình mạng thay đổi các gói sẽ truyền theo những tuyến mới giải thuật này sẽ tạo ra vô hạn các bản sao của mỗi gói khi đi qua các nút. Giải thuật này có 3 nhược điểm lớn như sau: thứ nhất là hiện tượng bản tin kép.
Tức là các gói dữ liệu giống nhau được gửi đến cùng nút. Thứ hai là hiện tượng chồng chéo, tức là các TIEU LUAN MOI download : skknchat@gmail.com 18 nút cùng cảm nhận một vùng không gian và do đó tạo ra các gói tương tự nhau gửi đến các nút lân cận. Và thứ ba đó là thuật toán này không hề quan tâm đến vấn đề năng lượng của các nút, các nút sẽ nhanh chóng tiêu hao năng lượng và làm giảm thời gian sống của mạng. Một sự cải tiến của giao thức này là Gossiping, thuật toán này cải tiến ở chỗ mỗi nút sẽ ngẫu nhiên gửi gói mà nó nhận được đến một trong các nút lân cận của nó.
Thuật toán này làm giảm số lượng các gói lan truyền trong mạng, tránh hiện tượng bản tin kép tuy nhiên có nhược điểm là có thể gói sẽ không bao giờ đến được đích. Hai giao thức SPIN (Sensor Protocols for Information via Negotiation – Các giao thức cảm biến thông tin thông qua điều chỉnh) và DD (Directed Diffusion – Giao thức lan tỏa trực tiếp) ban đầu được sử dụng nhằm mục đích tiết kiệm năng lượng thông qua việc điều chỉnh dữ liệu và loại bỏ các dữ liệu dư thừa. Hai giao thức này sau đó được dùng để thiết kế nên nhiều giao thức khác nhưng vẫn đi theo mục đích đặt ra. Giao thức này giả định rằng tất cả các nút trong mạng cảm biến đều có khả năng làm trạm cơ sở.
Điều này cho phép việc sử dụng bất kỳ một nút nào có thể nhận được thông tin ngay lập tức. Các giao thức này sử dụng tài nguyên của các nút lân cận với dữ liệu tương tự, và do đó cần phải có chi phí để phân phối dữ liệu mà các nút khác không có. Họ SPIN sử dụng việc điều chỉnh dữ liệu và các thuật toán thích ứng tài nguyên. Các nút chạy SPIN phân công một tên mức cao để mô tả một cách hoàn chỉnh dữ liệu thu được của chúng (gọi là siêu dữ liệu (meta-data)) và thực hiện các việc điều chỉnh siêu dữ liệu trước khi dữ liệu bất kỳ được truyền đi.
Điều này đảm bảo rằng không có dư thừa dữ liệu được gửi qua mạng. Ngữ nghĩa của các định dạng siêu dữ liệu được các ứng dụng đặc tả và không được quy định tại SPIN. Ví dụ, các cảm biến có thể sử dụng ID duy nhất của chúng để báo cáo siêu dữ liệu nếu chúng bao phủ một khu vực nhất định đã biết. Ngoài ra, SPIN có thể truy cập vào các mức năng lượng hiện hành của nút và thích nghi với các giao thức nó hoạt động dựa trên lượng năng lượng còn lại.
Những giao thức này làm việc theo cả cách sử dụng bảng điều khiển và phân phối thông tin trên mạng, ngay cả khi người sử dụng không yêu cầu bất kỳ dữ liệu nào. TIEU LUAN MOI download : skknchat@gmail.com 19 Họ SPIN được thiết kế để giải quyết các thiếu sót của việc phát tràn bằng cách điều chỉnh và thích ứng tài nguyên. Họ các giao thức SPIN được thiết kế dựa trên hai ý tưởng cơ bản: - Các nút cảm biến hoạt động hiệu quả hơn và bảo tồn năng lượng bằng cách gửi dữ liệu mô tả các dữ liệu cảm biến thay vì gửi tất cả dữ liệu, chẳng hạn, các nút hình ảnh và các nút cảm biến phải theo dõi những thay đổi trong các nguồn năng lượng của chúng. - Các giao thức thông thường như phát tràn hoặc dựa trên giao thức định tuyến gossiping lãng phí năng lượng và băng thông khi gửi các bản sao không cần thiết của dữ liệu khi các bộ cảm biến bao phủ các khu vực chồng chéo.
Những bất lợi của việc phát tràn bao gồm sự suy sụp, đó là do các bản sao của thông điệp được gửi tới cùng một nút, sự chồng chéo xảy ra khi hai nút cảm biến cùng một vùng sẽ gửi gói tin tương tự tới cùng một nút hàng xóm, và tài nguyên bị tiêu tốn do việc tiêu thụ một lượng lớn năng lượng mà không cần xem xét các ràng buộc về năng lượng.