Mục Lục
Nội dung khóa luận. 1
Danh sách các từviết tắt. 5
Chương 1: Giới thiệu chung. 7
1.1. Đặt vấn đề. 7
1.1.1. Khái niệm vềWLAN[1],[3],[6]
. 7
1.1.2. Lịch sửra đời mạng WLAN. 8
1.1.3. Một số ưu và nhược điểm của WLAN. 8
1.2. Mạng adhoc.10
1.2.1. Khái niệm và một số đặc điểm chung của mạng adhoc.10
1.2.2. Ví dụvềmạng adhoc.11
1.2.3. Các ứng dụng của mạng adhoc.12
1.2.4. Một sốvấn đềcần quan tâm trong mạng adhoc.13
1.3. Mục tiêu của luận văn.14
Chương 2: Mạng LAN không dây.15
2.1. Mạng WLAN theo chuẩn 802.11
[1], [2],[6]
.15
2.1.1. Mạng WLAN có cơsởhạtầng.15
2.1.2. Mạng adhoc.16
2.2. Kiến trúc giao thức mạng WLAN theo chuẩn 802.11.17
2.2.1. Lớp Vật Lý.18
2.2.2. Lớp điều khiển truy cập môi trường truyền MAC.22
2.2.3. Lớp quản lý tầng MAC.28
Chương 3: Định tuyến trong mạng adhoc.31
3.1. Giới thiệu vềthuật toán định tuyến.31
3.2. Yêu cầu của thuật toán định tuyến cho mạng không dây adhoc.31
3.3. Phân loại các thuật toán định tuyến cho mạng adhoc.35
3.3.1. DSDV (Destination Sequence Distance Vector).35
Mạng Adhoc, Khóa luận tốt nghiệp Cửnhân CNTT, Ngô Hải Sơn, 2008
4
3.3.2. AODV (Adhoc On-Demand Distance Vector Routing).37
3.3.3. DSR (Dynamic Source Routing).38
3.3.4. TORA (Temporally Ordered Routing Algorithm).40
Chương 4: Đánh giá hiệu suất các giao thức định tuyến bằng bộmô phỏng mạng NS2.42
4.1. Giới thiệu bộmô phỏng NS2
[4],[5]
.42
4.2. Khảnăng mô phỏng các mạng của NS2.43
4.3. Mô phỏng mạng adhoc và các giao thức định tuyến trong mạng adhoc.43
4.3.1. Mô phỏng mạng adhoc.43
4.3.2. Mô phỏng các giao thức định tuyến trong mạng adhoc
[1, T.Việt], [4], [5]
.45
4.4. Phân tích và so sánh hiệu suất của các giao thức định tuyến trong mạng adhoc.48
4.4.1. Các tham sốcủa môi trường:.48
4.4.2. Các thông số đánh giá hiệu suất:.49
4.4.3. Các thí nghiệm mô phỏng
[1, T.Việt]
.49
4.4.4. Nhận xét vềhiệu suất của các giao thức định tuyến.52
Kết luận.54
PhụLục.55
Tài liệu tham khảo . 61
61 trang |
Chia sẻ: netpro | Lượt xem: 4099 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Khóa luận Mạng Adhoc, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 đị
Các file đính kèm theo tài liệu này:
- Mạng adhoc và các giao thức định tuyến phổ biến của mạng adhoc.pdf