Giao thức quản lý topology trong mạng không dây ngang hàng

bé gi¸o dôc vµ ®µo t¹o

TR¦êNG §¹I HäC b¸ch khoa Hµ Néi

[ \

Phïng minh qu©n

giao thøc qu¶n lý topology

trong m¹ng kh«ng d©y ngang hµng

LuËn v¨n th¹c sÜ khoa häc

Chuyªn ngµnh: C«ng nghÖ th«ng tin

Hµ Néi - 2008

phïng minh qu©n

 C¤NG NGHÖ TH¤NG TIN

 KHãA 2006 - 2008

bé gi¸o dôc vµ ®µo t¹o

TR¦êNG §¹I HäC b¸ch khoa Hµ Néi

[ \

Phïng minh qu©n

giao thøc qu¶n lý topology

trong m¹ng kh«ng d©y ngang hµng

Chuyªn ngµnh: C«ng nghÖ th«ng tin

LuËn v¨n th¹c sÜ khoa häc

Ng−êi h−íng dÉn khoa häc:

ts. vò tuyÕt trinh

Hµ Néi - 2008

Giao thức quản lý topology trong mạng không dây ngang hàng

Phùng Minh Quân - Luận văn cao học

NHỮNG LỜI ĐẦU TIÊN

Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân

thành và sâu sắc nhất tới cô giáo, tiến sĩ Vũ Tuyết Trinh - người đã tận tình

hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho

tới khi hoàn thành công việc của mình.

Đồng thời, xin trân trọng gửi lời cảm ơn tới tập thể các thầy cô giáo

Khoa Công nghệ Thông tin - Đại học Bách Khoa Hà Nội đã tận tình giảng

dạy và tạo cho tôi một môi trường học tập nghiên cứu đầy đủ và thuận tiện

trong suốt 2 năm học vừa qua.

Xin cảm ơn tất cả những người thân yêu trong gia đình tôi cùng toàn thể

bạn bè, những người đã luôn mỉm cười và động viên tôi mỗi khi vấp phải

những khó khăn, bế tắc.

Cuối cùng, xin chân thành cảm ơn tiến sĩ Phùng Minh Hoàng (School of

Computing and Communications - Faculty of Engineering and IT - University

of Technology, Sydney), thạc sĩ Vũ Bội Hằng (Ngân hàng Công Thương Việt

Nam), những người đã đem đến cho tôi những lời khuyên vô cùng bổ ích để

giúp tháo gỡ những khó khăn, vướng mắc trong quá trình làm luận văn.

Giao thức quản lý topology trong mạng không dây ngang hàng

Phùng Minh Quân - Luận văn cao học

MỤC LỤC

DANH MỤC HÌNH VẼ

DANH MỤC BẢNG BIỂU

MỞ ĐẦU.............................................................................................................................1

CHƯƠNG 1 - TỔNG QUAN ............................................................................................4

1.1. Mạng P2P .................................................................................................................4

1.1.1. Mạng P2P có dây ...............................................................................................4

1.1.2. Mạng P2P không dây – Mạng tùy biến không dây............................................6

1.2. Bài toán quản lý topology cho mạng không dây P2P...............................................8

1.2.1. Phát biểu bài toán...............................................................................................8

1.2.2. Các phương pháp tiếp cận bài toán quản lý topology cho mạng không dây

tùy biến........................................................................................................................9

1.2.3. Vị trí của giao thức quản lý topology trong tầng giao thức của mạng tùy biến10

CHƯƠNG 2 - QUẢN LÝ KẾT NỐI CỦA CÁC NÚT MẠNG LÂN CẬN.................14

2.1. Giới thiệu ................................................................................................................14

2.2. Mô hình hóa hệ thống.............................................................................................14

2.3. Một số thuật toán ....................................................................................................16

2.3.1. Thuật toán dựa trên tính công bằng .................................................................17

2.3.2. Thuật toán dựa trên tính phổ biến của các file.................................................20

2.3.3. Thuật toán dựa trên mức năng lượng của các nút mạng..................................24

2.4. Vấn đề triển khai các thuật toán .............................................................................27

2.5. Khuyến nghị về việc sử dụng các thuật toán ..........................................................28

CHƯƠNG 3 - QUẢN LÝ VIỆC BẬT TẮT NÚT MẠNG............................................30

3.1. Giới thiệu ................................................................................................................30

3.2. Phân loại .................................................................................................................31

3.3. Một số giao thức bật tắt không đồng bộ .................................................................32

3.3.1. Giao thức RAW ...............................................................................................32

3.3.2. Giao thức AWP................................................................................................40

3.3.3. Giao thức CAW ...............................................................................................43

Giao thức quản lý topology trong mạng không dây ngang hàng

Phùng Minh Quân - Luận văn cao học

3.4. Khuyến nghị về việc sử dụng các giao thức ...........................................................53

CHƯƠNG 4 - MỘT SỐ ỨNG DỤNG............................................................................55

4.1. Giới thiệu ................................................................................................................55

4.2. Ứng dụng trong khắc phục thảm họa......................................................................55

4.2.1. Yêu cầu ............................................................................................................55

4.2.2. Giải pháp..........................................................................................................56

4.2.3. Lựa chọn giao thức quản lý topology ..............................................................57

4.3. Ứng dụng trong giám sát và theo dõi .....................................................................59

4.3.1. Yêu cầu ............................................................................................................59

4.3.2. Giải pháp..........................................................................................................59

4.3.3. Lựa chọn giao thức quản lý topology ..............................................................60

4.4. Ứng dụng trong chia sẻ file tại các khu vực đông người........................................61

4.4.1. Yêu cầu ............................................................................................................61

4.4.2. Giải pháp..........................................................................................................61

4.4.3. Lựa chọn giao thức quản lý topology ..............................................................62

KẾT LUẬN.......................................................................................................................63

TÀI LIỆU THAM KHẢO...............................................................................................64

Giao thức quản lý topology trong mạng không dây ngang hàng

Phùng Minh Quân - Luận văn cao học

DANH MỤC HÌNH VẼ

Hình 1.1: Mô hình mạng P2P .................................................................................................. 5

Hình 1.2: Mạng tùy biến không dây ........................................................................................ 7

Hình 1.3: Mục đích giải quyết của bài toán quản lý topology cho mạng tùy biến

không dây .........................................................................................................8

Hình 1.4: Vị trí của giao thức quản lý topology trong tầng giao thức................................... 11

Hình 1.5: Quan hệ giữa lớp routing và lớp quản lý topology................................................ 12

Hình 1.6: Quan hệ giữa lớp quản lý topology vả lớp MAC .................................................. 13

Hình 2.1: Mạng không dây tùy biến mật độ lớn.................................................................... 14

Hình 2.2: Tính bất đối xứng của tập liền kề .......................................................................... 16

Hình 2.3: Sự phụ thuộc của xác suất download file vào thứ hạng file .................................. 22

Hình 3.1: Xác suất để có ít nhất 1 nút trong tập chuyển tiếp của nút s ở trạng thái hoạt

động khi nút s hoạt động........................................................................................ 35

Hình 3.2: Các trường thông tin cần lưu trữ về nút mạng lân cận của giao thức AWP.......... 36

Hình 3.3: Sự phụ thuộc giữa tỷ lệ gói tin được gửi thành công với tỷ lệ phần trăm thời

gian hoạt động của nút........................................................................................... 37

Hình 3.4: Sự phụ thuộc giữa độ trễ của gói tin với tỷ lệ phần trăm thời gian hoạt động

của nút ................................................................................................................... 38

Hình 3.5: Năng lượng tiêu thụ của mạng theo thời gian ....................................................... 38

Hình 3.6: Tổng năng lượng tiêu thụ của mạng trong 300 s ................................................... 39

Hình 3.7: Thiết kế (7:3:1) của lịch bật tắt.............................................................................. 40

Hình 3.8: Cấu trúc của 1 time frame...................................................................................... 41

Hình 3.9: Ví dụ minh họa về 2 nút lân cận luôn nhận được message thông báo của nhau

(Dù đồng hồ bị lệch nhau) ..................................................................................... 41

Hình 3.10: Các trường thông tin cần lưu trữ về một nút mạng lân cận trong giao

thức AWP ............................................................................................................. 42

Hình 3.11: Tỷ lệ phần trăm của năng lượng dùng cho việc điều khiển trong giao

thức CAW............................................................................................................. 52

Hình 4.1: Quá trình gửi message báo động trong mạng sensor khi phát hiện dấu hiệu

bất thường ............................................................................................................. 60

Giao thức quản lý topology trong mạng không dây ngang hàng

Phùng Minh Quân - Luận văn cao học

DANH MỤC BẢNG BIỂU

Bảng 2.1 Các tham số của mô hình giả lập............................................................... 18

Bảng 2.2: Tỷ lệ yêu cầu download file thành công khi áp dụng thuật toán dựa trên

tính công bằng.......................................................................................... 19

Bảng 2.3: Độ trễ khi sử dụng thuật toán dựa trên tính công (tính theo giây) .......... 20

Bảng 2.4: Tỷ lệ yêu cầu download file được thực hiện thành công khi sử dụng thuật

toán dựa trên độ phổ biến ........................................................................ 23

Bảng 2.5: Độ trễ khi sử dụng thuật toán dựa trên độ phổ biến................................. 24

Bảng 2.6: Tỷ lệ yêu cầu download file được thực hiện thành công khi sử dụng thuật

toán dựa trên mức năng lượng................................................................. 26

Bảng 2.7: Độ trễ khi sử dụng thuật toán dựa trên mức năng lượng.......................... 26

Bảng 2.8: Đề xuất sử dụng các thuật toán xây dựng tập liền kề............................... 29

Bảng 3.1: Các tham số chính sử dụng trong mô hình giả lập AWP, CAW.............. 50

Bảng 3.2: Tỷ lệ yêu cầu download file được thực hiện thành công đối với CAW

và AWP ................................................................................................... 53

Bảng 3.3: Độ trễ của CAW và AWP ........................................................................ 53

Bảng 3.4: Đề xuất sử dụng các thuật toán bật tắt nút mạng ..................................... 54