Khóa luận Mạng Adhoc

huyết cũng chỉ có tối đa 3 kênh là kênh 1, kênh 6 và kênh 11 có thể được bố trí cùng nhau. Trong thực tế, vẫn có thể xảy ra trùng một phần nhỏ giữa các kênh. Điều này còn phụ thuộc vào thiết bị sử dụng và khoảng cách giữa các hệ thống. Hình 7: Các kênh không xung đột nhau khi ở cùng một khu vực Về khả năng chống nhiễu khi truyền dữ liệu thì so với FHSS, hệ thống DSSS chống nhiễu kém hơn do độ rộng dải tần nhỏ hơn (22 MHz so với 79 MHz) và dữ liệu của DSSS được truyền đồng thời trên toàn bộ băng tần thay vì truyền trên một băng tần trong một thời điểm của FHSS. 2.2.1.3. Kĩ thuật sử dụng hồng ngoại Trong kĩ thuật sử dụng hồng ngoại, bước sóng của ánh sáng nằm khoảng từ 850-900 nm. Nó có thể hoạt động trong môi trường có ánh sáng khuếch tán, và bán kính có thể thực hiện truyền thông giữa các thiết bị là 10m. Trong điều kiện có ánh sáng mạnh như ánh sáng mặt trời hay là ở những nơi phát nhiệt mạnh, kĩ thuật này không thể sử dụng được. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 22 2.2.2. Lớp điều khiển truy cập môi trường truyền MAC 2.2.2.1. Giao thức CSMA/CA Như chúng ta đã biết, CSMA/CD (Carrier Sense Multiple Access/Collision Detect) là cơ chế truy nhập đường truyền trong mạng LAN có dây và hoạt động rất hiệu. Trong mạng có dây, một máy tính muốn truyền một gói tin, nó sẽ lắng nghe xem đường truyền có bận không. Nếu đường truyền bận, nó sẽ tiếp tục lắng nghe cho đến khi đường truyền rỗi thì truyền gói tin đi với một xác suất nhất định. Đồng thời, trong lúc truyền, nó vẫn tiếp tục lắng nghe để đảm bảo không có xung đột xảy ra với gói tin đang truyền. Nếu xung đột được phát hiện trong quá trình truyền, máy sẽ tạm dừng truyền trong một khoảng thời gian nào đó, trước khi tiếp tục truyền gói tin bị xung đột. Như vậy theo cơ chế này, máy tính có thể phát hiện ra xung đột trong khi truyền dữ liệu. Nhưng với mạng không dây, do đặc điểm là truyền sóng trong không khí, nên điều này là không thể thực hiện được. Do đó, mạng không dây phải sử dụng giao thức CSMA/CA (Carier Sense Multiple Access/ Collision Avoidance), một giao thức có nhiều đặc điểm tương tự như giao thức của mạng LAN có dây. Để tránh xung đột, giao thức CSMA/CA có những quy tắc nghiêm ngặt hơn so với CSMA/CD. Khi một nút mạng trong mạng muốn truyền một gói tin, nó phải lắng nghe xem trong mạng có nút mạng nào đang thực hiện truyền tin hay không (cảm nhận sóng mang). Nếu môi trường mạng đang bị chiếm, nút mạng sẽ tính toán một khoảng trễ ngẫu nhiên để lặp lại việc nghe đường truyền. Ngay sau khoảng thời gian trễ đó, nút mạng lại lắng nghe xem môi trường mạng có rỗi hay không. Chính nhờ khoảng thời gian trễ đó mà nhiều nút mạng trong mạng sẽ không cố gắng truyền tin vào cũng một thời điểm. Đây chính là cách để mạng không dây tránh xung đột. Điểm khác biệt lớn nhất giữa hai giao thức này là CSMA/CA tránh xung đột (còn CSMA/CD phát hiện xung đột) và sử dụng gói tin ACK để xác nhận việc gửi gói tin thành công hay công. Nếu bên gửi nhận được gói tin ACK sau khi truyền một gói tin thì có nghĩa gói tin đã đến bên nhận thành công, ngược lại, nếu không nhận được gói tin ACK, bên gửi sẽ coi như là có tắc nghẽn và sẽ truyền lại gói tin. Bây giờ, chúng ta sẽ tìm hiểu các thành phần chính của giao thức CSMA/CA: • Cảm nhận sóng mang (carrier sense): Các nút mạng trong mạng không dây muốn truyền một gói tin phải kiểm tra xem đường truyền có bận hay không. Nếu bận phải trì hoãn việc truyền lại cho đến khi đường truyền rỗi. Các nút mạng xác định trạng thái của đường truyền dựa trên hai cơ chế: Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 23 9 Kiểm tra lớp vật lý xem có sóng mang hay không 9 Sử dụng chức năng carrier sense ảo là Network Allocation Vector (NAV) Một nút mạng có thể kiểm tra đường truyền có rỗi hay không nhờ việc kiểm tra lớp vật lý. Tuy nhiên, trong nhiều trường hợp, đường truyền có thể được đặt trước thông qua NAV. NAV thực ra một đồng hồ đếm giờ được cập nhật bởi các frame dữ liệu được gửi đi trong đường truyền. Ví dụ, trong một hệ thống mạng WLAN có cơ sở hạ tầng gồm 3 nút mạng là N1, N2 và N3. Giả sử N1 đang truyền một frame đến N2. Do đường truyền không dây là đường truyền chia sẻ dựa trên quảng bá nên N3 cũng có thể nhận được frame. Nhưng trong các frame của chuẩn 802.11 có chứa một trường là trường thời gian (Duration Field). Giá trị của trường này là đủ lớn để cho frame có thể truyền được đến đích và gói tin ACK có thể về được nơi gửi. Khi nhận được frame này, N3 sẽ cập nhật giá trị NAV của mình với giá trị của trường thời gian trong frame, và sẽ không thực hiện truyền ngay cho đến khi giá trị của duration trong frame là bằng 0. Một điểm cần lưu ý ở đây đó là các nút mạng chỉ cập nhật NAV của mình khi mà trường thời gian của frame lớn hơn giá trị NAV mà nút mạng đang lưu giữ. Ví dụ nếu N3 có NAV = 10mili giây thì N3 sẽ chỉ cập nhật NAV nếu duration của frame lớn hơn 10. Ngược lại, nó vẫn giữ nguyên giá trị của NAV. • Chức năng cộng phân tán (DCF-Distributed Coordination Function) IEEE xác định cơ chế truy nhập cho mạng 802.11 là DCF hoặc PCF. Cơ chế PCF dựa trên phương pháp truy nhập CSMA/CA. Trong cơ chế hoạt động của DCF, một nút mạng muốn truyền frame phải đợi một khoảng thời gian xác định sau khi đường truyền rỗi. Khoảng thời gian này được gọi là DIFS (DCF Interframe Space). Khi mà DIFS trôi qua, đường truyền đã có thể sẵn sàng cho các nút mạng truy nhập vào. Trong ví dụ trên, giả sử N2 và N3 muốn truyền frame sau khi N1 đã truyền xong. Mà N2 và N3 lại có cùng giá trị NAV, cả hai cũng thấy đường truyền rỗi. Lúc này khả năng xảy ra xung đột là rất lớn. Và để giải quyết vấn đề này, DCF sử dụng thuật toán Random Back-Off timer. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 24 Hình 8: Chức năng cộng phân tán DCF Thuật toán Random Back-Off sẽ chọn ngẫu nhiên một giá trị từ 0 đến giá trị của vùng cửa sổ tranh chấp (CW-Contention Window) – vùng màu hồng trong hình vẽ. Giá trị của CW có thể khác nhau, tùy theo mặc định của nhà sản xuất và nó được lưu trữ trong NIC (Network Interface Card) của nút mạng. Giá trị Random Back-off thực chất là khoảng thời gian mà máy trạm phải chờ thêm sau khi đường truyền rỗi và DIFS đã trôi qua. Giá trị của khoảng thời gian sẽ giảm đi 1 nếu sau mỗi khoảng thời gian DIFS, đường truyền vẫn rồi. Đến khi giá trị của nó giảm xuống còn 0, nút mạng bắt đầu truyền frame. Tuy nhiên, nếu có một nút mạng khác truy cập đường truyền trước khi giá trị Random Back-Off của nút mạng này giảm đến 0 thì nút mạng vẫn lưu giá trị đó lại (dừng đồng hồ) để sử dụng cho lần sau. Nút mạng nhận sau khi nhận được frame thành công sẽ gửi trở lại một frame biên nhận cho trạm truyền. Muốn làm được điều đó, trạm nhận cần phải chiếm được đường truyền. Để tránh khả năng frame ACK bị trì hoãn do phải giành đường truyền, frame ACK được phép bỏ qua quá trình Random Back-Off và chỉ phải đợi một khoảng thời gian ngắn được gọi là Short Interframe Space (SIFS) để có thể truyền. Giá trị của SIFS nhỏ hơn DIFS để đảm bảo nút mạng nhận có nhiều cơ hội chiếm được đường truyền để gửi biên nhận trước các nút mạng khác. • Vấn đề Hidden Terminal và việc sử dụng các gói tin RTS/CTS: Trong cơ chế CSMA/CA, chúng ta cần quan tâm đến vấn đề là hiện tượng cuối ẩn (hidden terminal) và trạm cuối lộ (exposed terminal). Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 25 9 Hiện tượng đầu cuối ẩn: Hình 9: Hiện tượng đầu cuối ẩn Hiện tượng này có thể được mô tả như sau: nút mạng B nằm trong vùng phủ sóng của hai nút mạng A và C. Hai nút mạng A và nút mạng C lại không nằm trong vùng phủ sóng của nhau. Nút mạng A đang truyền một gói dữ liệu cho B. C cảm nhận kênh truyền và do C nằm ngoài vùng phủ sóng của A nên C không cảm nhận được sóng mang của A. Do đó, C cũng truyền dữ liệu cho B, dẫn đến tại B xảy ra xung đột. 9 Hiện tượng trạm cuối lộ: Hình 10: Hiện tượng trạm cuối lộ Mô tả hiện tượng: Nút mạng B đang truyền dữ liệu cho nút mạng A. Cùng lúc đó, nút mạng C cũng muốn truyễn dữ liệu cho nút mạng D nhưng nút mạng C cảm nhận sóng mang thấy đường truyền đang bận nên không truyền nữa, trong khi nó hoàn toàn có thể truyền cho nút mạng D. 9 Chức năng cộng tác phân tán sử dụng gói tin điều khiển RTS/CTS: Gói tin RTS chứa địa chỉ nút mạng nhận và khoảng thời gian cần thiết cho quá trình truyền dữ liệu (bao gồm thời gian truyền toàn bộ dữ liệu và thời gian gói tin biên nhận của nút mạng nhận gửi lại). Khi nhận được gói tin RTS, nút mạng nhận sẽ gửi trả lại gói tin CTS sau khoảng thời gian SIFS. Khi nút mạng gửi nhận được gói CTS, nó bắt đầu truyền dữ liệu cho nút mạng nhận sau khoảng thời gian chờ SIFS và chờ nút mạng nhận gửi trả về gói ACK xác nhận đã gửi thành công. Sau khi nhận gói ACK, nút mạng sẽ giải phóng NAV để bắt đầu một chu kì mới. Sử dụng các gói tin RTS/CTS, vấn đề hidden terminal và exposed terminal có thể được khắc phục. Với hiện tượng đầu cuối ẩn, khi A truyền quảng bá gói tin RTS cho B, do C nằm ngoài vùng phủ sóng của A nên không cảm nhận được sóng mang, cho rằng Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 26 đường truyền rỗi. Khi nhận được gói tin RTS từ A, B sẽ gửi phản hồi lại gói CTS. Lúc này, C do nằm trong vùng phủ sóng của B nên có thể cảm nhận được đường truyền bận, do đó sẽ không truyền dữ liệu nữa. Hình 11:Cơ chế RTS/CTS giải quyết vấn đề trạm cuối ẩn. Với hiện tượng tạm cuối lộ, khi B truyền gói tin RTS cho A, C cảm nhận được đường truyền đang bận nên hoãn lại không truyền dữ liệu cho D. Nhưng sau khi A phản hồi lại gói tin CTS cho B, do C nằm ngoài vùng phủ sóng của A nên C sẽ không nhận được quảng bá gói tin CTS của A phát đi. Vì thế, C có thể nghĩ rằng A đã ngoài vũng phủ sóng và có thể truyền dữ liệu cho D một cách bình thường. Hình 12:Cơ chế RTS/CTS giải quyết vấn đề trạm cuối lộ. • Chức năng điều khiển tập trung (Point Coordination Function - PCF) PCF là một cơ chế truy cập tùy chọn (ngoài DCF) của chuẩn 802.11. Nó cung cấp khả năng phân phát các frame đến và đi từ AP mà không cần phải cạnh tranh giành đường truyền (Contention Free).Cơ chế hoạt động của PCF cần phải có một điểm truy cập (Access Point) nên không được áp dụng được cho mạng adhoc. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 27 Hình 13: PCF sử dụng việc hỏi vòng Trong PCF, thời gian được chia thành các khoảng được gọi là các superframe, được bắt đầu với các frame dẫn đường (beacon frame). Mỗi superframe được chia thành hai phần là khoảng không tranh chấp (Contention-free period) và khoảng tranh chấp (Contention Period). Ở đây, AP đóng vai trò của một bộ điều phối trung tâm (Point Coordinator), quyết định trạm nào phải chờ khoảng thời gian PIFS để truy cập môi trường truyền. PIFS là khoảng thời gian được sử dụng trong các dịch vụ giới hạn thời gian, có giá trị lớn hơn SIFS nhưng nhỏ hơn DIFS. Điều này cho phép các trạm PCF có thể truy nhập đường truyền trước các trạm DCF nhưng vẫn đảm bảo cho các frame điều khiển như ACK frame có cơ hội giành lấy đường truyền. Nhìn trên hình vẽ, ở thời điểm t0, khoảng không tranh chấp được bắt đầu. Tuy nhiên, do đường truyền mạng đang bận, AP không truy cập môi trường truyền. Đến thời điểm t1, khi đường truyền mạng rỗi, AP phải chờ một một khoảng thời gian PIFS nữa mới bắt đầu truy cập vào môi trường truyền. Lúc này, có hai khả năng xảy ra: nếu trạm nhận được dữ liệu D từ AP gửi xuống và muốn truyền dữ liệu, nó sẽ gửi lại cho AP dữ liệu cần gửi U. Ngược lại, nếu trạm nhận không muốn gửi dữ liệu, sau khoảng thời gian SIFS, AP sẽ không nhận được dữ liệu nào từ trạm đó. Trong hình, có 4 trạm không dây. Ban đầu, AP cho phép trạm 1 truyền dữ liệu bằng cách gửi cho trạm 1 gói dữ liệu D1, sau khoảng thời gian SIFS, AP nhận được gói U1 từ trạm 1 do trạm 1 cũng muốn truyền dữ liệu. Sau khi nhận được dữ liệu từ trạm 1, chờ thêm khoảng thời gian SIFS nữa, AP chỉ định trạm 2 truyền dữ liệu. Trạm 2 cũng muốn truyền dữ liệu nên truyền trở lại cho AP gói U2. Sau đó AP lại chỉ định cho trạm 3 truyền dữ liệu. Nhưng Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 28 trạm 3 không muốn truyền dữ liệu nên AP không nhận được dữ liệu từ trạm 3.Sau khoảng thời gian PIFS, AP lại cho phép trạm 4 truyền dữ liệu. Trạm 4 cũng muốn gửi dữ liệu nên gửi lại cho AP gói U4. Khi mà khoảng thời gian không tranh chấp sắp hết, AP sử dụng tín hiệu Cfend (Contention Free end). Ta có thể thấy, tại mỗi thời điểm chỉ có một trạm được truy cập môi trường truyền, nó có thể gửi hoặc không gửi dữ liệu. Các trạm có khoảng thời gian truy cập môi trường truyền riêng, không trùng nhau và do AP chỉ định. Do đó, trong khoảng thời gian không tranh chấp, không có xung đột xảy ra. 2.2.3. Lớp quản lý tầng MAC Lớp quản lý tầng MAC đóng vai trò trung tâm trong các trạm IEEE 802.11. Nó cung cấp một vài chức năng như Đồng bộ hóa (Synchronization), Quản lý năng lượng (Power Management) và Quản lý chuyển vùng (Roaming). 2.2.3.1. Đồng bộ hóa (Synchronization) Đồng bộ hóa có vai trò quan trọng trong các chức năng của tầng liên kết dữ liệu như chức năng quản lý năng lượng, chức năng cộng tác trong kĩ thuật PCF và chức năng đồng bộ nhảy tần trong các hệ thống tầng vật lý sử dụng kỹ thuật FHSS. Việc đồng bộ thời gian giữa các trạm trong một BS được thực hiện bằng việc gửi một gói tin beacon chứa nhãn thời gian và thông tin quản lý khác. Nhãn thời gian trong gói tin Beacon giúp các trạm điều chỉnh lại đồng hồ của mình. Theo thời gian, đồng hồ nội bộ này có thể thay đổi, do đó cứ sau một khoảng thời gian nhất định, các trạm lại phải điều chỉnh lại đồng hồ của mình. Khoảng thời gian đó gọi là beacon interval. Đối với mạng có cơ sở hạ tầng, trạm truy cập cơ sở đảm nhận việc đồng bộ hóa bằng cách phát gói tin beacon theo định kì để mọi trạm trong một BS điều chỉnh lại đồng hồ nội bộ của mình. Đối với mạng adhoc, điều này có phần phức tạp hơn do mạng không có trạm truy cập cơ sở để thực hiện việc đồng bộ. Mỗi nút mạng trong mạng sẽ phát đi gói tin beacon sau mỗi khoảng beacon. Và để tránh xung đột, các thuật toán back off chuẩn được áp dụng để làm giảm khả năng đụng độ, đảm bảo một nút mạng có thể gửi được gói tin beacon và các nút mạng khác đồng bộ thời gian theo gói đó. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 29 2.2.3.2. Quản lý năng lượng (Power Management) Các thiết bị không dây sử dụng pin là nguồn cung cấp năng lượng. Do đó, việc quản lý năng lượng nhằm tiết kiệm, tránh lãng phí đóng vai trò quan trọng trong việc kéo dài thời gian làm việc của thiết bị, tiện lợi cho người dùng. Để tiết kiệm năng lượng, IEEE 802.11 đưa ra ý tưởng thiết lập hai trạng thái cho một trạm: trạng thái “nghỉ” và trạng thái “làm việc”. Quá trình quản lý năng lượng của mạng không dây có cơ sở hạ tầng đơn giản hơn mạng adhoc nhiều. Trạm truy cập cơ sở có nhiệm vụ lưu lại mọi frame cho các trạm sử dụng cơ chế tiết kiệm năng lượng trong mạng nó quản lý. Khi đó, trạm truy cập cơ sở sẽ gửi một gói tin beacon trong đó có chứa ánh xạ định danh truyền thông (Traffic map Indication Map – TIM) gồm danh sách các trạm có dữ liệu cần gửi đến. Chức năng đồng bộ thời gian đảm bảo các trạm đều phải “thức” để nhận gói tin này. Đồng thời đối chiếu xem mình có tên trong ánh xạ định danh truyền thông không. Nếu có tồn tại, nó sẽ giữ nguyên trạng thái “thức” và thực hiện quá trình nhận dữ liệu. Ngược lại, trạm sẽ trở lại trạng thái “nghỉ” và chờ gói beacon kế tiếp. Đối với mạng adhoc, do không có trạm truy cập cơ sở nên các nút mạng phải tự lưu lại dữ liệu mình muốn gửi và gửi định danh của trạm cần gửi dữ liệu đến các trạm xung quanh trong giai đoạn nó thức nhờ sử dụng ánh xạ định danh truyền thông adhoc (Adhoc Traffic Indication Map – ATIM). 2.2.3.3. Quản lý chuyển vùng (hand-off) Trong một khu vực lớn, mạng không dây cần lắp nhiều trạm truy cập cơ sở để có thể mở rộng vùng phủ sóng, giúp người sử dụng có thể truy cập tại bất kì điểm nào trong khu vực đó. Khi một thiết bị không dây di chuyển giữa các điểm trong khu vực, cần có một cơ chế quản lý việc chuyển vùng để đảm bảo tính truyền thông của thiết bị không bị gián đoạn. Việc chuyển vùng này được thực hiện theo các bước: - Một trạm nhận thấy tín hiệu liên kết giữa mình với trạm truy cập cơ sở là quá yếu (tín hiệu quá yếu), nó sẽ tìm kiếm một trạm cơ sở khác cung cấp dịch vụ với một liên kết tốt hơn. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 30 - Trong quá trình quét tín hiệu mạng được chia làm hai dạng là quét chủ động và quét bị động. Quét chủ động là máy trạm trực tiếp phát đi một gói tin tín hiệu đến mỗi kênh truyền và chờ đợi phản hồi từ các kênh truyền đó. Quét thụ động là máy trạm nghe môi trường truyền để tìm ra một BS mới. - Sau khi nhận được tín hiệu phản hồi, trạm cần chuyển vùng sẽ chọn máy trạm cơ sở cung cấp dịch vụ liên kết tốt nhất đến nó và gửi một yêu cầu cung cấp dịch vụ. - Trạm truy cập cơ sở sẽ trả lời yêu cầu của máy trạm chuyển vùng. Nếu chấp nhận thì máy trạm chuyển vùng sẽ gia nhập một BS mới. Ngược lại, nó sẽ phải quét lại để tìm một máy trạm cơ sở mới chấp nhận cho nó tham gia vào BS mới. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 31 Chương 3: Định tuyến trong mạng adhoc 3.1. Giới thiệu về thuật toán định tuyến Trong một hệ thống mạng, một trong những yếu tố ảnh hưởng lớn nhất đến hiệu suất của mạng đó là thời gian truyền các gói tin từ điểm đầu đến điểm cuối sao cho nhanh và chính xác nhất. Để đạt được điều đó thì tầng mạng có nhiệm vụ là tìm đường đi, xác định các router trung gian để chuyển gói tin từ điểm đầu đến điểm cuối. Các thuật toán giúp xác định đường đi như vậy gọi là thuật toán định tuyến. Như vậy chức năng của thuật toán định tuyến chính là xác định đường đi tốt nhất cho gói tin từ bên gửi đến bên nhận. Đối với mạng không dây có cơ sở hạ tầng, việc truyền thông giữa các nút mạng trong mạng phụ thuộc rất nhiều vào base station. Các nút mạng muốn liên lạc với nhau đều phải nằm trong vùng phủ sóng của base station (nếu một nút mạng mà nằm ngoài vùng phủ sóng của base station thì nó không thể nào liên lạc được với các nút mạng khác). Nhưng với mạng adhoc thì lại khác. Các nút mạng dù nằm ngoài vùng phủ sóng của nhau vẫn có thể liên lạc được với nhau thông qua các nút mạng trung gian. Do đó, việc tìm ra các nút mạng trung gian để truyền gói tin giữa nút mạng đầu và nút mạng cuối là rất quan trọng. Ngoài ra, một số đặc điểm khác biệt của mạng adhoc so với các mạng khác như các nút mạng có thể di động, dẫn đến topo mạng thay đổi theo; băng thông của mạng cũng thay đổi liên tục, tốc độ truyền tín hiệu của mạng phụ thuộc nhiều vào tính chất vật lý của các nút mạng và giao diện mạng, ... Chính những đặc điểm này làm cho việc thiết kế các giao thức định tuyến cho mạng adhoc là một bài toán khó. 3.2.Yêu cầu của thuật toán định tuyến cho mạng không dây adhoc Như đã trình bày ở trên, do các đặc điểm khác biệt của mạng adhoc, chúng ta không thể áp dụng các thuật toán định tuyến truyền thống như Trạng thái liên kết (Link State) hay Vector khoảng cách (Distance Vector) cho mạng adhoc được. Cả hai thuật toán này đều yêu cầu các router quảng bá thông tin định tuyến theo kiểu định kì. Những hoạt động này hạn chế khả năng thích ứng của giao thức với các thay đổi của topo mạng. Nếu khoảng thời gian định kỳ khá ngắn, giao thức sẽ hoạt động không hiệu quả bởi nó phải làm việc nhiều hơn so với sự thay đổi của topo mạng và gây lãng phí băng thông và năng lượng của các nút mạng một cách không cần thiết. Còn nếu thời gian định kì quá dài, giao thức sẽ không phản ứng kịp với sự thay đổi của topo mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 32 Với thuật toán Link State, các router sẽ gửi thông tin quảng bá định kì về các hàng xóm và giá của đường đi tới các hàng xóm đến tất cả các router trong mạng. Từ đó, các router sẽ biết được toàn bộ topo của mạng để tính toán đường đi tới đích ngắn nhất có thể. Còn với thuật toán Distance Vector, mỗi router lại gửi định kì các thông tin khoảng cách từ nó đến các router khác. Bằng việc tính toán, so sánh khoảng cách từ mỗi hàng xóm đến một đích nào đó, các router sẽ quyết định tuyến đường đi ngắn nhất đến nút mạng đích. Như vậy, nếu sử dụng các thuật toán thông thường với mạng adhoc có thể dẫn đến một loạt các vấn đề sau: - Đặc điểm đầu tiên của các thuật toán định tuyến thông thường đã không phù hợp với mạng adhoc. Đó là việc các router liên tục gửi quảng bá định kì đến các nút mạng trong mạng. Việc gửi quảng bá định tuyến định kì gây ra hai vấn đề sau: o Thứ nhất, nó sẽ gây lãng phí băng thông cho các nút mạng trong mạng adhoc. Có những khi không có sự thay đổi nào trong mạng nhưng các router tiếp tục gửi các cập nhật thông tin định tuyến theo định kì làm các nút mạng phải tính toán lại các tuyến đường. Nếu trong vùng phủ sóng của một nút mạng có quá nhiều nút mạng khác thì nút mạng này phải nhận rất nhiều thông tin cập nhật định tuyến. Điều này gây lãng phí băng thông một cách không cần thiết. o Thứ hai, việc gửi các cập nhật định tuyến theo định kì cũng gây lãng phí năng lượng không cần thiết cho các nút mạng trong mạng. Chúng ta đã biết năng lượng của các nút mạng trong mạng adhoc chủ yếu là pin. Việc sử dụng năng lượng một cách tiết kiệm và hợp lý là rất cần thiết. Nếu các nút mạng phải gửi quảng bá định tuyến theo định kì sẽ tốn rất nhiều năng lượng, bởi năng lượng để gửi một gói tin không phải là nhỏ. Bên cạnh đó, việc nhận một gói tin tốn ít năng lượng nhưng việc phải cập nhật, tính toán các tuyến đường lại cản trở việc tiết kiệm năng lượng của các nút mạng. - Ở các mạng thông thường, liên kết giữa hai nút mạng trong mạng hoặc giữa nút mạng với base station là các liên kết đối xứng. Trong khi đó, liên kết giữa hai nút mạng của mạng adhoc có thể là liên kết không đối xứng, nghĩa là việc truyền thông giữa hai nút mạng không thể thực hiện tốt trên cả hai hướng. Lý do là vì khả năng truyền tín hiệu của các nút mạng là khác nhau: nút mạng nào có năng lượng truyền tín hiệu mạnh thì nút mạng đó có liên kết tốt với các nút mạng nhận tín hiệu của nó, Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 33 ngược lại, nút mạng có năng lượng truyền tín hiệu yếu thì khả năng không liên kết được với các nút mạng nhận tín hiệu là khó tránh khỏi, nếu có liên kết được thì đó cũng chỉ là những liên kết yếu, không ổn định. Do đó, giao thức định tuyến thông thường không thể hoạt động trong môi trường mạng như vậy. - Một đặc điểm nữa của mạng adhoc làm chúng ta không thể áp dụng được các thuật toán định tuyến thông thường cho nó. Đó là trong mạng adhoc tồn tại nhiều liên kết dư thừa. Với mạng có dây truyền thống, người ta thường chỉ dùng rất ít các router để nối hai mạng với nhau. Vì thế các tuyến đường dư thừa trong mạng có dây là không nhiều và các thuật toán định tuyến thông thường vẫn tính đến cả những liên kết đó. Nhưng với mạng adhoc lại khác. Mỗi nút mạng lại đóng vai trò như một router, mạng adhoc có bao nhiêu nút mạng thì có bấy nhiêu router. Điều này làm cho việc truyền dữ liệu từ nút mạng nguồn đến nút mạng đích có thể phải đi qua nhiều hơn một nút mạng trung gian, và tuyến đường mà dữ liệu di chuyển cũng không phải là duy nhất. Bên cạnh tuyến đường tốt nhất vẫn có thể tồn tại nhiều tuyến đường khác có thể hoạt động bình thường. Với mạng có quá nhiều tuyến đường dư thừa như vậy, các thuật toán định tuyến nếu tính cả đến chúng sẽ làm cho việc cập nhật và tính toán tuyến đường trở lên nhiều hơn. Điều đó là không cần thiết. - Một vấn đề cuối cùng quan trọng hơn cả, đó là các thuật toán đó không được thiết kế dành cho mạng có topo động như của mạng adhoc. Với mạng có dây truyền thống, liên kết giữa các router gần như là không đổi, giá (chất lượng) của một liên kết có thể thay đổi do tắc nghẽn chứ vị trí của các router là cố định trong cấu trúc mạng. Nhưng trong mạng adhoc, điều đó lại không hề có. Với những vấn đề nêu ra ở trên, chúng ta có thể rút ra được một số yêu cầu với các thuật toán định tuyến cho mạng adhoc: - Thuật toán phải được thiết kế sao cho phù hợp với tính động của topo mạng và các liên kết bất đối xứng. - Hoạt động phân tán: cách tiếp cận tập trung cho mạng adhoc sẽ thất bại do sẽ tốn rất nhiều thời gian để tập hợp các thông tin trạng thái hiện tại của mạng để tính toán rồi lại phát tán lại nó cho các nút mạng. Trong thời gian đó, cấu hình mạng có thể đã thay đổi rất nhiều. - Tính toán đến vấn đề năng lượng và băng thông của mạng: Do các nút mạng có nguồn năng lượng hạn chế nên cần phải tính toán đến vấn đề tiết kiệm năng lượng. Giao thức đị