ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Nguyễn Gia Như

PHÁT TRIỂN THUẬT TOÁN
TIẾN HÓA GIẢI MỘT SỐ BÀI TOÁN
TỐI ƯU TRONG MẠNG KHÔNG DÂY

LUẬN ÁN TIẾN SỸ TOÁN HỌC

Hà Nội - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Nguyễn Gia Như

PHÁT TRIỂN THUẬT TOÁN TIẾN
HÓA GIẢI MỘT SỐ BÀI TOÁN TỐI
ƯU TRONG MẠNG KHÔNG DÂY
Chuyên ngành: Cơ sở toán học cho Tin học
Mã số: 62460110

LUẬN ÁN TIẾN SỸ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS.TS Lê Trọng Vĩnh
2. PGS.TSKH Nguyễn Xuân Huy


hỗ trợ kinh phí cho tôi hoàn thành luận án này.
Cuối cùng, tôi xin bày tỏ lòng biết ơn đối với gia đình và người thân đã luôn
động viên, hỗ trợ tôi trong suốt thời gian học tập và thực hiện luận án.

ii


Mục lục
Lời cam đoan

i

Lời cảm ơn

ii

Danh mục từ viết tắt

vi

Danh mục bảng

viii

Danh mục hình vẽ

ix

Mở đầu



.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

5
5
5
6
6

2.1 Tối ưu thông lượng trong mạng lưới không dây . . . . . . . . . .
2.1.1 Mô hình hóa và phát biểu bài toán . . . . . . . . . . . .
2.1.1.1 Kiến trúc hệ thống . . . . . . . . . . . . . . . .
2.1.1.2 Mô hình truyền thông . . . . . . . . . . . . . .
2.1.1.3 Thông lượng . . . . . . . . . . . . . . . . . . .
2.1.1.4 Trọng số MTW . . . . . . . . . . . . . . . . . .
2.1.1.5 Chia sẻ hiệu suất sử dụng các Gateway . . . . .
2.1.1.6 Lập trình tính toán thông lượng . . . . . . . . .
2.1.1.7 Phân tích, đánh giá các phương pháp . . . . . .
2.1.2 Đặt gateway hiệu quả sử dụng thuật toán PSO . . . . .
2.1.2.1 Biểu diễn của một phần tử . . . . . . . . . . .
2.1.2.2 Khởi tạo quần thể ban đầu . . . . . . . . . . .
2.1.2.3 Hàm đo độ thích nghi . . . . . . . . . . . . . .
2.1.2.4 Quá trình tiến hóa . . . . . . . . . . . . . . . .
2.1.2.5 Quá trình dừng . . . . . . . . . . . . . . . . . .
2.1.2.6 Mô tả thuật toán . . . . . . . . . . . . . . . . .
2.1.3 Kết quả mô phỏng và đánh giá . . . . . . . . . . . . . .
2.1.3.1 Tham số mô phỏng . . . . . . . . . . . . . . . .
2.1.3.2 Kết quả mô phỏng . . . . . . . . . . . . . . . .
2.2 Truyền thông Broadcast và cây truyền thông tối ưu . . . . . . .
2.2.1 Bài toán cây khung truyền thông tối ưu . . . . . . . . .
2.2.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . .
2.2.2.1 Mã hóa tập cạnh . . . . . . . . . . . . . . . . .
2.2.2.2 Mã hóa Prufer . . . . . . . . . . . . . . . . . .
2.2.2.3 Mã hóa liên kết cạnh và nút (LNB) . . . . . . .
2.2.2.4 Mã hóa NetKeys . . . . . . . . . . . . . . . . .
2.2.2.5 Mã hóa CB-TCR . . . . . . . . . . . . . . . . .
2.2.3 Tối ưu cây khung truyền thông sử dụng thuật toán PSO
2.2.3.1 Mã hóa và giải mã . . . . . . . . . . . . . . . .
2.2.3.2 Mô tả thuật toán . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.

47
47
48
48
49
50
50
52
54
59
59
60
60
60
61
61
61
61
61
62
65
66
68
69


3.3

Mã hóa cá thể . . . . . . . . . . . . . . . . . . .
Mô tả thuật toán . . . . . . . . . . . . . . . . . .
3.1.4
mô phỏng và đánh giá . . . . . . . . . . . . . . .
Mô hình thực nghiệm và thiết lập tham số cho các
thuật toán . . . . . . . . . . . . . . . . . . . . . .
3.1.4.2 Phân tích, đánh giá các thuật toán . . . . . . . .
3.1.4.3 Áp dụng thử nghiệm tại thành phố Đà Nẵng . .
Tối ưu truy cập tập trung trong mạng không dây . . . . . . . . .
3.2.1 Mô hình hóa và phát biểu bài toán . . . . . . . . . . . . .
3.2.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . .
3.2.3 Tối ưu truy cập tập trung sử dụng thuật toán PSO . . . .
3.2.3.1 Mã hóa cá thể . . . . . . . . . . . . . . . . . . .
3.2.3.2 Mô tả thuật toán . . . . . . . . . . . . . . . . . .
3.2.4 Kết quả mô phỏng và đánh giá . . . . . . . . . . . . . . .
3.2.4.1 Mô hình thực nghiệm và thiết lập tham số cho các
thuật toán . . . . . . . . . . . . . . . . . . . . . .
3.2.4.2 Phân tích, đánh giá các thuật toán . . . . . . . .
Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. 85
. 87
. 87
.
.
.
.

Tài liệu tham khảo

105

v


Danh mục từ viết tắt
Viết tắt

Dạng đầy đủ

Diễn giải

ACO

Ant Colony Optimization

Tối ưu đàn kiến

BSC

Base Station Controller

Trạm điều khiển cơ sở

BSS

Base Station Subsystem


Thuật toán tiến hóa

EP

Evolutionary Programming

Lập trình tiến hóa

ES

Evolutionary Strategies

Các chiến lược tiến hóa

FDMA

Frequency Division Multiple Access

Đa truy cập phân chia tần số

GA

Genetic Algorithm

Thuật toán di truyền

GoS

Grade of Service


Tổng đài truy cập tập trung

MANET

Mobile Adhoc Network

Mạng di động Ad-hoc

MS

Mobile Station

Trạm di động cơ sở

MSC

Mobile Switch Controller

Tổng đài chuyển mạch

MTW

Multihop Traffic-flow weight

Trọng số lưu lượng đa chặng

NGN

Next Generation Network


Bộ ghi định vị thường trú
vi


WLAN

Wireless Local Area Network

Mạng LAN không dây

WMAN

Wireless Metropolitan Area Network

Mạng di động đô thị

WMN

Wireless Mesh Network

Mạng lưới không dây

WPAN

Wireless Personal Area Network

Mạng cá nhân không dây

WMN


.
.

63
73
75
76

3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10

Qui ước các ký hiệu dùng trong bài toán TA . . . . . . . . . .
Qui ước các ký hiệu dùng trong bài toán đặt trạm điều khiển .
Ví dụ về bài toán TA . . . . . . . . . . . . . . . . . . . . . . . .
Thông tin về bộ dữ liệu thực nghiệm đặt trạm điều khiển . . .
Các tham số thiết lập khi chạy thuật toán . . . . . . . . . . . .
So sánh hàm mục tiêu của các thuật toán . . . . . . . . . . . .
Đề xuất qui hoạch trạm BTS tại Đà Nẵng . . . . . . . . . . . .
Định nghĩa các ký hiệu dùng trong bài toán truy cập tập trung
Thông tin về bộ dữ liệu thực nghiệm tối ưu truy cập . . . . . .
Các tham số thiết lập khi chạy thuật toán . . . . . . . . . . . .


.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.


1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
1.11
1.12
1.13
1.14
1.15
1.16

Kiến trúc mạng lưới không dây . . . . . . . . .
Kết nối điểm-điểm . . . . . . . . . . . . . . . .
Kết nối điểm–đa điểm . . . . . . . . . . . . . .
Kết nối đa điểm – đa điểm . . . . . . . . . . .
Mô hình hệ thống thông tin di động GSM . . .
Lộ trình phát triển của thông tin di động . . .
Kiến trúc mạng di động không dây . . . . . . .
Quá trình quy hoạch mạng . . . . . . . . . . .
Sơ đồ tổng quát của thuật toán di truyền . . .
Thí nghiệm đàn kiến 1 . . . . . . . . . . . . . .
Thí nghiệm đàn kiến 2 . . . . . . . . . . . . . .
Sơ đồ tổng quát của thuật toán tối ưu đàn kiến
Quy luật chuyển động của bầy đàn . . . . . . .
Quy luật tìm tổ của bầy đàn . . . . . . . . . .

.
.
.
.
.
.

10
12
12
12
13
14
15
22
29
31
32
33
35
35
36
45

2.1
2.2
2.3
2.4
2.5
2.6


48
51
53
55
56

.
.
.
.
.
.
.
.
.
.
.
.

58
64
64
64
65
66
68
68
72
72


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

So sánh các phương án tối ưu của bài toán #4 giữa các thuật
Kiến trúc mạng truy cập không dây . . . . . . . . . . . . . .
Mô hình mạng truy cập không dây . . . . . . . . . . . . . . .
Mô hình mạng truy cập không dây theo kiến trúc cây . . . .
So sánh hàm mục tiêu giữa các thuật toán . . . . . . . . . . .
So sánh thời gian thực thi giữa các thuật toán . . . . . . . . .

x

. . .
. . .
. . .
. . .
. . .
toán
. . .
. . .
. . .
. . .
. . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

81
82
84
86
89
89
94
95
96
101
101


Mở đầu
Ngày nay, mạng máy tính đã trở thành một cơ sở hạ tầng quan trọng trong
nền kinh tế toàn cầu và sự ra đời của Internet đã làm thay đổi mạnh mẽ của cuộc
sống con người. Trong cuộc cách mạng này, bên cạnh sự tiến bộ về mặt công nghệ
thì vai trò của việc nghiên cứu và đề xuất các thuật toán mới cũng có ý nghĩa
hết sức quan trọng. Để đưa ra được giải pháp hữu hiệu cho một vấn đề thực tế
cần sự hiểu biết cả lý thuyết thuật toán và các phương tiện kỹ thuật. Một trong
những vấn đề đáng quan tâm nhất của mạng máy tính là hiệu năng mạng. Hiệu

được quản lý một cách hiệu quả hơn và các kênh cũng được sử dụng
hiệu quả hơn.
(b) Sự cung cấp băng thông thông minh: Đây là một thách thức chính
trong các mạng không dây ở thế hệ sau, nó được xem xét không tầm
thường và hầu như chưa được giải quyết hoàn toàn. Các giải pháp cho
cấp phát băng thông động là cần thiết để hỗ trợ các dịch vụ đa phương
tiện đã được tích hợp với các yêu cầu QoS. Trong khi đó, việc cực đại
thông lượng mạng không liên quan đến sự thay đổi về lưu lượng.
2. Các mạng di động không đồng nhất: Việc định tuyến các gói tin có quan hệ
với nhau để kết nối chuyển giao giữa các vùng. Các thuật toán định tuyến
truyền thống không xem xét đầy đủ khoảng thời gian có thể cho việc truy
cập bởi các thiết bị đầu cuối trong suốt quá trình xử lý chuyển giao. Đó là
mong muốn để tạo ra các thuật toán định tuyến mới có thể duy trì hiệu suất
end-to-end với những cân nhắc đầy đủ về quá trình bàn giao trong mạng
không đồng nhất. Như vậy việc hỗ trợ các ứng dụng thời gian thực là đặc
biệt quan trọng trong mạng như VoIP, truyền video, . . .
3. Vấn đề an ninh cho mạng không dây:
(a) Việc sử dụng các tài nguyên không dây cho các ứng dụng an ninh:
Thách thức đặt ra ở đây là làm sao để sử dụng các tài nguyên đang tồn
tại trong các mạng không dây hỗ trợ ứng dụng liên quan tới an ninh.
Ví dụ Radar tự động và màn hình giám sát dựa trên mệnh lệnh.
(b) Kỹ thuật bảo mật cho các mạng không dây: Các vấn đề chính được xác
định cho việc thiết kế của các hệ thống như là: tính tỉ lệ, độ phức tạp
và hiệu quả; độ vững chắc; các kỹ thuật an ninh mạng cho các mạng
không dây; và các kỹ thuật riêng biệt cho việc thiết kế an ninh trong
mạng ad-hoc và các mạng điểm tới điểm.
Trong thực tế, các bài toán tối ưu mạng thường gặp là các bài toán tối ưu
tổ hợp, trong đó phải tìm các giá trị cho các biến rời rạc để làm cực trị hàm mục
tiêu nào đó [14]. Đa số các bài toán này thuộc lớp NP-khó. Trừ các bài toán cỡ
nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thường không thể tìm

Luận án tập trung giải quyết một lớp vấn đề về tối ưu trên mạng không dây với
cách tiếp cận thuật toán tiến hóa PSO và hướng tới ba mục tiêu như sau:
(i) Tối ưu thông lượng trong mạng lõi: mạng lõi (Core network -CN) đóng vai
trò quan trọng trong việc quyết định năng lực phục vụ cũng như khả năng
nâng cấp mạng. Tất cả các nhu cầu xuất phát từ phần mạng truy nhập
đều phải thông qua xử lý của phần mạng lõi, và bất cứ những sự thay
đổi nào cũng đều dựa trên khả năng phục vụ của phần CN. Vì vậy việc
nghiên cứu tính toán và tối ưu dung lượng mạng lõi CN là hết sức quan
trọng [11, 28, 55, 60, 61, 65, 66, 73].
(ii) Tối ưu thông lượng trong mạng lưới không dây: Để xác định vị trí gateway
nhằm đạt thông lượng cực đại, một độ đo hiệu năng được sử dụng gọi là
Multihop Traffic flow weight nhằm tính toán những nhân tố ảnh hưởng đến
thông lượng của mạng WMNs [4, 45, 59, 64]
(iii) Tối ưu truy cập trong mạng không dây: Xác định các base station trong mạng
không dây là một trong những khâu quan trọng của quá trình thiết kế mạng
không dây. Việc định vị các base station trong mạng không dây liên quan
đến nhiều yếu tố khác nhau như lưu lượng mạng , kênh truyền, kịch bản can
thiệp, số lượng Base Stations và các thông số quy hoạch mạng khác. Sau khi
tối ưu được vị trí các trạm Base Stations, công việc tiếp theo chúng tôi tiếp
cận là tối ưu truy cập tập trung trong mạng không dây với sự kết hợp giữa
các BTS, MSC và LE [2, 21, 23, 24, 42, 47, 49, 50, 74].
3


Với các mục tiêu hướng đến như đã phân tích ở trên, cấu trúc của luận án
được tổ chức như sau:
- Chương 1: Trình bày tổng quan về tối ưu mạng. Trong chương này, phần
đầu luận án giới thiệu tổng quan về mạng không dây, các vấn đề của tối ưu
mạng. Tiếp theo, luận án trình bày các thuật toán tiến hóa như: giải thuật
di truyền (GA), tối ưu hóa đàn kiến (ACO) và thuật toán tối ưu bầy đàn

trong kỷ yếu hội nghị quốc tế, 2 bài báo đăng trên các tạp chí quốc tế, 1 bài đăng
trên tạp chí trong nước và 4 bài trong kỷ yếu hội quốc gia chuyên ngành.
4


Chương 1
Tổng quan về tối ưu mạng
Xã hội càng phát triển nhu cầu truyền thông của con người ngày càng cao,
mọi người muốn mình có thể được kết nối với thế giới vào bất cứ lúc nào, từ bất
cứ nơi đâu. Đó chính là lý do mạng không dây ra đời và liên tục được tập trung
nghiên cứu và phát triển trong nhiều năm qua. Do những lợi ích về tính linh hoạt
và tiện lợi khi sử dụng nên các chuẩn không dây ngày càng được ứng dụng phổ
biến, mỗi chuẩn kỹ thuật đều có những ưu và nhược điểm về phạm vi phủ sóng,
tốc độ truyền dữ liệu, yêu cầu về thời gian thực,. . . Tuỳ từng yêu cầu cụ thể mà
chúng ta sử dụng các kỹ thuật khác nhau. Hiện nay, hệ thống mạng không dây đã
được triển khai rộng rãi nhất trên toàn thế giới. Thành công của các mạng không
dây do tính hiệu quả, giá thành rẻ, dễ dàng lắp đặt, triển khai mà vẫn đảm bảo
tốc độ truyền dữ liệu khá cao.
Ra đời trong bối cảnh nhu cầu liên lạc giao tiếp xã hội ngày càng cao, các ứng
dụng truyền thông đa phương tiện đang khẳng định vai trò và ý nghĩa quan trọng
của mình một cách mạnh mẽ. Các ứng dụng truyền thông đa phương tiện xuất
hiện ở nhiều nơi, nhiều lúc và trong nhiều lĩnh vực, từ đời sống thường nhật, giao
tiếp liên lạc, giải trí và giáo dục: VoIP, Movie Streaming, Video Conference,. . . Do
đó sự kết hợp giữa tính linh hoạt và tiện lợi của mạng không dây và nhu cầu sử
dụng lớn của các ứng dụng đa phương tiện trở thành một xu hướng tất yếu, đầy
tiềm năng. Với những tiến bộ của công nghệ hình ảnh, âm thanh cùng với mong
muốn của người dùng thì các ứng dụng đa phương tiện luôn luôn có nhu cầu sử
dụng đường truyền cả về tốc độ và chất lượng vượt trước khả năng đáp ứng của
phương tiện. Đây chính là vấn đề mà bài toán tối ưu mạng cần phải giải quyết.


đã được phát triển từ giữa những năm 1990, nhưng mãi đến năm 2002 nó mới
trở nên thông dụng ở các thiết bị từ máy tính xách tay đến các thiết bị hỗ trợ cá
nhân không dây. Công nghệ Bluetooth hiện đang có xu hướng sử dụng thay thế
cáp ngoại vi cho một số các thiết bị, hơn là công cụ nhằm cho phép một số lượng
lớn các thiết bị trong nhà hoặc văn phòng cho phép giao tiếp trực tiếp với nhau
không cần dây cáp.
Viện công nghệ Điện và Điện tử IEEE (Institute of Electrical and Electronics
Engineers) đã đưa ra chuẩn 802.15 và được sử dụng trong mạng WPAN với các
tốc độ truyền dữ liệu khác nhau : 802.15.1 với tốc độ truyền dữ liệu trung bình,
trong khi 802.15.3 có tốc độ truyền dữ liệu cao và 802.15.4 có tốc độ truyền thấp.
IEEE 802.15.1 đặc tả công nghệ Bluetooth đã được thiết kế để cho phép kết nối
không dây băng thông hẹp, cho phép các thiết bị máy tính xách tay, chuột, bàn
phím, máy in, tai nghe, điện thoại di động,... truyền thông với nhau [34].

1.1.2.2

Mạng cục bộ không dây

WLAN là một mạng cục bộ kết nối hai hay nhiều máy tính với nhau thông
qua việc sử dụng sóng hồng ngoại hoặc sóng vô tuyến để truyền nhận dữ liệu [68].
WLAN hiện nay đã được ứng dụng rộng rãi trong các tòa nhà, trường học, bệnh
viện, công ty và công cộng,...Có hai công nghệ chính được sử dụng để truyền thông
trong WLAN là truyền thông bằng tia hồng ngoại hoặc truyền thông bằng sóng
vô tuyến, thông thường thì sóng radio được dùng phổ biến hơn vì nó truyền xa
hơn, lâu hơn, rộng hơn, và có băng thông cao hơn. LAN cũng có hai dạng kiến
trúc là WLAN có cơ sở hạ tầng (sử dụng các Access Point hoặc trạm cơ sở Base
Station) để kết nối phần mạng không dây với phần mạng có dây truyền thống và
mạng không có cơ sở hạ tầng (mạng Ad-hoc) [72].
6


1-10Mbit/s), độ trễ cao hơn, tỉ lệ lỗi cũng nhiều hơn (tỉ lệ lỗi là 10-4 so với 10-10
của mạng sử dụng cáp quang). Tuy vậy, theo một số chuẩn mới, ở một số môi
trường truyền đặc biệt, việc truyền thông trong mạng không dây cũng có thể đạt
được tốc độ cao hơn đáng kể, ví dụ như trong chuẩn 802.11n việc truyền thông có
thể đạt tốc độ từ 100-200Mbit/s. Vấn đề chi phí cho các thiết bị của mạng WLAN
có giá thành cao hơn khá nhiều so với các thiết bị mạng có dây, điều này là một
trở ngại cho sự phát triển của mạng không dây. Tiếp đó là vấn đề độc quyền trong
các sản phẩm. Nhiều thiết bị và sản phẩm chỉ có thể hoạt động được nếu sử dụng
phần cứng hoặc phần mềm của công ty sản xuất nào đó, và phải hoạt động theo
quy định của quốc gia mà nó đang được sử dụng. Các tần số phát cũng được các
quốc gia quy định nhằm tránh việc xung đột sóng vô tuyến của các mạng khác
nhau. Do đó, việc sản xuất các sản phẩm cho mạng WLAN cần phải chú ý đến
quy định của từng quốc gia. Cuối cùng là phạm vi phủ sóng của mạng không dây,
7


các mạng không dây chỉ hoạt động trong phạm vi nhất định. Nếu ra khỏi phạm
vi phát sóng của mạng thì chúng ta không thể kết nối mạng [68].
Song song với sự phát triển của mạng không dây, mạng WLAN được chia ra
thành hai mô hình chính, đó là mô hình mạng không dây có cơ sở hạ tầng và mô
hình mạng không dây không có cơ sở hạ tầng Ad-hoc. Các kiến trúc mạng này
được đưa ra nhằm làm cho mạng không dây dần thoát khỏi sự phụ thuộc hoàn
toàn vào mạng cơ sở hạ tầng. Một trong những mô hình mạng được đề xuất đó
chính là mạng Ad-hoc thường được viết tắt là MANET. Việc các mạng không dây
ít phụ thuộc vào cơ sở hạ tầng là một điều rất thuận lợi nhưng lại có những vấn
đề khác đặt ra như tốc độ truyền thông không cao, mô hình mạng không ổn định
như mạng có dây truyền thống do các nút mạng hay di chuyển, năng lượng cung
cấp cho các nút mạng thường chủ yếu là pin...

1.1.2.3



việc tạm thời. Tuy nhiên chúng có thể có những nhược điểm về vùng phủ sóng
bị giới hạn, mọi người sử dụng đều phải nằm trong vùng có thể “nghe” được lẫn
nhau.
Ứng dụng của mạng Ad-hoc để đáp ứng nhu cầu truyền thông mang tính
chất tạm thời: Ở tại địa điểm trong một khoảng thời gian nhất định, giống như
trong một lớp học, một cuộc hội thảo hay một cuộc họp,...việc thiết lập một mạng
mang tính chất tạm thời để truyền thông với nhau chỉ diễn ra trong một khoảng
thời gian ngắn. Nếu chúng ta thiết lập một mạng có cơ sở hạ tầng, dù là mạng
không dây cần chi phí cao về tài nguyên cũng như nhân lực, vật lực, thời gian. Do
đó, mạng Ad-hoc được coi là giải pháp tốt nhất cho những tình huống này. Hỗ trợ
khi xảy ra các thiên tai, hỏa hoạn và dịch họa: khi xảy ra các thiên tai như hỏa
hoạn, động đất, cháy rừng ở một nơi nào đó, cơ sở hạ tầng ở đó như đường dây,
các máy trạm, máy chủ,... có thể bị phá hủy dẫn đến hệ thống mạng bị tê liệt là
hoàn toàn khó tránh khỏi. Vì thế, việc thiết lập nhanh chóng một mạng cần thời
gian ngắn mà lại có độ tin cậy cao và không cần cơ sở hạ tầng để đáp ứng truyền
thông, nhằm giúp khắc phục, giảm tổn thất sau thiên tai, hỏa hoạn là cần thiết.
Khi đó mạng Ad-hoc là một lựa chọn phù hợp nhất cho những tình huống như
vậy [72]. Trong một số ứng dụng nào đó, nếu sử dụng dịch vụ mạng có cơ sở hạ
tầng có thể không hiệu quả cao bằng việc dùng mạng Ad-hoc. Ví dụ như với một
mạng có cơ sở hạ tầng, do được điều khiển bởi một điểm truy cập mạng lên các
nút mạng muốn truyền thông với nhau đều phải thông qua nó. Ngay cả khi hai
nút mạng ở gần nhau, chúng cũng không thể trực tiếp truyền thông với nhau mà
phải chuyển tiếp qua một điểm truy cập tập trung. Điều đó gây ra một sự lãng
phí thời gian và băng thông mạng. Trong khi đó, nếu sử dụng mạng Ad-hoc việc
truyền thông giữa hai nút mạng đó lại trở lên vô cùng dễ dàng và nhanh chóng.
Hai nút mạng gần nhau có thể truyền thông trực tiếp với nhau mà không cần phải
thông qua thiết bị trung gian nào khác.


cung cấp sự truy cập mạng cho các clients. Các thiết bị này thường không bị ràng
buộc về năng lượng, khả năng tính toán, bộ nhớ và hoạt động như những thiết bị
chuyển mạch thông minh. WMN có tất cả các ưu điểm của các mạng không dây
Ad-hoc và có thêm nhiều ưu điểm mở rộng nhờ kỹ thuật kiến trúc cơ sở hạ tầng.
Mesh backbone có thể triển khai nhanh chóng với giá thành thấp nhưng là một hệ
thống hiệu quả, thực tế, mềm dẻo và mạnh để hỗ trợ việc truy cập mạng cho các
client. Mesh backbone có thể cung cấp cho các client nhiều dịch vụ và tài nguyên
khác nhau thông qua các chức năng gateway (cổng mạng) và bridging (cầu nối).
Những thuận lợi này nhấn mạnh rằng, WMN là công nghệ hứa hẹn cho một số
lượng lớn các ứng dụng như là mạng gia đình, mạng cộng đồng hay tập đoàn, truy
nhập internet công cộng. . . tốc độ cao.
Sự phát triển nhanh chóng của công nghệ mạng không dây trong những năm
gần đây đã cho phép người sử dụng chủ động trong việc lựa chọn giải pháp thích
hợp khi triển khai mạng. Mỗi công nghệ mạng không dây được thiết kế để hoạt
động ở một phạm vi nhất định và được phân loại theo khả năng phủ sóng của
từng công nghệ. Trong các ứng dụng mạng không dây phạm vi vừa và nhỏ, 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
10


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 các tính chất của mạng. Kỹ
thuật mạng hình lưới không dây WMN 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 [4].
Trong những năm gần đây, mạng lưới không dây (WMN) đã được sử dụng như
là giải pháp chủ yếu cho việc mở rộng kết nối Internet cho các nút di động. Nhiều
thành phố ở Mỹ (Medford, Oregon; Chaska, Minnesota; và Gilbert, Arizona) đã

khu vực thuê bao chứ không phải lắp tại nút đường lên. Tuy vậy, các trạm
thu phải nằm trong phạm vi phủ sóng và có đường nhìn thẳng với trạm phát
11


sóng gốc. Các vật cản như cây cối, nhà cửa, đồi núi. . . sẽ góp phần làm cấu
hình mạng lưới Điểm – Đa điểm hoạt động không hiệu quả (Xem Hình 1.3).
- Đa điểm–Đa điểm (Multipoints–to-Multipoints): Mỗi nút có vai trò không
chỉ là điểm truy nhập cho các trạm mà còn làm nhiệm vụ chuyển tiếp dữ
liệu. Cấu hình này có độ tin cậy mạng cao nhất do các nút có sự liên thông
với nhau, một nút chỉ cần có kết nối với một nút bất kỳ mà không cần phải
có kết nối trực tiếp với nút đường lên như trong cấu hình Điểm–Đa điểm,
là có thể kết nối với toàn mạng. Tuy nhiên, đổi lại giao thức tìm đường của
mạng sẽ có độ phức tạp cao hơn (Xem Hình 1.4).

Hình 1.2: Kết nối điểm-điểm

Hình 1.3: Kết nối điểm–đa điểm

Hình 1.4: Kết nối đa điểm – đa điểm

12


Ưu điểm của mô hình lưới đó là độ tin cậy cao vì các kết nối mạng không phụ
thuộc vào bất kỳ node nào. Nếu một node của mạng bị trục trặc, các node có thể
tương tác với một node khác thông qua node trung gian. Mô hình này cũng thích
hợp cho các mạng lớn như mạng WAN vì nó cho phép nhiều vị trí trên mạng lớn
kết nối đến một nơi tin cậy khác.