Đồ án tốt nghiệp Đại học Mục lục
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA VIỄN THÔNG I
o0o
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGHIÊN CỨU GIAO THỨC ĐỊNH TUYẾN
TRONG MẠNG HÌNH LƯỚI KHÔNG DÂY WMN

Sinh viên thực hiện : Phạm Quang Huy
Hà Nội 11 - 2008
i
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Mục lục
MỤC LỤC
THUẬT NGỮ VIẾT TẮT iv
DANH MỤC HÌNH VẼ v
LỜI NÓI ĐẦU vi
CHƯƠNG I: viii
GIỚI THIỆU CHUNG viii
1.1 Giới thiệu chung về MANET viii
1.2 Các giao thức định tuyến trong MANET ix
1.2.1 Các giải pháp định tuyến thông thường ix
1.2.2 Phân loại giao thức định tuyến trong MANET xi
1.3 Giới thiệu chung về mạng hình lưới không dây WMN xiii
1.4 Định tuyến trong mạng WMN xv
1.5 Tiêu chuẩn 802.11s xvi
1.5.1 Giới thiệu chung xvi
1.5.2 Tổng quan về IEEE 802.11s xvi
1.6 Định tuyến trong mạng hình lưới 802.11s xix
1.6.1 Phân loại các giao thức định tuyến MANET xix

tuyến xli
2.3.12 Sửa chữa nội vùng xlii
2.3.13 Các hoạt động sau khi khởi động lại xliv
2.3.14 Các giao diện mạng xliv
2.4 Kết luận chương xlv
CHƯƠNG III: xlv
GIAO THỨC ĐỊNH TUYẾN NGUỒN ĐỘNG DSR xlv
3.1 Tổng quan và tầm quan trọng của giao thức xlvi
3.2 Vấn đề cơ bản của cơ chế khám phá tuyến và duy trì tuyến
xlviii
3.2.1 Vấn đề cơ bản của khám phá tuyến xlviii
3.2.2 Vấn đề cơ bản của duy trì tuyến l
3.3 Định dạng mào đầu các lựa chọn DSR li
3.3.1 Sự phân chia cố định của mào đầu các lựa chọn DSR lii
3.3.2 Lựa chọn ROUTE REQUEST liv
3.3.3 Lựa chọn ROUTE REPLY lv
3.3.4 Lựa chọn ROUTE ERROR lvi
3.3.5 Lựa chọn Acknowledgement Request lviii
3.3.6 Lựa chọn Acknowledgment lviii
3.3.7 Lựa chọn tuyến nguồn DSR lix
3.3.8 Lựa chọn Pad1 lx
3.3.9 Lựa chọn PadN lxi
3.4 Hoạt động của DSR lxi
3.4.1 Quá trình xử lý gói tin thông thường lxi
3.4.2 Xử lý khám phá tuyến lxviii
3.4.3 Xử lý duy trì tuyến lxxvi
3.4.4 Hỗ trợ nhiều giao diện mạng lxxxiii
3.4.5 Sự phân mảnh và ghép lại IP lxxxv
3.5 Vị trí của chức năng định tuyến DSR trong mô hình tham khảo
của ISO lxxxvi

ISO International Organization for
Standardization
Tổ chức chuẩn hóa Quốc tế
LLACKS link-layer acknowledgments Báo nhận lớp liên kết
MAC Medium Access Control Điều khiển truy nhập môi
trường
MANET Mobile Ad-hoc Network Mạng tùy biến di động
MAP Mesh Access Point Điểm truy nhập hình lưới
MIC Metric of Interference and
Channel-switching
Tham số nhiễu và chuyển mạch
kênh
ML Minimum Loss Tổn thất tối thiểu
MP Mesh Point Điểm hình lưới
MPP Mesh Point Portal Điểm cổng mạng hình lưới
MPR Multi-Point Relay Trễ đa điểm
NGN Next Generation Network Mạng thế hệ kế tiếp
OLSR Optimized Link State Routing Định tuyến trạng thái liên kết
tối ưu
OSI Open Systems Interconnection Mô hình tham chiếu các hệ
thống mở OSI
RD Route Discovery Khám phá tuyến
RERR Route Error Lỗi tuyến
RM Route Maintenance Duy trì tuyến
RREP Route Reply Hồi đáp tuyến
RREP- ACK Route Reply Acknowledgment Báo nhận hồi đáp tuyến
RREQ Route Request Yêu cầu tuyến
iv
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ

lượng người sử dụng lớn, cung cấp đồng thời nhiều dịch vụ khác nhau trên cùng một
đường truyền không dây. Tuy nhiên, với các ứng dụng mạng có phạm vi vừa và nhỏ,
công nghệ WiMAX không phải là một giải pháp phù hợp do giá thành thiết bị đầu cuối
cao, chi phí thiết lập mạng lớn nên công nghệ WLAN (IEEE 802.11) vẫn là một giải
pháp hoàn toàn phù hợp về đặc điểm kỹ thuật cũng như chi phí sử dụng. Tuy nhiên, do
hạn chế về tầm phủ sóng, công nghệ WLAN truyền thống không thể đáp ứng được các
ứng dụng cần mở rộng mạng. Vì vậy, trên cơ sở các yếu tố công nghệ có sẵn của công
nghệ không dây chuẩn, yêu cầu đặt ra là phải xây dựng được giải pháp kết nối để tạo
ra mạng có phạm vi phủ sóng cao hơn nhưng vẫn đảm bảo được tính chất của mạng.
Mạng hình lưới không dây WMN (Wireless Mesh Network) có thể được coi là một
giải pháp tốt cho vấn đề đặt ra, nhằm mở rộng phạm vi phủ sóng cho các mạng WLAN
chuẩn. Dựa trên các thiết bị có sẵn của WLAN cùng với một số cải tiến về cả phần
cứng, phần mềm; xây dựng giao thức truyền thông mới, mạng WMN có thể cải thiện
đáng kể tầm phủ sóng của mạng ban đầu. Mạng WMN có khả năng tự hàn gắn, tự cấu
hình lại và tạo ra mạng có độ tin cậy cao; có thể hoạt động khi có một node bị lỗi hoặc
chất lượng kết nối mạng kém. Trong lĩnh vực mạng không dây, mạng lưới được áp
dụng để nới rộng phạm vi phủ sóng của mạng không dây truyền thống. Các node trong
mạng truyền thông trực tiếp với các node khác và tham gia trong mạng lưới. Nếu một
node có thể kết nối với một node lận cận khác thì sẽ có kết nối với toàn mạng.
Do tính chất của mạng WMN là bao gồm những phần tử cố định và những phần
tử di động (trong đó các phần tử cố định thì không phục thuộc chủ yếu vào nguồn pin,
nó có thể được coi như cơ sở hạ tầng của mạng) nên vấn đề định tuyến trong mạng
WMN rất được quan tâm. Các thuật toán định tuyến phải đảm bảo định tuyến hiệu quả
đối với cả thành phần cố định và thành phần di động, có thêm các tham số mới để
đánh giá hiệu suất mạng, tính ổn định, tốc độ định tuyến,… Định tuyến trong mạng
hình lưới không dây cũng chính là vấn đề được đề cập trong đồ án này. Đồ án nghiên
vi
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
cứu về giao thức định tuyến trong mạng hình lưới WMN và gồm có 3 chương, được

bộ nhớ lớn, dung lượng đĩa hàng trăm gigabyte, khả năng âm thanh đa phương tiện và
màn hình màu đã trở nên phổ biến trong đời sống hàng ngày và trong công việc. Đồng
thời, các yêu cầu kết nối mạng để sử dụng các thiết bị di động gia tăng đáng kể, bao
gồm việc hỗ trợ các sản phẩm mạng vô tuyến dựa trên vô tuyến hoặc hồng ngoại ngày
càng nhiều. Với kiểu thiết bị điện toán di động này, thì giữa những người sử dụng di
động luôn mong muốn có sự chia sẻ thông tin.
Một mạng tùy biến là một tập hợp các thiết bị di động hình thành nên một mạng
tạm thời mà không cần sự trợ giúp của bất kỳ sự quản lý tập trung hoặc các dịch vụ hỗ
trợ chuẩn nào thường có trên mạng diện rộng mà ở đó các thiết bị di động có thể kết
nối được. Các node được tự do di chuyển và thiết lập nó tùy ý, do đó, topo mạng
không dây có thể thay đổi một cách nhanh chóng và không thể dự báo. Nó có thể hoạt
động một mình hoặc có thể được kết nối tới Internet. MANET là một mạng có cơ sở
hạ tầng nhỏ do nó không yêu cầu bất cứ một cơ sở hạ tầng cố định nào (như một trạm
cơ sở) cho hoạt động của nó vì và vậy nó có thể được triển khai nhanh chóng và có
khả năng tự cấu hình. Các node truyền thông không dây và chia sẻ cùng phương tiện.
Do MANET là một mạng mềm dẻo mà có thể được thiết lập tại bất cứ đâu vào
bất cứ thời điểm nào mà không cần đến cơ sở hạ tầng hiện tại, bao gồm cả sự cấu hình
trước đó và người quản trị, mọi người có thể nhận ra tiềm năng thương mại và lợi thế
của mạng Ad hoc có thể mang lại. MANET có thể được dùng trong quân sự, trong các
mạng cảm biến, các hoạt động cứu hộ, sử dụng để truyền thông giữa các sinh viên
trong khu trường sở, trao đổi thông tin và dữ liệu trong các khu thương mại, tự do chia
sẻ kết nối Internet, dùng trong các buổi hội thảo…
MANET có hai chế độ hoạt động chính là chế độ cở sở hạ tầng và chế độ IEEE
Ad hoc.
Chế độ cơ sở hạ tầng: Chế độ này thì mạng bao gồm các điểm truy cập AP cố
định và các node di động tham gia vào mạng, thực hiện truyền thông qua các điểm
truy cập. Trong chế độ này thì các liên kết có thể thực hiện qua nhiều chặng.
viii
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ

tới toàn bộ các bộ định tuyến trong mạng. Với những thông tin chi phí mỗi liên kết
trong mạng, mỗi bộ định tuyến sẽ tính toán đường ngắn nhất tới từng đích có thể. Khi
đưa ra một gói để chuyển tiếp tới đích nào đó, mỗi bộ định tuyến chuyển tiếp gói tới
bộ định tuyến bước nhẩy tiếp theo dựa trên đường tối ưu nhất hiện nay tới đích. Các
giao thức định tuyến trạng thái liên kết hướng tới đích nhanh hơn khi các điều kiện
trong mạng thay đổi, nhưng nói chung đòi hỏi thời gian CPU nhiều hơn (để tính toán
đường ngắn nhất tới đích) và nhiều băng thông mạng hơn các thuật toán vectơ khoảng
cách.
Khi sử dụng các giao thức định tuyến thông thường trong một mạng tùy biến,
mỗi thiết bị di động được coi là một bộ định tuyến, có một số vấn đề với phương pháp
này:
- Truyền dẫn giữa 2 thiết bị di động qua một mạng vô tuyến không nhất thiết phải
tốt như nhau trên cả 2 hướng. Do đó một số tuyến được các giao thức định
tuyến truyền thống xác định có thể không hoạt động trong các môi trường như
vậy.
- Nhiều liên kết giữa các bộ định tuyến có được bởi thuật toán đinh tuyến có thể
dư thừa. Các mạng có dây thì ngược lại, thường được cấu hình chỉ có 1 hoặc
một số ít các bộ định tuyến để kết nối 2 mạng bất kỳ. Các đường dư thừa không
cần thiết trong môi trường vô tuyến làm tăng kích cỡ các cập nhật định tuyến
x
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
mà phải gửi qua mạng, và tăng phần phụ trội CPU để xử lý cập nhật và tính
toán tuyến mới.
- Việc định kỳ gửi các cập nhật định tuyến tiêu tốn băng thông mạng. Đôi khi,
không có thay đổi trong cập nhật định tuyến, nhưng mỗi bộ định tuyến (thiết bị
di động) vẫn phải tiếp tục gửi các cập nhật định kỳ để các bộ định tuyến khác sẽ
tiếp tục coi các tuyến qua bộ định tuyến đó là có hiệu lực. Các cập nhật định
tuyến từ các thiết bị ở ngoài phạm vi truyền dẫn của nhau sẽ không gây nhiễu
cho nhau, nhưng khi nhiều thiết bị di động là trong phạm vi truyền dẫn của

đường có thể được chia giao thức định tuyến thành các loại sau: reactive, proactive và
hybrid.
Hình 1.3: Phân loại giao thức định tuyến
Các giao thức định tuyến reactive là các giao thức được xây dựng dựa vào việc
tách riêng phát hiện đường (route discovery), duy trì đường (route maintenance) và
không cần cập nhật các đường theo chu kỳ. Các giao thức loại này sẽ yêu cầu thủ tục
quyết định đường khi cần thiết. Khi một node nguồn cần một đường đến đích, nó sẽ
thực hiện quá trình tìm đường trong mạng. Node nguồn phát quảng bá gói tin yêu cầu
tìm đường đi đến các node lân cận, các node lân cận này lại gửi gói tin đến các node
hàng xóm của nó, và gửi như vậy cho đến khi tới đích. Đích sẽ gửi gói tin phúc đáp
cho node nguồn thông qua các node trung gian. Khi đường đi được thiết lập, nó được
duy trì nhờ một thủ tục giữ đường cho đến khi đích không chấp nhận gói do nguồn gửi
đến hoặc không cần sử dụng đường đó nữa. Với phương pháp reactive, việc tính toán
tìm đường chỉ thực hiện khi cần thiết nên độ phức tạp tính toán giảm so với phương
pháp proactive nhưng lại bị trễ nhiều hơn do thủ tục thiết lập đường.
Các giao thức định tuyến proactive là các giao thức kết hợp việc phát hiện
đường đi và duy trì đường đi bằng cách gửi các gói cập nhật định tuyến. Nếu trạng thái
của một liên kết hoặc một router có sự thay đổi thì các gói tin cập nhật này sẽ thông
báo cho tất cả các router còn lại biết để tính toán lại đường đi. Do đó, mỗi node đều
biết đường đi đến các node còn lại. Như vậy sẽ không có trễ nhưng duy trì thường
xuyên các đường đi không sử dụng làm cho việc quản lý các đường phức tạp hơn.
xii
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
Các giao thức định tuyến hybrid được tạo ra để cố gắng kết hợp các ưu điểm
của 2 loại giao thức trên: sử dụng phương pháp định tuyến proactive với các node gần
hoặc cần dùng thường xuyên; sử dụng giao thức reactive với các node ở xa hoặc ít khi
cần truyền thông tin đến.
b. Định tuyến dựa vào vị trí
Đối với thuật toán định tuyến này, các gói được chuyển đi dựa vào vị trí địa lý

Các node hình lưới có thể có nhiều giao diện vô tuyến để gia tăng khả năng của
mạng hình lưới không dây. Các giao diện vô tuyến giảm thiểu sự suy giảm thông
lượng bởi các gói nhận và chuyển tiếp tuần tự trong các node hình lưới với chỉ một
giao diện vô tuyến. Điều này cũng có thể sử dụng nhiều kênh. Dung lượng tuỳ biến
của mạng WMN là giới hạn nhưng sự cài đặt đơn giản và tính mềm dẻo vẫn là những
ưu điểm của mạng.
Hình1.4: Các thành phần cơ bản của mạng WMN
Gần đây các thiết bị khách hàng ngày càng đóng vai trò như là một node hình
lưới. Điều này mở rộng mạng WMN về vùng mạng tuỳ biến không dây cổ điển. Điều
này không thành vấn đề, vì MANET và WMN có chung một khái niệm. Chúng chỉ sử
dụng các giá trị khác nhau trong các tham số mạng: các node với tính di động từ “tĩnh”
sang “chuyển động với tốc độ v” sử dụng truyền thông vô tuyến qua một hay nhiều
giao diện trên các chặng vô tuyến, nơi mà các tuyến được xác định rõ với các giao
thức định tuyến tự tổ chức làm việc với các tham số định tuyến khác nhau.
Có 3 kiểu mạng WMN, đó là : WMN hạ tầng, WMN khách hàng, và WMN lai
ghép. WMN hạ tầng bao gồm các thiết bị chuyên dụng của hạ tầng mạng, như là các
điểm truy nhập hay chuyển tiếp. Các thiết bị khách hàng không tham gia vào việc định
tuyến ở node lưới. Thay vào đó , chúng kết nối vào các điểm truy nhập bằng công
nghệ truy nhập vô tuyến truyền thống. WMN khách hàng bao gồm các thiết bị khách
hàng như máy tính xách tay. Các thiết bị khách hàng tham gia vào việc định tuyến ở
node lưới. Hơn nữa chúng có thể thực hiện chức năng như một thiết bị hạ tầng. WMN
lai ghép bao gồm cả hai loại thiết bị trên.
xiv
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
1.4 Định tuyến trong mạng WMN
Vì WMN có chung đặc điểm với những mạng tuỳ biến không dây, những giao
thức định tuyến được phát triển cho MANET có thể được ứng dụng vào WMN. Chẳng
hạn, những mạng hình lưới được Microsoft xây dựng dựa vào định tuyến nguồn động
(DSR), và nhiều công ty khác, sử dụng định tuyến vector cự ly theo yêu cầu tuỳ biến

Đồ án tốt nghiệp Đại học Danh mục hình vẽ
tự nhiên gây ra. Tương ứng là giao thức định tuyến cũng nên hỗ trợ chọn đường
lại tuỳ vào các liên kết lỗi.
- Cân bằng tải: Các bộ định tuyến vô tuyến cho mạng hình lưới tốt cho cân bằng
tải bởi vì chúng có thể lựa chọn đường đi hiệu quả nhất cho dữ liệu.
- Giảm thiểu tiêu đề định tuyến: Sự bảo vệ băng thông là bắt buộc cho sự thành
công của bất kì mạng vô tuyến nào. Giảm thiểu tiêu đề định tuyến là điều quan
trọng, đặc biệt bởi một nguyên nhân tái quảng bá.
- Khả năng mở rộng: Mạng hình lưới có khả năng mở rộng và có thể kiểm soát
hàng trăm hàng nghìn node. Bởi vì nhà điều hành mạng không phụ thuộc vào
một điểm điều khiển trung tâm, cộng thêm các điểm thu thập dữ liệu hoặc
gateway là rất tiện lợi. Điều quan trọng cho mạng WMN với hàng nghìn node
là hỗ trợ khả năng mở rộng trong các giao thức định tuyến.
- Hỗ trợ QoS: Để giới hạn dung lượng kênh, ảnh hưởng của xuyên nhiễu, số
lượng lớn các người dùng và sự nổi trội của các ứng dụng đa phương tiện thời
gian thực, việc hỗ trợ chất lượng dịch vụ (QoS) trở nên một yêu cầu quyết định
trong các mạng như vậy.
1.5 Tiêu chuẩn 802.11s
1.5.1 Giới thiệu chung
Các dịch vụ mạng không dây đang bùng nổ và trở thành một phần không thể
thiếu trong hệ thống dịch vụ mạng thế hệ kế tiếp NGN (Next generation Network).
Chính vì vậy, sự hình thành và phát triển mạnh mẽ của các công nghệ không dây mới
trong thời gian gần đây đã và đang thu hút nhiều sự quan tâm nghiên cứu của rất nhiều
các tổ chức nghiên cứu cũng như các trung tâm triển khai thử nghiệm. Trong nỗ lực
chuẩn hóa các hệ thống và tìm kiếm các giải pháp kết nối và nâng cao hiệu năng mạng,
tổ chức IEEE đã hình thành một số nhóm dành riêng để phát triển lĩnh vực WMN
(Wireless Mesh Network) như: IEEE 802.11s [Mạng không dây cục bộ WLAN],
802.15.5 [Mạng không dây cá nhân WPAN – Wireless Personal Area Network], IEEE
802.16j [Mạng không dây đô thị WMAN – Wireless Metropolital Network]. WMN có
thể được ứng dụng cho nhiều kiểu hạ tầng mạng không dây khác nhau và một trong số

Đồ án tốt nghiệp Đại học Danh mục hình vẽ
Hình 1.6: Kiến trúc các khối chức năng của 802.11s
- Khối chức năng định tuyến, chuyển tiếp và học cấu hình: Chứa các chức
năng phát hiện node lân cận, thu thập các tham số đo trạng thái đường liên kết
vô tuyến sử dụng cho định tuyến. Các giao thức định tuyến sử dụng địa chỉ
MAC làm địa chỉ nhận dạng cũng như cho chức năng chuyển tiếp gói. Để sử
dụng hiệu quả nguồn tài nguyên vô tuyến, giao thức định tuyến sử dụng các
tham số vô tuyến và các kênh đa tần phù hợp với các điều kiện vô tuyến để
chọn đường.
- Khối đo lường và tính toán: Chứa các chức năng tính toán các tham số vô
tuyến được sử dụng trong giao thức định tuyến; đo lường các điều kiện vô
tuyến để lựa chọn kênh tần số.
- Khối điều phối truy nhập phương tiện: Bao gồm các chức năng chống suy
giảm hiệu năng do các hiện tượng che dấu thông tin node (Hidden, Exposed
Node); các chức năng thực hiện điều khiển ưu tiên, điều khiển tắc nghẽn, điều
khiển quản lý và chức năng kích hoạt sử dụng lại tần số.
- Khối an ninh: Chứa các chức năng an ninh để bảo vệ các khung dữ liệu mang
trên WLAN và các khung quản lý được sử dụng bởi các chức năng quản lý như
giao thức định tuyến. Các phương pháp an ninh cho WLAN được định nghĩa
trong 802.11i.
- Khối liên mạng: IEEE 802.11 là một phần trong cấu trúc IEEE 802 vì thế
WLAN thực hiện kết nối với các mạng khác (ví dụ: 802.3) thông qua chức năng
cầu nối nằm tại MPP.
- Khối chức năng quản lý và cấu hình: Khối này gồm một giao diện WLAN sử
dụng để tự động thiết lập các tham số tần số vô tuyến MP với mục đích quản lý
chính sách chất lượng dịch vụ.
xviii
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
1.6 Định tuyến trong mạng hình lưới 802.11s

xix
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
1.6.2 Tham số đo lượng liên kết vô tuyến
Chất lượng dịch vụ của WLAN phụ thuộc lớn vào chất lượng các liên kết
không dây, độ xuyên nhiễu và tỉ lệ chiếm dụng tài nguyên vô tuyến. Để phản ánh các
điều kiện trên, 802.11s định nghĩa tham số đo lượng liên kết Airtime được sử dụng để
tính toán năng lực truyền dẫn giữa các cặp liên kết trong mạng hình lưới. Tham số này
mô tả số lượng nguồn tài nguyên kênh tiêu thụ bởi các khung truyền dẫn qua liên kết
cụ thể. Để sử dụng trong tính toán định tuyến, tham số đo lượng liên kết Airtime được
thể hiện qua tham số tính giá (cost). Tham số tính giá Ca được định nghĩa theo tốc độ
điều chế r và tỉ lệ bít lỗi ept cho một khung kiểm tra có kích thước Bt.
pt
t
PCQ Q
e -1
1
)
r
B
O O ( C ++=
Tiêu đề truy nhập kênh Oca, tiêu đề giao thức Op và kích thước khung kiểm tra Bt là
hằng số theo bảng 1.

Bảng 1: Các hằng số đo lượng liên kết Airtime
Tham số 802.11a 802.11b Mô tả
Oca 75 µs 335 µs Tiêu đề truy nhập kênh
Op 110 µs 364 µs Tiêu đề giao thức
Bt 8224 8224 Số lượng bit trong
khung

thập qua bản tin thăm dò node nguồn gửi đi từ node gốc xuống các node lá theo
phương thức quảng bá và phát lại quảng bá bản tin. Thông tin tuyến từ node
gốc tới bất kỳ node lá bất kỳ được thu thập qua bản tin đáp ứng tuyến RREP
hướng từ node lá tới node gốc. Các thông tin này được lưu trong bảng chuyển
tiếp để sử dụng như địa chỉ bước kế tiếp cho các gói tin đến node. Các bước
hoạt động cơ bản của giao thức định tuyến TBR được trình bày trên lược đồ tại
hình 1.7.
Bước 1: Lựa chọn MP trong mạng hình lưới làm gốc, thông thường là MPP.
Bước 2: Bản tin thông báo được phát chuyển quảng bá từ node gốc tới các node lá, các
node nhận thông tin thực hiện thiết lập đường dẫn tới node gốc và lựa chọn node cha
qua bản tin RREP hướng ngược.
Bước 3: MP duy trì đường dẫn bằng cách gửi bản tin RREQ tới node cha và nhận lại
bản tin RREP.
Bước 4: Khi nhận được node cha, MP đăng ký chính nó với node gốc bằng bản tin
RREP. Mỗi một node trung gian trên đường dẫn đều nhận được bản tin tương tự để
cập nhật vào bảng định tuyến.
xxi
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
Bước 5: Việc chuyển tiếp dữ liệu, duy trì cấu hình và tối ưu hóa được thực hiện tại
bước này. Dữ liệu được chuyển tiếp dọc theo đường dẫn tới node gốc qua các node
trung gian và chức năng duy trì cấu hình được thực hiện qua các bản tin RREQ được
gửi định kỳ.
Bước 6: Nếu một node MP thay đổi node cha bởi một node cha khả tuyển nằm trong
danh sách định tuyến, nó sẽ gửi bản tin đăng ký lại tới node gốc sau đó node gốc sẽ
gửi bản tin thông báo lỗi tới đường dẫn cũ. Nếu không có node cha khả tuyển trong
danh sách, thủ tục khởi tạo lại tuyến bắt đầu lại từ bước 1.

Hình 1.7: Các bước thủ tục chính của giao thức TBR
Như trên lược đồ đã chỉ ra, giao thức TBR luôn chỉ thiết lập duy nhất một

mạng hình lưới không dây WMN, tiêu chuẩn 802.11s, qua đó cung cấp những khái
niệm tổng quát nhất về các mạng này và tiêu chuẩn 802.11s. Cho thấy mạng hình lưới
không dây WMN là xu hướng phát triển của mạng không dây trong tương lai. Nó cung
cấp một giải pháp tối ưu cho mạng không dây, tận dụng cơ sở hạ tầng vốn có của
mạng WLAN, tạo nên một mạng hình lưới với tính ổn định cao hơn, phạm vi phủ sóng
lớn hơn, gia tăng khả năng họat động của mạng bằng cách hỗ trợ nhiều giao diện vật lý
khác nhau,
Chương I cũng đề cập tới các giao thức định tuyến có trong mạng tùy biến di
động MANET, mạng hình lưới không dây WMN và trong tiêu chuẩn 802.11s; trình
tổng quan về các giao thức trong các mạng này và trong tiêu chuẩn 802.11s, từ đó có
cái nhìn bao quát về các giao thức định tuyến trong các mạng không dây và có các
khái niệm ban đầu về các giao thức được nghiên cứu trong các chương sau.
xxiii
Phạm Quang Huy. D04VT2
Đồ án tốt nghiệp Đại học Danh mục hình vẽ
CHƯƠNG II:
GIAO THỨC ĐỊNH TUYẾN
VECTƠ CỰ LY THEO YÊU CẦU TÙY BIẾN AODV
2.1 Tổng quan về AODV
Yêu cầu cơ bản của thuật toán có thể được gọi là các hệ thống tiếp nhận đường
đi theo yêu cầu thuần túy; các node không nằm trên tuyến hoạt động thì không duy trì
bất kì thông tin định tuyến cũng như không tham gia vào bất kì bảng định tuyến nào.
Hơn nữa, một node không có gì để khám phá và duy trì tuyến tới node khác cho đến
khi hai node phải kết nối, trừ khi các node trước cung cấp các dịch vụ của mình như là
trạm trung chuyển để duy trì kết nối giữa hai node khác. Khi khu vực kết nối của node
di động được quan tâm, mỗi node di động có thể nhận biết được các node hàng xóm
nhờ việc sử dụng một số kĩ thuật, bao gồm quảng bá nội vùng ( không phải toàn hệ
thống) được biết đến như các bản tin Hello. Bảng định tuyến của các node lân cận
được tổ chức tối ưu hóa thời gian để đáp ứng nội vùng và cung cấp cho các yêu cầu
thành lập tuyến mới. Mục tiêu chính của thuật toán là:

Khi một node cần xác định tuyến tới một node đích, nó tạo ra sự tràn lụt các
bản tin RREQ trong mạng. Node khởi đầu này quảng bá một bản tin RREQ tới tất cả
các node lân cận, các node này lại tiếp tục quảng bá bản tin tới các hàng xóm của nó,
và cứ như vậy. Để ngăn chặn sự quay vòng chu kì, mỗi node nhớ việc chuyển tiếp
tuyến yêu cầu mới nhất trong một bộ nhớ đệm tuyến yêu cầu (route request buffer).
Khi các yêu cầu này trải rộng trong mạng, các node trung gian lưu giữ các tuyến
ngược quay lại node nguồn. Khi một node trung gian có nhiều tuyến ngược, nó luôn
luôn chọn các tuyến với giá trị hop count nhỏ nhất.
xxv
Phạm Quang Huy. D04VT2