Các phƣơng pháp chuyển tiếp gói tin để đạt đƣợc hiệu suất (xét về số lƣợng gói tin chuyển đƣợc hoặc trễ) còn phải xét đến cấu hình của mạng. Vì vậy, khi lựa chọn tuyến truyền, cần bổ sung thông tin về nút lân cận phù hợp để chuyển tiếp gói tin. Sự phù hợp có thể đƣợc đánh giá thơng qua nhiều tiêu chí khác nhau, ví dụ số lƣợng bƣớc nhảy tối thiểu hoặc năng lƣợng tối thiểu cần để truyền gói tin tới đích thơng qua các nút lân cận. Các thông tin
này đƣợc lƣu trong bảng định tuyến, nhƣ minh họa trong bảng 4.2.
Bảng 4.2 Bảng địnhtuyến của một số nút minh họa trong hình 4.4, sử dụng thơng số số bƣớc nhảy Đích Bƣớc kế tiếp Số bƣớc nhảy Đích Bƣớc kế tiếp Số bƣớc nhảy A A 1 A S 2 D A 3 D C 2 D B 3 D S 3 D E 2 E A 2 E E 1 E C 3
(a) Bảng định tuyến của nút S (b) Bảng định tuyến của nút B
Xác định các bảng định tuyến này là nhiệm vụ của giải thuật định tuyến với sự trợ giúp của giao thức định tuyến. Trong các mạng hữu tuyến, các giao thức này thƣờng dựa trên trạng thái đƣờng truyền hoặc các giải thuật vector khoảng cách. Trong mạng vô tuyến, mạng di động hoặc mạng đa bƣớc nhảy cần sử dụng các khái niệm khác. Định truyến trong mạng cỡ lớn gặp nhiều khó khăn, thiết kế phải đảm bảo sự chính xác, tính ổn định và khả năng tối ƣu. Các giao thức định tuyến ở đây có thể là phân bố, thƣờng yêu cầu chi phí thấp, tự cấu hình và có khả năng hoạt động trong các cấu hình mạng thƣờng xuyên thay đổi. Cùng với các đặc tính của mạng cảm biến khơng dây nhƣ tiết kiệm năng lƣợng và băng thông hạn chế, đặt ra nhiều thách thức cho giải thuật định tuyến để đáp ứng yêu cầu lƣu lƣợng và kéo dài thời gian sống của mạng.
4.3.2 Các thách thức trong kỹ thuật định tuyến
Mạng cảm biến khơng dây có nhiều điểm chung với mạng hữu tuyến và mạng ad hoc. Tuy nhiên, mạng cảm biến có một số đặc điểm riêng, do đó địi hỏi phải có thiết kế giao thức định tuyến riêng cho mạng.
143
a. Kích thước mạng và đặc tính thay đổi theo thời gian
Nút cảm biến hoạt động với khả năng tính tốn, lƣu trữ và thơng tin hạn chế do giới hạn
nguồn năng lƣợng cung cấp. Mật độ cảm biến có thể rất ít, cũng có thể rất dày đặc. Trong
mạng cảm biến, nút ở trạng thái động và khả năng thích ứng cao do yêu cầu tự phân bố và tiết
kiệm năng lƣợng. Các nút phải điều chỉnh hoạt động để đáp ứng với sự thất thƣờng và không
thể đốn trƣớc của kết nối khơng dây gây ra bởi mức nhiễu cao và can nhiễu tần số vô tuyến
làm giảm chất lƣợng ứng dụng.
b. Tài nguyên hạn chế
Các nút cảm biến đƣợc thiết kế với độ phức tạp ít nhất và giá thành thấp để đáp ứng cho các mạng cỡ lớn. Năng lƣợng là vấn đề quan tâm nhiều nhất trong mạng cảm biến, phải tạo ra hoạt động lâu dài trong điều kiện nguồn pin hạn chế. Truyền đa đƣờng qua mạng khơng dây chính là nguồn gây tiêu tốn công suất nhiều nhất. Vấn đề quản lý nguồn năng lƣợng trở thành một thách thức với mạng cảm biến không dây trong nhiều ứng dụng quan trọng.
Các kiểu dữ liệu trao đổi giữa các nút phụ thuộc vào đặc điểm riêng của từng ứng dụng
cụ thể. Có những ứng dụng yêu cầu thu thập dữ liệu theo chu kỳ hay khi có sự xuất hiện của
một sự kiện nào đó. Trƣờng hợp khác dữ liệu lại đƣợc tập hợp, lƣu trữ, xử lý bởi một nút sau
đó đƣợc chuyển tiếp cho các nút khác. Đối với mạng quy mô lớn, số lƣợng lớn nút cảm biến
phân bố trên khu vực rộng, các kiểu dữ liệu phức tạp cần có các giao thức định tuyến tối ƣu để đảm bảo chất lƣợng thông tin và thời gian sử dụng của mạng. Do đó thiết kế giải thuật định
tuyến hiệu quả là yêu cầu quan trọng, đảm bảokhả năng mở rộng quy mô và tính ổn định của
mạng cảm biến khơng dây, cũng nhƣ sự phát triển mạnh mẽ các ứng dụng trong tƣơng lai.
c. Mơ hình dữ liệu
Mơ hình dữ liệu miêu tả dịng di chuyển thơng tin giữa các nút cảm biến và bộ thu dữ liệu. Các mơ hình này thƣờng phụ thuộc vào bản chất của ứng dụng về khía cạnh cách thức yêu cầu và sử dụng dữ liệu. Các mơ hình dữ liệu sử dụng cho các ứng dụng cảm biến phải đáp ứng nhu cầu thu thập dữ liệu và yêu cầu tƣơng tác. Một số các ứng dụng cảm biến yêu cầu các mơ hình thu thập dữ liệu dựa trên q trình lấy mẫu định kỳ hoặc đƣợc điều khiển bởi sự xuất
hiện của các sự kiện nào đó. Trong một số ứng dụng khác, dữ liệu có thểđƣợc thu thập và lƣu
lại, sau đó có thể đƣợc xử lý và tập hợp lại bởi một nút cảm biến trƣớc khi đƣợc chuyển tiếp tới bộ thu. Cũng có những ứng dụng yêu cầu các mơ hình dữ liệu hai chiều, nghĩa là phải đảm bảo tƣơng tác hai chiều giữa các cảm biến và bộ thu dữ liệu.
u cầu phải hỗ trợ nhiều dạng mơ hình dữ liệu làm tăng độ phức tạp trong việc thiết kế các giao thức định tuyến. Tối ƣu hóa giao thức định tuyến cho các yêu cầu dữ liệu nào đó của một ứng dụng trong khi phải cung cấp đa dạng các mơ hình dữ liệu và đảm bảo hiệu suất cao nhất (về khả năng mở rộng, độ tin cậy, khả năng đáp ứng và hiệu quả năng lƣợng) trở thành một thách thức lớn trong kỹ thuật định tuyến.
4.3.3 Các chiến lượcđịnh tuyến trong WSN
Định tuyến trong mạng cảm biến khơng dây gặp khó khăn lớn là tạo sự cân bằng giữa độ nhạy và tính hiệu quả. Sự cân bằng giữa đặc tính giới hạn khả năng xử lý và thông tin của các nút cảm biến với phần chi phí cần thiết. Trong mạng cảm biến khơng dây, chi phí cho quản lý (overhead) đƣợc tính dựa trên băng thơng sử dụng, cơng suất tiêu thụ và yêu cầu xử lý
144
nút di động. Vì nếu chi phí quản lý q lớn gây lãng phí năng lƣợng, băng thơng, thời gian xử
lý, tăng độ trễ gói tại nút nhƣng chất lƣợng dữ liệu tốt hơn. Ngƣợc lại, chi phí quản lý nhỏ thì
thời gian xử lý, băng thơng, độ trễ thấp, tuy nhiên chất lƣợng có thể giảm. Thách thức của giao thức định tuyến chính là tìm ra giải thuật để cân bằng những yêu cầu này.
Nhìn chung, nếu dựa trên cấu trúc mạng, định tuyến trong WSN có thể đƣợc chia thành các dạng:
Định tuyến ngang hàng (flat-based routing): Trong định tuyến ngang hàng, tất cả các
nút thƣờng có vai trị hoặc chức năng nhƣ nhau. Dạng này dành cho kiến trúc mạng phẳng, trong đó tất cả các nút xem nhƣ cùng cấp. Kiến trúc phẳng có nhiều lợi ích nhƣ tối thiểu chi phí để xây dựng hạ tầng mạng và có khả năng tìm ra nhiều đƣờng liên lạc giữa các nút với sai số cho phép.
Địnhtuyến phân cấp (hierarchical-based routing): Trong định tuyến phân cấp, các nút sẽ có các vai trị khác nhau trong mạng. Dạng thứ hai này dùng trong mạng có cấu trúc tiết kiệm năng lƣợng, ổn định và khả năng mở rộng. Các nút mạng đƣợc sắp xếp vào các cụm, trong đó một nút có năng lƣợng lớn nhất đóng vai trị cụm chủ (cluster head). Cụm chủ có trách nhiệm phối hợp các hoạt động giữa các nút trong cụm và chuyển thông tin giữa các cụm. Việc phân cụm giảm năng lƣợng tiêu thụ và kéo dài thời gian sống của mạng.
Định tuyến theo vị trí (location-based routing): Trong định tuyến theo vị trí, vị trí của các nút cảm biến sẽ đƣợc khai thác để thiết kế tuyến truyền dữ liệu trong mạng. Định tuyến theo vị trí rất hữu ích cho các ứng dụng mà vị trí của nút trong một vùng địa lý của mạng liên quan đến yêu cầu của nút nguồn. Yêu cầu có thể là xác định vùng diện tích cụ thể nơi có thể xảy ra một hiện tƣợng mà nút nguồn quan tâm hoặc xác định vùng lân cận của một điểm cụ thể trong môi trƣờng mạng.
Nếu dựa trên hoạt động giao thức, định tuyến trong WSN có thể đƣợc phân thành các dạng:
Định tuyến đa đƣờng (multipath-based): sử dụng đồng thời nhiều tuyến để truyền dữ liệu.
Định tuyến theo yêu cầu (query-based): nút có nhu cầu nhận dữ liệu sẽ gửi yêu cầu, khởi xƣớng quá trình truyền tin.
Định tuyến theo thỏa thuận (negotiation-based): các nút sẽ truyền dữ liệu thỏa thuận trƣớc khi thiết lập tuyến.
Định tuyến theo chất lƣợng dịch vụ (QoS-based): giao thức định tuyến phải đáp ứng các yêu cầu nhất định về chất lƣợng dịch vụ.
Định tuyến nhất quán (coherent-based): chỉ thực hiện tối thiểu các hoạt động xử lý trong mạng.
Tùy thuộc vào cách thức nút nguồn tìm đƣợc tuyến đƣờng truyền tới nút đích, các giải
thuật định tuyến cũng có thể đƣợc chia thành ba dạng: proactive, reactive và hybrid.
Proactive (khởi tạo trƣớc): còn gọi là table driven, dựa trên sự phân phát theo chu kỳ thông tin định tuyến để đạt đƣợc các bảng định tuyến nhất quán và chính xác đến tất
145
cả các nút của mạng. Cấu trúc mạng có thể là phẳng hay phân cấp. Dùng phƣơng pháp
này cho cấu trúc phẳng có khả năng tìm ra đƣợc đƣờng đi tối ƣu.
Reactive (phản ứng): xây dựng tuyến đến một đích đến nào đó theo nhu cầu. Giải thuật
này thƣờng khơng xây dựng thông tin chung đi qua tất cả các nút của mạng. Do đó
chúng dựa trên định tuyến động để tìm ra đƣờng đi từ nguồn đến đích. Giải thuật định tuyến reactive thay đổi theo cách mà chúng điều khiển quá trình flooding để giảm thơng tin chi phí quản lý và cách các tuyến đƣợc tính tốn và xây dựng lại khi liên kết khơng thực hiện đƣợc.
Hybrid (hỗn hợp): dựa trên cấu trúc mạng để tạo tính ổn định và khả năng mở rộng
cho mạng có kích thƣớc lớn. Trong những giải thuật dạng này, mạngđƣợc phân chia
thành các cụm (cluster). Do số lƣợng lớn và tính di động, mạng có đặc tính động khi các nút vào hay tách ra khỏi các cụm. Giải thuật định tuyến hybrid có thể đƣợc dùng
theo mơ hình định tuyến proactive đƣợc dùng cho bên trong các cụm và định tuyến
reactive dùng liên kết giữa các cụm.
Sơ đồ phân loại các kỹ thuật định tuyến đƣợc minh họa trong hình 4.5.