TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────

LUẬN VĂN THẠC SĨ
NGÀNH CÔNG NGHỆ THƠNG TIN

Thiết kế topo cho mạng lưới
khơng gian tự do

Học viên thực hiện :

Nguyễn Mạnh Tiến

Giảng viên hướng dẫn: PGS.TS. Trương Thị Diệu Linh

HÀ NỘI 3-2019


PHIẾU GIAO NHIỆM VỤ LUẬN VĂN THẠC SĨ
1. Thông tin về học viên
Họ và tên học viên: Nguyễn Mạnh Tiến
Điện thoại liên lạc: 0915054001

Email:

Khóa CH2016B

Hệ đào tạo: Đại học chính quy

Luận văn thạc sĩ được thực hiện tại: Viện Công nghệ thông tin và Truyền thông, Đại

học Bách khoa Hà Nội
Thời gian làm luận văn: Từ ngày 23/11/2017 đến 27/03/2019
2. Mục đích nội dung của luận văn
- Xây dựng phương án, giải pháp dự phịng khi có tình huống gián đoạn đường
truyền
- Thiết kế Topo mạng đáp ứng giải pháp dự phòng nêu trên, với các yêu cầu về
băng thông, độ phủ và tỷ lệ lỗi nằm trong giới hạn cho phép
3. Các nhiệm vụ cụ thể của luận văn
- Tìm hiểu lý thuyết cơ bản của truyền thơng quang khơng dây FSO.
- Tìm hiểu các phương pháp giải quyết bài toán đặt ra.
- Đề xuất giải pháp cho bài toán thiết kế topo đáp ứng khả năng dự phịng cho mạng
quang khơng dây.
- Cài đặt và đánh giá hiệu quả của giải thuật đề xuất.
4. Lời cam đoan của học viên:
Tôi – Nguyễn Mạnh Tiến – cam kết luận văn thạc sĩ là cơng trình nghiên cứu của
bản thân tôi dưới sự hướng dẫn của PGS.TS. Trương Thị Diệu Linh
Các kết quả nêu trong luận văn thạc sĩ là trung thực, khơng phải là sao chép tồn văn
của bất kỳ cơng trình nào khác.
Hà Nội, ngày tháng năm
Tác giả luận văn

Nguyễn Mạnh Tiến
5. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của luận văn và cho phép
bảo vệ:
Hà Nội, ngày tháng năm
Giáo viên hướng dẫn

Trương Thị Diệu Linh
2



LỜI CẢM ƠN
Lời đầu tiên, tôi xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trương Thị Diệu
Linh, người đã tận tình dạy dỗ, chỉ bảo, hướng dẫn tơi trong suốt thời gian thực hiện
luận văn này.
Đồng thời tôi cũng xin bày tỏ lòng cảm ơn sâu sắc tới các thầy, cô trong Viện
Công nghệ thông tin và truyền thơng nói riêng cũng như các thầy, cơ trong trường
Đại học Bách Khoa Hà Nội nói chung, những người đã dạy dỗ và truyền đạt cho tôi
những kiến thức quý báu.
Cuối cùng, tôi xin được gửi lời cảm ơn tới gia đình, người thân và bạn bè,
những người ln ủng hộ, hỗ trợ và tạo mọi điều kiện tốt nhất để tơi có thể hồn thành
luận văn này.

Hà Nội, tháng 3 năm 2019

Học viên : Nguyễn Mạnh Tiến

3


MỤC LỤC
PHIẾU GIAO NHIỆM VỤ LUẬN VĂN THẠC SĨ ...................................................2
LỜI CẢM ƠN .............................................................................................................3
TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ ........................................................6
DANH MỤC HÌNH ẢNH ..........................................................................................9
DANH MỤC TỪ VIẾT TẮT VÀ THUẬT NGỮ ....................................................10
MỞ ĐẦU ...................................................................................................................11
CHƯƠNG I: GIỚI THIỆU CHUNG VỀ ĐỀ TÀI VÀ HƯỚNG GIẢI QUYẾT .....13
1.1.


ĐẶT VẤN ĐỀ .............................................................................................13

1.2.

ĐỊNH HƯỚNG GIẢI QUYẾT ...................................................................15

CHƯƠNG II: CƠ SỞ LÝ THUYẾT.........................................................................17
2.1

HỆ THỐNG QUANG KHƠNG DÂY ........................................................17

2.2

MƠ HÌNH HỆ THỐNG FSO ......................................................................18

2.3

HỆ THỐNG HẠ TẦNG MẠNG TRÊN CAO HAP ...................................19

2.4

PHÂN CỤM FSO SỬ DỤNG THUẬT TỐN K-MEAN .........................21

2.5

CÁC PHƯƠNG PHÁP DỰ PHỊNG ĐƯỜNG ĐI .....................................23

2.5.1

Dự phịng topo theo vịng .....................................................................24


2.5.2

Dự phịng tuyến tính: ............................................................................25

2.5.3. Dự phịng theo tài ngun: .......................................................................25
2.6 TÌM ĐƯỜNG ĐI CĨ DỰ PHỊNG SỬ DỤNG THUẬT TỐN
SUURBALLE ........................................................................................................26
2.7

XÂY DỰNG MƠ HÌNH MẠNG ................................................................27

2.7.1.

Tổng quan .............................................................................................27

2.7.2.

Các điều kiện ràng buộc .......................................................................27

2.7.3.

Tỷ lệ lỗi bit – BER ................................................................................28

CHƯƠNG III: XÂY DỰNG GIẢI THUẬT THIẾT LẬP TOPO MẠNG ...............30
3.1.

MỤC TIÊU ..................................................................................................30

3.2.


CÁC VẤN ĐỀ CẦN XỬ LÝ ......................................................................30

3.3.

PHÂN CỤM CÁC THIẾT BỊ FSO .............................................................33

3.4. ĐỀ XUẤT GIẢI THUẬT TÌM ĐƯỜNG ĐI CĨ DỰ PHỊNG CHO MỖI
CẶP NGUỒN – ĐÍCH ..........................................................................................35
3.5.

ĐỀ XUẤT THUẬT TỐN BỔ SUNG CÁC HAP ....................................37
4


3.6. ĐỀ XUẤT THUẬT TOÁN XÂY DỰNG ĐƯỜNG ĐI DỰ PHỊNG CHO
CÁC CẶP NGUỒN ĐÍCH CHỈ CĨ MỘT ĐƯỜNG ĐI CHÍNH .........................38
CHƯƠNG IV: CÀI ĐẶT THUẬT TỐN VÀ KẾT QUẢ THỰC HIỆN ...............39
4.1.

MÔI TRƯỜNG CÀI ĐẶT ..........................................................................39

4.2.

ĐẦU VÀO DỮ LIỆU:.................................................................................39

4.3.

KẾT QUẢ THỬ NGHIỆM .........................................................................40


4.3.1.

Kết quả phân cụm các node ..................................................................40

4.3.2.

Kết quả phân cụm các node có phân vùng ...........................................41

4.3.3. Thử nghiệm với các cụm FSO, trong đó có các đường liên kết giữa các
cụm khác nhau ....................................................................................................42
4.3.4.

Kết quả sử dụng giải thuật đề xuất, bổ sung đường đi đầu tiên ...........43

4.3.5.

Kết quả sử dụng giải thuật đề xuất, bổ sung đường đi thứ hai .............43

4.3.6. Kết quả áp dụng cho nhiều cặp nguồn đích, sử dụng bộ dữ liệu khơng
có liên kết mặt đất ..............................................................................................45
4.3.7. Kết quả sử dụng bộ dữ liệu bổ sung các liên kết mặt đất giữa các FSO
nguồn tại các cụm lân cận: .................................................................................47
CHƯƠNG V: KẾT LUẬN........................................................................................49
5.1.

KẾT QUẢ ĐẠT ĐƯỢC ..............................................................................49

5.2.

CÁC ĐIỂM HẠN CHẾ ...............................................................................49


5.3.

HƯỚNG PHÁT TRIỂN ..............................................................................50

5.4.

KẾT LUẬN CHUNG ..................................................................................50

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

5


TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ

Đề tài: Thiết kế topo cho mạng lưới không gian tự do
Tác giả luận văn: Nguyễn Mạnh Tiến
Khóa: CH2016B
Người hướng dẫn: PGS.TS Trương Thị Diệu Linh
Từ khóa: FSO, HAP, Suurballe, Dijkstra
Mục đích nội dung của luận văn
- Xây dựng phương án, giải pháp dự phịng khi có tình huống gián đoạn đường
truyền
- Thiết kế Topo mạng đáp ứng giải pháp dự phòng nêu trên, với các yêu cầu về
băng thông, độ phủ và tỷ lệ lỗi nằm trong giới hạn cho phép
Các nhiệm vụ cụ thể của luận văn
- Tìm hiểu lý thuyết cơ bản của truyền thơng quang khơng dây FSO.
- Tìm hiểu các phương pháp giải quyết bài toán đặt ra.
- Đề xuất giải pháp cho bài toán thiết kế topo đáp ứng khả năng dự phịng cho mạng

quang khơng dây.
- Cài đặt và đánh giá hiệu quả của giải thuật đề xuất.

Nội dung tóm tắt:
Truyền thơng quang khơng dây (FSO) là cơng nghệ truyền dẫn tín hiệu quang
qua mơi trường vô tuyến (không gian tự do). Trong những năm gần đây, truyền thông
quang không dây đang được xem như một giải pháp hứa hẹn thay thế cho các kết nối
vô tuyến băng rộng nhờ các ưu điểm mà nó có được bao gồm: tốc độ cao, chi phí hiệu
quả, khơng yêu cầu cấp phép tần số, triển khai nhanh và linh hoạt.
Với những ưu điểm trên, hệ thống mạng truyền thông quang không dây đang
được triển khai bởi rất nhiều các công ty truyền thông lớn trên thế giới: SpaceX,
Facebook, Google,…Ở Việt Nam, vị trí địa lý gần biển, thường xảy ra thiên tai lũ lụt,
cũng như địa hình tổng thể có nhiều khu vực đồi núi, hiểm trở, cho nên việc nghiên
cứu, phát triển áp dụng công nghệ truyền thơng quang khơng dây trong tương lai có
thể là một hướng đi phù hợp
Truyền thông quang không dây dựa trên quy tắc tầm nhìn thẳng: Light Of
Sight (LOS) , tuy nhiên, bên cạnh những ưu điểm, hệ thống mạng truyền thông quang
6


không dây cũng gặp phải những thách thức cần phải vượt qua đó là giới hạn khoảng
cách truyền, chịu ảnh hưởng mạnh của yếu tố tác động của môi trường truyền lan
khơng gian như mưa, sương mù, khói, bụi, tuyết… và đặc biệt là sự nhiễu loạn khơng
khí.
Trong việc triển khai mạng quang khơng dây, để khắc phục các khó khăn trong
việc triển khai các thiết bị FSO trên mặt đất như đồi núi hiểm trở, thiên tai lũ lụt, …
thì việc sử dụng các thiết bị HAP trở nên rất quan trọng. HAP (High Altitude
Platform) là một vật thể bay gần như cố định, cung cấp một số dịch vụ cho một khu
vực rộng lớn, nằm ở độ cao hàng chục km trên không trong một khoảng thời gian dài.
Một HAP thường hoạt động thiết kế hoạt động ở độ cao 17-22km và có thể hoạt động

trong khoảng 3-4 giờ, thậm chí là một ngày.
Tuy nhiên với việc ảnh hưởng của các yếu tố môi trường như nhiễu loạn khơng
khí, mây, mưa, sương mù, … thì việc một đường truyền dữ liệu đang hoạt động ổn
định bị gián đoạn là có thể xảy ra, do đó đặt ra vấn đề là cần có các đường truyền dữ
liệu dự phịng. Mục tiêu nghiên cứu của luận văn là thiết kế các topo mạng, các vị trí
đặt HAP để có thể đảm bảo tính dự phịng của mạng quang khơng dây.
Trong luận văn, tác giả trình bày những lý thuyết cơ bản của truyền thông
quang không dây FSO, hạ tầng mạng trên cao, các ưu điểm và nhược điểm của hệ
thống. Ngồi ra, tác giả cũng trình bày thuật tốn phân cụm, tìm đường, các giải thuật
được áp dụng để xây dựng topo mạng có tính dự phịng cao.
Để giải quyết bài toán luận văn đưa ra, tác giả đề xuất giải pháp gồm các vấn
đề chính sau:
Thực hiện phân cụm các thiết bị FSO trên mặt đất, trong đó mỗi cụm
sẽ có 1 HAP thực hiện việc truyền dữ liệu tới các thiết bị trong cụm.
Thực hiện giải thuật Suurballe có chỉnh sửa, bổ sung điều kiện để tìm
đường đi có dự phịng.
Thực hiện bổ sung các thiết bị HAP theo phương pháp hình học Euclid,
để xác định tọa độ lắp đặt các thiết bị trên đường đi.
Sử dụng giải thuật Dijkstra có chỉnh sửa để xác định đường đi tối ưu
cần thiết lập, bổ sung.
Bổ sung các liên kết trên mặt đất giữa các thiết bị nguồn (đích) trên các
cụm lân cận (với điều kiện ràng buộc là khoảng cách cho phép và có thể lắp đặt), mục
đích để tái sử dụng lại đường đi từ các thiết bị trong cụm lân cận, giảm bớt số lượng
HAP cần bổ sung.
Phần cuối cùng tác giả đưa ra các mơ hình thử nghiệm, các giá trị đầu vào để
có thể đánh giá, nhận xét tính khả thi, mức độ tối ưu và các hướng phát triển tiếp theo.
Dựa vào kết quả thử nghiệm các bộ dữ liệu, với hiệu quả rõ rệt, tác giả đề xuất bổ
sung thêm các liên kết chéo giữa các thiết bị FSO tại các cụm lân cận trên mặt đất, để
7



tận dùng đường đi đã có sẵn, giảm thiểu chi phí vận hành và số lượng thiết bị cần lắp
đặt.
Kết quả đạt được:
Trong quá trình nghiên cứu hệ thống truyền thơng khơng dây FSO, xây dựng
topo mạng có tính dự phịng, tác giả đã hồn thành được các mục tiêu của luận văn,
cụ thể là:
- Tìm hiểu lý thuyết cơ bản về hệ thống truyền thông quang không dây, đặc
điểm và cấu trúc của các thiết bị HAP, cơ chế hoạt động, phối hợp của các HAP và
các thiết bị FSO.
- Tìm hiểu về các cơ chế dự phịng trong việc truyền thơng quang khơng dây,
nghiên cứu các thuật tốn và đề xuất chỉnh sửa, bổ sung như Dijkstra, Suurballe, KMean, …
- Đề xuất thuật toán cho bài toán thiết kế topo đáp ứng khả năng dự phòng
cho mạng quang không dây.
- Đề xuất giải pháp bổ sung các HAP trên khơng gian, đáp ứng u cầu dự
phịng và tối thiểu các HAP cần sử dụng.
- Đề xuất giải pháp sử dụng các liên kết mặt đất trong điều kiện cho phép, để
tăng hiệu quả thuật toán trong việc bổ sung các HAP.
- Cài đặt và đánh giá hiệu quả của giải thuật đề xuất.
Trong phạm vi luận văn, tác giả đã trình bày giải thuật xây dựng topo mạng
có dự phịng, với đặc tính áp dụng các thuật tốn tìm đường có chỉnh sửa: Dijkstra,
Suurballe, thuật tốn phân cụm KMean, … cũng như đề xuất phương pháp hình học
Euclid để xác định tọa độ các thiết bị HAP, phương pháp bổ sung liên kết giữa các
thiết bị FSO trên mặt đất.
Với việc áp dụng giải thuật trong luận văn, với bài tốn sử dụng nhiều cặp
nguồn đích, thì việc bổ sung HAP cho các đường đi của các cặp nguồn đích sau, có
thể tái sử dụng được các HAP đã xây dựng trước đó, nên có thể tối thiểu chi phí lắp
đặt và triển khai các HAP.

8



DANH MỤC HÌNH ẢNH
STT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

27

Hình ảnh
Trang
Hình 1: Mơ hình mạng quang khơng dây
11
Hình 2: Mơ hình truyền dữ liệu quang khơng dây
15
Hình 3: Mơ hình hệ thống truyền thơng quang khơng dây FSO
16
Hình 4: Hệ thống HAP – High Altitude Platform
18
Hình 5: Hệ thống nhiều HAP
18
Hình 6: Ảnh hưởng của mơi trường tới hệ thống FSO
19
Hình 7: Mơ hình thuật tốn K-Mean có bổ sung
20
Hình 8: Kiến trúc bảo vệ mạng
21
Hình 9: Dự phịng theo vịng
22
Hình 10: Dự phịng tuyến tính
23
Hình 11: Dự phịng dành riêng và dự phịng chia sẻ
23
Hình 12: Tìm đường có dự phịng theo thuật tốn Suurballe
25
Hình 13: Sơ đồ tổng qt thuật tốn
30

Hình 14: Thuật tốn phân cụm có điều chỉnh các điều kiện
32
Hình 15: Giải thuật tìm đường đi có dự phịng
34
Hình 16: Thuật tốn bổ sung các HAP trung gian
36
Hình 17: Kết quả phân cụm với 4 Cluster của 300 thiết bị FSO
38
Hình 18: Kết quả phân cụm với 4 Cluster trên hai vùng độc lập
39
Hình 19: Mơ hình giả lập phân cụm bổ sung các liên kết giữa các cụm kề nhau
40
Hình 20: Sử dụng thuật toán xây dựng đường đi, xác định được đường đi chính
41
Hình 21: Đường đi chính và dự phịng
42
Hình 22: Danh sách các HAP khi thực hiện hai lần cho hai cặp nguồn – đích
43
Hình 23: Mơ hình mạng cho hai cặp nguồn đích
43
Hình 24: Mơ hình mạng cho ba cặp nguồn đích
44
Hình 25: Đồ thị đánh giá số lượng HAP cần bổ sung theo số lượng cặp FSO
46
nguồn – đích
Hình 26: Đường đi của hai cặp nguồn – đích trong trường hợp sử dụng liên kết
47
mặt đất giữa hai cụm kề nhau
Hình 27: Đồ thị đánh giá số lượng HAP cần bổ sung theo số lượng cặp FSO
47

nguồn – đích trong trường hợp bổ sung các liên kết mặt đất

9


DANH MỤC TỪ VIẾT TẮT VÀ THUẬT NGỮ
FSO
BER
LOS
𝐵𝐸𝑅𝑒2𝑒
FEC
ILP
API

Free Space Optics
Bit Error Rate
Line Of Sight
Bit Error Rate end-to-end
Forward Error Correction
Interger Linear Programing
Application Program Interface

Mạng quang khơng dây
Tỷ lệ lỗi Bit
Tầm nhìn thẳng
BER từ điểm đầu đến điểm cuối
Kỹ thuật sửa lỗi hướng đi
Chương trình quy hoạch tuyến tính
Giao diện chương trình ứng dụng


DANH MỤC BẢNG

STT
1
2

Tên
Bảng 1: Số HAP cần bổ sung theo số cặp nguồn đích
với bộ dữ liệu khơng sử dụng liên kết mặt đất
Bảng 2: Số HAP cần bổ sung theo số cặp nguồn đích
với bộ dữ liệu bổ sung liên kết mặt đất

Trang
46
47

10


MỞ ĐẦU
Lý do chọn đề tài:
Mạng Internet phát triển kéo theo các yêu cầu về băng thông, tốc độ đường truyền
ngày càng cao. Chính vì vậy, việc truyền thơng qua cáp quang đang dần được phổ
biến. Tuy nhiên, những khó khăn trong việc triển khai hệ thống dây cáp, các nguy
hiểm trong quá trình triển khai đối với người thực hiện, tại các quốc gia thường xuyên
xảy thiên tai động đất, lũ lụt như Hàn Quốc, Nhật Bản, Mỹ, Việt Nam, …việc triển
khai cũng như khắc phục sau thiên tai là vơ cùng khó khăn và phức tạp. Ngồi những
khó khăn trên, có những lý do ngẫu nhiên khiến dây cáp bị đứt, ngồi tầm kiểm sốt
Truyền thơng quang khơng dây: Free Space Optics (FSO) ra đời nhằm khắc phục
được những nhược điểm của việc truyền dữ liệu thông qua cáp quang nhưng vẫn có

thể đảm bảo được yêu cầu đường truyền. Truyền thông quang không dây (FSO-Free
Space Optical) là một hệ thống bao gồm hai thiết bị đặt tại vị trí có thể nhìn thấy nhau
theo đường thẳng, khoảng cách giữa hai thiết bị có thể lên đến hàng trăm hay hàng
nghìn mét, là một bước đi mới, nhằm cải thiện, giải quyết những nhược điểm của
truyền thông cáp quang, vẫn đảm bảo những yêu cầu về chất lượng của đường truyền.
Việc triển khai một hệ thống FSO là tương đối đơn giản và nhanh chóng do các thiết
bị quang không dây đều nhỏ gọn, dễ dàng di chuyển. Ưu điểm nổi trội của truyền
quang không dây đối với truyền cáp quang là các thiết bị quang không dây kết nối
qua mơi trường khơng khí.
Trong những năm gần đây, truyền thông quang không dây đang được xem như
một giải pháp hứa hẹn thay thế cho các kết nối vô tuyến băng rộng nhờ các ưu điểm
mà nó có được bao gồm: tốc độ cao, chi phí hiệu quả, khơng yêu cầu cấp phép tần số,
triển khai nhanh và linh hoạt.
Truyền thông quang không dây kết hợp hạ tầng mạng trên cao là việc kết hợp
giữa các thiết bị truyền thông quang không dây FSO đặt trên các thiết bị bay trên
không, kết nối với các thiết bị truyền thông quang dưới mặt đất tạo ra một mơ hình
truyền thơng quang. Mơ hình này hiện nay được triển khai bởi nhiều công ty lớn trên
thế giới: SpaceX, Google, Facebook, ...
Hạ tầng mạng trên cao (HAP-High Altitude Platform) là tập hợp những vật thể
bay trên không, thường nằm ở độ cao 20km, gắn các thiết bị truyền thông không dây.
Các thiết bị này liên kết với nhau tạo ra các hệ thông mạng, bao phủ một khu vực
rộng lớn. Các HAP có thể hoạt động trong một khoảng thời gian trung bình khoảng
5 giờ. Các vật thể bay này có thể là các máy bay, khinh khí cầu, …

Luận văn có các nhiệm vụ tổng quan như sau:
-

Xây dựng phương án, giải pháp dự phịng và tái cấu hình khi có tình huống
gián đoạn đường truyền
11



-

Thiết kế Topo mạng đáp ứng giải pháp dự phòng nêu trên, với các yêu cầu về
băng thông, độ phủ và tỷ lệ lỗi nằm trong giới hạn cho phép

Bố cục luận văn
Luận văn được chia ra làm 5 chương cụ thể như sau:
CHƯƠNG 1: Giới thiệu chung về đề tài và hướng giải quyết
Đặt vấn đề và nêu ra hướng giải quyết của luận văn
CHƯƠNG 2: Cơ sở lý thuyết
Trình bày những khái niệm cơ bản về truyền thơng quang khơng dây, mơ
hình cơ bản của hệ thống quang khơng dây. Mơ hình hệ thống HAP. Các thuật tốn
phân cụm, tìm đường, tối ưu hóa, …
CHƯƠNG 3: Xây dựng giải thuật thiết lập topo mạng
Xây dựng bài toán đề tài, hướng giải quyết. Xây dựng mơ hình hệ thống,
chương trình. Triển khai các thuật tốn trên để xây dựng hệ thống mạng.
CHƯƠNG 4: Cài đặt thuật toán và kết quả thực hiện
Các kết quả thu được sau khi viết chương trình triển khai các thuật tốn
trên. Nhận xét và phân tích các kết quả đạt được
CHƯƠNG 5: Kết luận
Sau khi hoàn thành luận văn, tác giả đưa ra một vài kết luận về công việc
đã làm, đưa ra định hướng phát triển vấn đề.

12


CHƯƠNG I: GIỚI THIỆU CHUNG VỀ ĐỀ TÀI VÀ HƯỚNG GIẢI
QUYẾT

1.1.

ĐẶT VẤN ĐỀ

Ngày nay tại một số nước phát triển, hệ thống truyền quang không dây đã được
đưa vào thử nghiệm và lắp đặt cho nhiều tập đoàn lớn, mang lại hiệu quả đáng kể.
Tại Việt Nam do giá thành thiết bị tương đối lớn, cơ sở hạ tầng chưa thực sự phát
triển nên các hệ thống quang không dây còn chưa phổ biến. Tuy nhiên, trong thời
gian tới, với những ưu điểm nổi trội thì hệ thống này sẽ dần trở nên phổ biến.
Truyền quang không dây truyển đổi dữ liệu từ tín hiệu điện sang tín hiệu quang
và thực hiện q trình truyền dữ liệu, sử dụng sóng ánh sáng để truyền dữ liệu, truyền
trong môi trường không khí. Do truyền dữ liệu qua khơng khí, việc lắp đặt hệ thống
FSO được thực hiện dễ dàng, nhanh chóng, q trình truyền dữ liệu khơng bị ảnh
hưởng bởi sự cố đứt cáp. Với những ưu điểm trên, hệ thống mạng quang khơng dây
dễ dàng phục hồi tình trạng mạng cho những khu vực sau thảm họa thiên tai, cũng
như việc triển khai hệ thống mạng cho các khu vực xa xơi hẻo lánh, địa hình hiểm
trở, …

Hình 1: Mơ hình mạng quang khơng dây
Để xây dựng một hệ thống truyền thông không dây trên một khu vực rộng lớn,
hiểm trở cần có sự kết hợp của nhiều thiết bị HAP lắp đặt trên không gian, ở các độ
13


cao lớn (20 km) với các thiết bị FSO mặt đất (Ground node) như hình 1. Tuy nhiên
do giá thành các thiết bị bay khá lớn, và độ phủ của các thiết bị FSO trên HAP cũng
chỉ có thể phủ một diện tích nhất định (độ mở thiết bị phát là 25o, tại độ cao h=20 km
thì bán kính phủ là 30 km (theo tài liệu ITU [2]), do đó cũng khơng thể lắp đặt q ít.
Do đó phát sinh yêu cầu xây dựng topo mạng truyền thông không dây với các điểm
đặt các HAP bổ sung.

Trong quá trình hoạt động của hệ thống truyền thông không dây FSO, do các
điều kiện mơi trường như mây, nhiễu loạn khơng khí, … thì đường truyền dữ liệu bị
gián đoạn, nên cần thiết kế topo mạng có tính dự phịng cao.
Bài tốn được đặt ra như sau: Giả sử có một số điểm trên mặt đất cần truyền
dữ liệu cho nhau, các điểm này được trang bị các thiết bị quang không dây FSO. Các
điểm cho trước này ở cách xa nhau và không thể truyền dữ liệu trực tiếp hay qua các
điểm trung gian trên mặt đất, do đó để truyền dữ liệu giữa các điểm nguồn-đích ta
cần sử dụng các thiết bị HAP trên không trung làm điểm chuyển tiếp dữ liệu. Các
thiết bị HAP này sẽ giao tiếp với nhau và giao tiếp với các thiết bị FSO trên mặt đất
– Ground node. Giữa các cặp nguồn-đích ln có hai đường truyền dữ liệu: đường
chính và đường dự phịng để đảm bảo kết nối dữ liệu luôn liên tục và ổn định.
Bài tốn được cho trước các thơng tin sau:
Cho trước số Ground node tối đa và vị trí các điểm đặt thiết bị FSO
dưới mặt đất.
Cho trước độ cao các HAP được hoạt động.
Cho trước băng thông tối đa của HAP cung cấp cho các thiết bị FSO
dưới mặt đất.
Cho trước ma trận thông lượng M (trong điều kiện bài tốn, tác giả thiết
lập thơng lượng giữa các liên kết là bằng nhau và nhỏ hơn băng thông tối đa truyền
giữa các thiết bị)
Cho trước các cặp nguồn-đích cần truyền dữ liệu
Yêu cầu đặt ra
Truyền dữ liệu giữa các cặp ground node ở xa, thông qua các HAP
Đảm bảo băng thông giữa từng HAP với cụm FSO trên mặt đất luôn
nằm trong giới hạn băng thông của HAP.
Đảm bảo đạt các yêu cầu của ma trận thông lượng
Tỷ lệ lỗi BERe2e<𝛿
Ràng buộc:
Có một số hữu hạn các ground nodes có kết nối đường truyền trên mặt
đất với nhau.

14


Mỗi HAP thì có thể phủ một vài Ground nodes trong một phạm vi nhất
định bán kính R.
Giả thiết đường truyền từ 1 HAP xuống một cụm node có thể trên mặt
đất bị gián đoạn do thời tiết hoặc môi trường truyền, hoặc có vật thể che khuất
Tổng số thiết bị HAP sử dụng nhỏ hơn số lượng tối đa MHAP cho phép
Do chi phí lắp đặt và vận hành các HAP lớn hơn nhiều với thiết bị FSO,
nên giải thuật bài toán đưa ra sẽ chú trọng vào tiêu chí giảm thiểu số lượng HAP cần
lắp đặt, khơng thực hiện ràng buộc số FSO.
Nhiệm vụ luận văn
Xây dựng phương án, giải pháp dự phịng khi có tình huống gián đoạn
đường truyền
Thiết kế Topo mạng đáp ứng giải pháp dự phịng nêu trên, với các u
cầu về băng thơng, độ phủ và tỷ lệ lỗi nằm trong giới hạn cho phép

1.2.

ĐỊNH HƯỚNG GIẢI QUYẾT

Bài toán nêu trên là một bài tốn phức tạp, có nhiều ràng buộc, đặc biệt là việc
cần thiết kế một topo mạng có tính dự phịng cao. Để giải quyết vấn đề trên, tác giả
phải lần lượt nghiên cứu và giải quyết các bài toán nhỏ hơn, cụ thể như sau:
Do phải truyền dữ liệu từ các điểm xa nhau, khơng có kết nối trực tiếp,
nên cần phải sử dụng các HAP làm điểm truyền dữ liệu trung gian. Từ đó phát sinh
vấn đề xác định tọa độ của các HAP để số lượng HAP là nhỏ nhất (mục đích là tiết
kiệm chi phí lắp đặt, triển khai các HAP). Chính vì thế cần phải nghiên cứu và áp
dụng mơ hình phân cụm dữ liệu.
Để xác định đường truyền dữ liệu từ điểm nguồn tới điểm đích, tác giả

cần nghiên cứu và áp dụng các giải thuật tìm đường để xác định đường đi ngắn nhất,
với ràng buộc là tỷ lệ lỗi trên tồn trình BERe2e nằm trong phạm vi cho phép.
Với yêu cầu topo mạng phải có tính dự phịng, tác giả cần nghiên cứu
các cơ chế dự phòng của mạng, theo đường và theo đoạn để có thể xây dựng giải
thuật tối ưu.
Với các HAP hiện có sau q trình phân cụm, việc có đủ cả đường
truyền dữ liệu chính và dự phịng có thể khơng được thỏa mãn, do đó tác giả cần
nghiên cứu thêm giải thuật bổ sung các HAP vào topo mạng để có thể thỏa mãn u
cầu dự phịng cao.
Để giải quyết bài toán phân cụm, tác giả sử dụng thuật tốn K-mean có chỉnh
sửa để thực hiện tìm tọa độ các HAP cần bổ sung
Để thực hiện bài toán tìm đường, có dự phịng và thỏa mãn các điều kiện ràng
buộc, tác giả sử dụng thuật tốn Suurballe có chỉnh sửa để thực hiện tìm đường đi có
dự phịng theo đường.
15


Ngồi ra, tác giả cịn sử dụng thuật tốn Dijkstra có chỉnh sửa, để xác định
đường đi ngắn nhất và khoảng cách tối thiểu tới điểm đích.
Với vấn đề bổ sung các HAP để đảm bảo tính dự phịng, tác giả sử dụng
phương pháp hình học Euclid để xác định tọa độ các HAP cần bổ sung trong quá trình
xây dựng topo mạng.
Trong q trình xây dựng thuật tốn, tác giả đề xuất phương pháp sử dụng các
liên kết mặt đất (có dây hoặc khơng dây) giữa các thiết bị FSO nguồn/đích trong các
cụm lân cận, trong điều kiện cho phép về khoảng cách và khả năng lắp đặt.
Mục đích của phương pháp trên là sử dụng các đường truyền mặt đất (nếu có)
để truyền dữ liệu sang cụm bên cạnh, tái sử dụng đường đi sẵn có của các thiết bị
FSO khác tại cụm lân cận, giảm bớt số HAP cần xây dựng.
Để xây dựng các liên kết giữa các thiết bị FSO nguồn (đích) tại hai cụm lân
cận, tác giả tạo các kết nối 1-1 giữa các FSO nguồn (đích) tại hai cụm. Giới hạn số

kết nối là số FSO nguồn (đích) nhỏ nhất của các cụm.
Để đánh giá thuật toán, tác giả đề xuất sử dụng hai bộ dữ liệu
- Bộ dữ liệu tổng quát: Trong đó các thiết bị FSO trên mặt đất khơng có liên
kết với nhau
- Bộ dữ liệu có liên kết chọn lọc: Các FSO đóng vai trị thiết bị nguồn hoặc
đích tại các cụm lân cận sẽ có liên kết 1-1 với nhau (từng cặp liên kết), trong giới hạn
về khoảng cách.

16


CHƯƠNG II: CƠ SỞ LÝ THUYẾT
2.1 HỆ THỐNG QUANG KHÔNG DÂY
Truyền quang qua không gian tự do (FSO) hay giao tiếp quang không dây
được giới thiệu lần đầu bởi Alexander Graham Bell ở cuối thế kỷ 19. Thí nghiệm
FSO của Bell đó là ơng đã chuyển đổi tín hiệu âm thanh (giọng nói) thành tín hiệu
điện thoại và phát chúng giữa các bộ thu phát qua không gian tự do dọc theo một
luồng sáng trong khoảng cách khoảng 183m. Thiết bị thí nghiệm của ơng được gọi là
“photophone”, Bell coi trọng công nghệ quang này hơn là điện thoại – phát minh vĩ
đại của ơng vì cơng nghệ này khơng cần đến dây dẫn cho việc truyền tín hiệu.
Truyền thơng không dây là công nghệ sử dụng sự lan truyền ánh sáng trong
không gian để truyền dữ liệu. Đây là cơng nghệ truyền thơng băng thơng rộng tầm
nhìn thẳng: Line of Sight (LOS), trong đó ánh sáng được truyền trực tiếp thơng qua
khơng khí. Các chùm sáng trong hệ thống FSO được truyền bởi ánh sáng laser tập
trung vào vùng phát hiện photon có độ nhạy cao.
Hệ thống quang khơng dây cung cấp khả năng truyền tải từ 100 Mbps đến 2,5
Gbps, tầm hoạt động với từ vài trăm mét đến vài kilomet. Điểm cốt lõi trong hệ thống
FSO là giữa đường truyền của hai thiết bị khơng có vật cản (Line of sight). Hệ thống
FSO hoạt động với bước sóng 1550nm, mắt người ít bị ảnh hưởng bởi bước sóng này,
và bước sóng này ít chịu ảnh hưởng của bức xạ mặt trời và tương thích với cơ sở hạ

tầng hiện nay.
Việc truyền dữ liệu bằng công nghệ FSO được thực hiện khá đơn giản. Hệ
thống bao gồm hai thiết bị có nhiệm vụ truyền và nhận tín hiệu quang. Mỗi thiết bị
sử dụng nguồn phát ánh sáng (thường là ánh sáng laser) để phát tín hiệu và một thấu
kính để thu nhận tín hiệu. Kênh truyền tín hiệu là mơi trường khơng khí bên ngồi.
Chùm sáng được phát ra để truyền tín hiệu là chùm sáng phân kỳ, dạng hình nón, có
góc mở rộng hẹp, cỡ vài mrad

Hình 2: Mơ hình truyền dữ liệu quang khơng dây
17


Các đặc điểm cơ bản của hệ thống FSO như sau:
• Băng thơng điều chế rộng.
• Búp sóng hẹp.
• Khơng yêu cầu cấp phép phổ tần.
• Hệ thống triển khai dễ dàng, nhanh chóng
• Phụ thuộc vào các điều kiện mơi trường.

Ngồi các điểm trên, các đặc điểm khác của FSO bao gồm:
• Lợi ích từ truyền thơng sợi quang hiện tại.
• Khơng bị ảnh hưởng của nhiễu điện từ.
• Khơng giống như hệ thống có dây, FSO là một hệ thống khơng cố định có
thể thu hồi tài sản.
• Phát xạ phải nằm trong giới hạn an toàn quy định.
• Trọng lượng nhẹ và nhỏ gọn.
• Tiêu thụ điện năng thấp.
• u cầu tầm nhìn thẳng và liên kết chặt chẽ như là một kết quả của việc
búp sóng hẹp.


2.2 MƠ HÌNH HỆ THỐNG FSO
Giống như các hệ thống truyền thông khác, hệ thống FSO gồm 3 phần: Bộ
phát, kênh truyền và bộ thu:

Hình 3: Mơ hình hệ thống truyền thông quang không dây FSO

18


Bộ phát tín hiệu:
Bộ phát tín hiệu có nhiệm vụ chính là chuyển đổi tín hiệu điện thành tín hiệu
quang, sau đó truyền qua kênh truyền tới bộ thu. Phương thức điều chế được sử dụng
rộng rãi tại bộ phát là điều chế cường độ, trong đó cường độ phát xạ của nguồn quang
sẽ được điều chế bởi số liệu cần truyền đi. Bộ phát tín hiệu bao gồm bộ điều chế,
mạch điều khiển, nguồn quang, bộ phát tín hiệu.
Kênh truyền:
Trong hệ thống quang khơng dây, kênh truyền tín hiệu là mơi trường khơng
khí. Tín hiệu chịu ảnh hưởng, hao tổn bởi các yếu tố mơi trường. Ngồi ra, tín hiệu
còn chịu ảnh hưởng bởi các hiện tưởng hấp thụ, tán xạ.
Bộ thu tín hiệu:
Bộ thu tín hiệu có nhiệm vụ chính là thu, lọc, khơi phục tín hiệu được phát đi
từ bộ phát, chuyển đổi tín hiệu quang thu được sang tín hiệu điện. Các tín hiệu sau
khi được chuyển đổi sẽ được chuyển tới các thiết bị đầu cuối. Bộ thu bao gồm bộ thu
tín hiệu quang, bộ lọc tín hiệu, bộ tách sóng và bộ giải điều chế.

2.3 HỆ THỐNG HẠ TẦNG MẠNG TRÊN CAO HAP
High-altitude platform (HAPs) là những máy bay, khinh khí cầu được đặt ở
độ cao trên 20km, trong tầng bình lưu của khí quyển, được sử dụng để thiết lập một
mạng viễn thông hoặc thực hiện viễn thám phục vụ người dân hay quân đội. Nó có
thể là máy bay, tàu bay hoặc khí cầu, có người lại hoặc khơng có người lái.

HAP hoạt động trong tầng bình lưu, nơi mà nhiệt độ giảm dần theo độ cao,
HAP nằm ngay trên đỉnh của tầng đối lưu, nơi mà nhiệt độ duy trì ở -60oC, tầng bình
lưu bắt đầu ở độ cao 7km ở các địa cực và 18km ở xích đạo, cho đến độ cao 50km.
Trong luận văn, tác giả giả thiết độ cao của HAP nằm ở độ cao 20km, tại độ
cao này, tốc độ gió là khơng đáng kể nên các HAP khơng tốn nhiều năng lượng để
duy trì vị trí. Một thế mạnh quan trọng khác là độ bao phủ rộng cho việc truyền thông
cũng như nằm trên độ cao thương mại.

19


Hình 4: Hệ thống HAP – High Altitude Platform
Trong trường hợp sử dụng nhiều HAP, khi các thiết bị FSO trên mặt đất muốn
kết nối với nhau, thì thiết bị nguồn sẽ truyền dữ liệu lên HAP tương ứng trên không
gian của cụm mặt đất, rồi các thiết bị FSO trên các HAP sẽ truyền dữ liệu cho nhau
rồi truyền tới thiết bị FSO đích trên mặt đất.

Hình 5: Hệ thống nhiều HAP
20


FSO là một cơng nghệ tầm nhìn thẳng nên các điểm kết nối buộc phải nhìn
thấy nhau. Hơn nữa, khi ánh sáng truyền qua khơng gian, nó phải đối mặt với các
thách thức lớn do sự thay đổi của bầu khí quyển như: sương mù, mưa tuyết, sự ơ
nhiễm, sự hấp thụ, sự tán xạ, sự nhiễu loạn, vật cản vật lý hay sự lệch hướng phát thu
khi tòa nhà dao động…
Trong thực tế chất lượng các liên kết FSO phụ thuộc khá nhiều vào điều kiện
thời tiết. Các liên kết FSO sẽ chịu suy hao đường truyền trong các điều kiện như mưa,
sương mù, tuyết.


Hình 6: Ảnh hưởng của môi trường tới hệ thống FSO

2.4 PHÂN CỤM FSO SỬ DỤNG THUẬT TOÁN K-MEAN
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các
phương pháp Unsupervised Learning trong Machine Learning. Có rất nhiều định
nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể hiểu phân cụm là các
qui trình tìm cách nhóm các đối tượng đã cho vào các cụm (clusters), sao cho các đối
tượng trong cùng 1 cụm tương tự (similar) nhau và các đối tượng khác cụm thì khơng
tương tự (Dissimilar) nhau.
K-Means là thuật tốn rất quan trọng và được sử dụng phổ biến trong kỹ thuật
phân cụm. Tư tưởng chính của thuật tốn K-Means là tìm cách phân nhóm các đối
tượng (objects) đã cho vào K cụm (K là số các cụm được xác đinh trước, K nguyên
dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm nhóm
(centroid) là nhỏ nhất.

21


Khởi tạo n tâm cụm
ngẫu nhiên

Gán các node vào
cụm gần nhất

No

Tính lại tọa độ tâm
cụm

Các cụm ổn định, khơng

thay đổi

Yes

Hình 7: Mơ hình thuật tốn K-Mean
Trong việc phân cụm thơng qua thuật toán K-mean, việc xác định số cụm K
rất quan trọng, có nhiều phương pháp sử dụng xác định số cụm như phương pháp
elbow, … Trong luận văn tác giả dựa vào các điều kiện ràng buộc để xác định số
cụm:
-

Số thiết bị FSO tối đa trong một cụm
Số cụm là số tối thiểu để giảm chi phí lắp đặt, duy trì và thiết bị

Khi áp dụng mơ hình thuật toán K-mean vào việc phân cụm các thiết bị FSO
dưới mặt đất, tác giả đưa thêm các điều kiện ràng buộc để giải quyết yêu cầu luận
văn:
Điều kiện 1: Giả thiết rằng các liên kết từ thiết bị FSO dưới mặt đất tới HAP
có băng thơng tối đa là bằng nhau và mỗi HAP chỉ cung cấp một ngưỡng băng thông
nhất định. Theo tài liệu ITU [2], tại độ cao 20km, khẩu độ mở của thiết bị FSO đặt
trên HAP là 25o, thì băng thơng tối đa cho mỗi liên kết với các thiết bị FSO dưới mặt
22


đất là 2Mb/s đến 45Mb/s. Vì thế trong luận văn, để thử nghiệm tác giả chọn băng
thông tối đa cho mỗi liên kết là 10Mb/s, giới hạn băng thông cho tổng băng thông
liên kết từ các thiết bị FSO tới HAP là 1000Mb/s. Với lựa chọn này, tổng số thiết bị
FSO trong một cụm không vượt quá 100 thiết bị.
Điều kiện 2: Trong luận văn, tác giả thử nghiệm với độ bao phủ của thiết bị
HAP là 30km, dựa trên tài liệu: ITU [2], tài liệu này khuyến khích một số tham số

triển khai HAP với khẩu độ mở của thiết bị FSO đặt trên HAP là 25o tại độ cao 20km,
thì bán kính bao phủ của HAP đặt tại tâm của khu vực là 30km.

2.5 CÁC PHƯƠNG PHÁP DỰ PHÒNG ĐƯỜNG ĐI
Trong việc thiết kế topo mạng, việc đưa ra các phương pháp dự phịng và khơi
phục là vơ cùng quan trọng, để đảm bảo tính ổn định của mạng lưới.
Các sự cố thường gặp trên đường truyền rất đa dạng, như đứt cáp, nhiễu tín
hiệu, ảnh hưởng bởi thời tiết: mây, mưa, sương mù, ... Các sự cố có thể xảy ra tại các
nút mạng, hoặc kết nối giữa các điểm với nhau. Có thể xảy ra lỗi đơn hoặc đồng thời
nhiều lỗi cùng lúc.
Các yếu tố đánh giá chất lượng mạng: Thời gian gián đoạn càng nhỏ càng tốt,
tính sẵn sàng của dịch vụ và khả năng duy trì dịch vụ khi xảy ra lỗi
Để xây dựng hệ thống mạng có tính dự phịng cao, cần có kế hoạch đối phó
với các lỗi có thể xảy ra, và bổ sung tính năng dự phịng tài ngun và lên phương án
khơi phục một cách nhanh chóng.
Các phương pháp bảo vệ mạng:

Hình 8: Kiến trúc bảo vệ mạng
23


Để dự phịng mạng lưới, có thể có các phương pháp dự phòng sau:
-

-

Dự phòng theo topo:
✓ Dự phòng vòng
✓ Dự phịng tuyến tính: Link, đoạn, đường
Dự phịng theo việc sử dụng tài nguyên:

✓ Dự phòng dành riêng
✓ Dự phòng chia sẻ
2.5.1 Dự phòng topo theo vòng
Các node được nối với nhau qua các link tạo thành vòng tròn, dữ liệu
được truyền ngược lại khi có sự cố:

Hình 9: Dự phòng theo vòng

24


2.5.2 Dự phịng tuyến tính:
Là dự phịng thiết kế theo đường thẳng, gồm 3 loại: link, đoạn, đường

Hình 10: Dự phịng tuyến tính
2.5.3. Dự phịng theo tài ngun:
- Dự phịng dành riêng: Một tài nguyên dự phòng chỉ được dùng để bảo vệ
một đường truyền chính
- Dự phịng chia sẻ: Một tài ngun dự phịng có thể được dùng trong nhiều
đường dự phịng để bảo vệ nhiều đường truyền chính
Thơng thường, dự phịng chia sẻ có tốc độ khơi phục chậm hơn dự phòng dành
riêng do mất thời gian thành lập đường dự phòng từ các tài nguyên dự phòng
khi sự cố xảy ra.

Hình 11: Dự phịng dành riêng và dự phòng chia sẻ
Với các phương pháp dự phòng như trên, áp dụng các yêu cầu, ràng buộc của
bài toán: Có thể xảy ra lỗi kết nối ở bất cứ điểm nào trên đường đi. Tác giả lựa chọn
25