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ế và tối ưu mạng truyền thơng quang
không dây trong không gian sử dụng hạ tầng
mạng trên cao (High Altitude Platform)

Sinh viên thực hiện : Vũ Phạm Minh Hiển
CBC17018
Giáo viên hướng dẫn: PGS.TS. Trương Thị Diệu Linh

HÀ NỘI 12-2017
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

1


PHIẾU GIAO NHIỆM VỤ LUẬN VĂN THẠC SĨ
1. Thông tin về sinh viên
Họ và tên sinh viên: Vũ Phạm Minh Hiển
Điện thoại liên lạc: 0979816380
Email:
Khóa: CLC2017B
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 –

Trường Đại học Bách Khoa Hà Nội.
Thời gian làm luận văn thạc sĩ: Từ ngày 26/07/2017 đến 26/12/2017
2. Mục đích nội dung của luận văn thạc sĩ:
Nghiên cứu mơ hình mạng truyền thông quang không dây trong không gian sử
dụng hệ thống hạ tầng mạng trên cao (High Altitude Platform). Xác định vị trí của
các HAP trên khơng, thiết kế topo mạng giữa các HAP.
3. Các nhiệm vụ cụ thể của luận văn thạc sĩ:
 Nhiệm vụ 1: Tìm hiểu các khái niệm về truyền thông quang không dây (FSO),
hạ tầng mạng trên cao (HAP): Cách thức hoạt động, sơ đồ mạng, các thiết bị
đi kèm, cách thức vận hành của thiết bị…
 Nhiệm vụ 2: Vận dụng thuật toán phân cụm K-mean, thuật tốn tìm đường
Dijkstra, thuật tốn Heuristic,…để thiết kế topo mạng giữa các HAP và phân
bố vùng bao phủ của các HAP.
4. Lời cam đoan của sinh viên:
Tôi – Vũ Phạm Minh Hiể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 26 tháng 12 năm 2017
Tác giả luận văn

Vũ Phạm Minh Hiể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 thạc sĩ và
cho phép bảo vệ:
Hà Nội, ngày 26 tháng 12 năm 2017
Giáo viên hướng dẫn

PGS.TS. Trương Thị Diệu Linh
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018


2


TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ
Ngày nay, với sự phát triển của cơng nghệ thơng tin nói chung và mạng
Internet nói riêng, người dùng có những yêu cầu cao hơn về tốc độ băng thông cũng
như đường truyền mạng. Với lý do trên, sử dụng cáp quang để trong truyền thông
đang trở nên phổ biến. Việc sử dụng cáp quang tồn tại những khó khăn trong việc
thiết lập mạng lưới dây cáp (đặc biệt là ở các vùng có địa hình phức tạp như đồi núi,
hải đảo…), các tác động của con người, thiên tai có thể ảnh hưởng đến đường dây
cáp. Việc phục hồi mạng cho các khu vực sau thảm họa thiên nhiên, cũng như việc
cung cấp dịch vụ mạng đến những vùng hẻo lánh, hải đảo trở nên dễ dàng hơn rất
nhiều với việc sử dụng hệ thống mạng quang không dây Free Space Optics kết hợp
sử dụng hạ tầng mạng trên cao (HAP- High Altitude Platform)
FSO là cơng nghệ truyền dẫn tín hiệu quang qua môi trường không gian. 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 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 việc triển khai hệ thống truyền quang không dây trên các khu
vực có địa hình đồi núi là vơ cùng khó khăn, hạn chế tầm nhìn bởi cây cối, chênh lệch
độ cao giữa các vị trí. Do đó, một giải pháp đưa ra là sử dụng các hạ tầng mạng trên
cao làm trung gian để truyền thông giữa các thiết bị FSO dưới mặt đất.

HAP (Hight Altitude Platform) là một vật thể bay gần như cố định, cung cấp
một số các 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.
Việc thiết kế hệ thống mạng trong trường hợp này là khó khăn, với nhiều ràng
buộc liên quan tới khoảng cách, băng thông sử dụng giữa các thiết bị. Mục tiêu nghiên
cứu của luận văn là xác định vị trí đặt các HAP và thiết kế topo mạng giữa các HAP
này.
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

3


Trong luận văn, tác giả sẽ tìm hiểu những lý thuyết cơ bản của truyền thông
quang không không dây (FSO), hạ tầng mạng trên cao (HAP), những khái niệm cơ
bản, sơ đồ hệ thống, những thuận lợi cũng như thách thức của hệ thống. Các thuật
tốn phân cụm, tìm đường, tối ưu hóa cũng sẽ được đề cập trong luận văn. Tiếp đó,
mục tiêu chính của luận văn sẽ là xác định vị trí đặt các HAP bằng cách phân cụm
các nút mạng dưới mặt đất, sau đó xây dựng hệ thống liên kết mạng giữa các HAP.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

4


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 suốt 5 năm học vừa qua.
Tiếp đó tơi xin được gửi lời cảm ơn tới các bạn trong lớp KSCLC-HTTT&TTK57 nói riêng và các bạn sinh viên trong trường nói chung vì đã đem đến cho tơi một
mơi trường học thân thiện và hòa đồng, giúp đỡ lẫn nhau cùng tiến bộ.
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 luôn ủ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, ngày 26 tháng 12 năm 2017

Vũ Phạm Minh Hiển

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

5


MỤC LỤC
PHIẾU GIAO NHIỆM VỤ LUẬN VĂN THẠC SĨ ...................................................2
TÓM TẮT NỘI DUNG LUẬN VĂN THẠC SĨ ........................................................3
LỜI CẢM ƠN .............................................................................................................5
MỤC LỤC ...................................................................................................................6
DANH MỤC HÌNH ẢNH ..........................................................................................8
DANH MỤC TỪ VIẾT TẮT, THUẬT NGỮ ............................................................9
CHƯƠNG 1: GIỚI THIỆU CHUNG VỀ ĐỀ TÀI VÀ HƯỚNG GIẢI QUYẾT .....12
1.1. Đặt vấn đề ....................................................................................................12
1.2. Định hướng giải quyết .................................................................................13
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT .........................................................................15
2.1. Hệ thống quang khơng dây ..........................................................................15

2.2. Mơ hình hệ thống FSO ................................................................................16
2.3. Hệ thống hạ tầng mạng trên cao HAP .........................................................17
2.4. Phân cụm nút mạng bằng thuật toán K-mean ..............................................20
2.4.1. Tổng quan về thuật toán K-mean – Các khái niệm cơ bản ...................20
2.4.2. Các điều kiện ràng buộc khi thực hiện phân cụm các thiết bị FSO dưới
mặt đất bằng thuật toán K-mean ........................................................................21
2.5. Thiết kế topology mạng HAP bằng thuật toán Dijkstra và Heuristic ..........22
2.5.1. Tổng quan về thuật toán Dijkstra và giải thuật Heuristic .....................22
2.5.2. Các điều kiện ràng buộc khi xây dựng mơ hình mạng HAP sử dụng thuật
toán Dijkstra và giải thuật Heuristic ..................................................................22
2.5.3. Tỉ lệ lỗi bit – BER .................................................................................22
CHƯƠNG 3: XÂY DỰNG THUẬT TOÁN THIẾT KẾ TOPO MẠNG FSO SỬ
DỤNG HAP ..............................................................................................................25
3.1. Ý tưởng chung .............................................................................................25
3.2. Phân chia các thiết bị FSO về các HAP ......................................................26
3.3. Thiết kế topo mạng giữa các HAP ..............................................................28
CHƯƠNG 4: CÀI ĐẶT THUẬT TOÁN, KẾT QUẢ THỰC HIỆN .......................30
4.1. Mơi trường cài đặt thuật tốn ......................................................................30
4.2. Kết quả thử nghiệm .....................................................................................30
4.2.1. Kết quả phân chia các thiết bị FSO về các HAP ..................................30
4.2.2. Kết quả chương trình thiết kế topo mạng .............................................33
4.3. Đánh giá kết quả thu được ...........................................................................40
CHƯƠNG 5: KẾT LUẬN ........................................................................................41
5.1. Kết quả đạt được ..........................................................................................41
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

6


5.2. Những điểm còn hạn chế .............................................................................41

5.3. Hướng phát triển ..........................................................................................41
5.4. Kết luận chung .............................................................................................42
TÀI LIỆU THAM KHẢO .........................................................................................43

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

7


DANH MỤC HÌNH ẢNH
Hình 1.1 : Mơ hình mạng multi-HAP kết hợp FSO ..................................................12
Hình 2.1: Mơ hình truyền quang giữa 2 thiết bị FSO ...............................................15
Hình 2.2: Mơ hình hệ thống truyền thơng quang khơng dây ....................................16
Hình 2.3: Máy bay khơng người lái Proteus .............................................................18
Hình 2.4: Tốc độ gió theo độ cao ..............................................................................18
Hình 2.5: Cấu hình cơ bản của hệ thống mạng trong trường hợp 1 HAP .................19
Hình 2.6: Cầu hình mạng cơ bản trong trường hợp sử dụng nhiều HAP .................20
Hình 2.7: Mơ hình thuật tốn K-mean ......................................................................21
Hình 2.8: Sơ đồ liên kết mạng ví dụ tính BER .........................................................24
Hình 3.1: Sơ đồ thuật tốn ........................................................................................26
Hình 3.2: Sơ đồ khối chương trình phân chia các thiết bị FSO dưới mặt đất ...........27
Hình 3.3: Sơ đồ khối chương trình thiết kế topo mạng .............................................29
Hình 4.1: Kết quả phân cụm các thiết bị FSO mặt đất với 8 HAP ...........................31
Hình 4.2: Tọa độ tâm 8 HAP ....................................................................................31
Hình 4.3: Kết quả phân cụm các thiết bị FSO mặt đất với 9 HAP ...........................32
Hình 4.4: Tọa độ tâm 9 HAP ....................................................................................32
Hình 4.5: Kết quả phân cụm các thiết bị FSO mặt đất với 10 HAP .........................33
Hình 4.6: Tọa độ tâm 10 HAP ..................................................................................33
Hình 4.7: Kết quả thiết kế topo mạng cho 8 HAP ....................................................34
Hình 4.8: Kết quả của 8 HAP....................................................................................35

Hình 4.9: Kết quả thiết kế topo mạng cho 9 HAP ....................................................36
Hình 4.10: Kết quả của 9 HAP..................................................................................37
Hình 4.11: Kết quả thiết kế topo mạng cho 10 HAP ................................................38
Hình 4.12: Kết quả của 10 HAP................................................................................39
Hình 4.13: Thống kê số lượng HAP và số liên kết FSO……………………………39

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

8


DANH MỤC TỪ VIẾT TẮT, THUẬT NGỮ
Từ viết tắt,
thuật ngữ
FSO

Free Space Optics

Truyền thông quang không dây

HAP

High Altitude Platform

Hạ tầng mạng trên cao

LOS

Line Of Sight


QoS

Quality of Service

Tầm nhìn thẳng, tín hiệu ánh sáng
truyền đi giữa hai thiết bị đặt thẳng
nhau
Chất lượng dịch vụ trên đường
truyền

LAN
MIB

Local Area Network
Management Information
Base
SONAbeam
Terminal
Controller

STC

Tên đầy đủ

BER

Bir Error Rate

ITU-R


Rx Power

International
Telecommunication
Union
Radiocommunication
Sector
Receive Power

mrad
dB

Mili-radian
Decibel

dBm

Decibel-miliwatt

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

Ý nghĩa

Mạng nội bộ
Cơ sở dữ liệu thông tin quản lý
Phần mềm theo dõi cũng như cấu
hình thiết bị SONAbeam do hãng
fSONA cung cấp
Tỉ lệ lỗi bit
Liên minh Viễn thông Quốc tế.

Tập trung vào việc xác định các tần
số radio tồn cầu đáp ứng lợi ích của
các nhóm cạnh tranh nhau
Cơng suất tín hiệu đo được tại nơi
đặt thiết bị thu
Đơn vị đo độ lớn của góc
Là một đơn vị so sánh tương đối giữ
hai giá trị.
Là một đơn vị so sánh tuyệt đối với
1mW.

9


MỞ ĐẦU
Với sự gia tăng của nhu cầu sử dụng Internet của người sử dụng, điều đó địi
hỏi u cầu về băng thông, tốc độ đường truyền và chất lượng dịch vụ phải được đảm
bảo, những ưu điểm về băng thông, truyền thông bằng cáp quang trở nên 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 (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í.
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,…
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,...
Truyền thông quang không dây sử dụng các hạ tầng mạng trên cao cịn gặp
nhiều khó khăn trong việc triển khai. Ví dụ, hiện nay Google sử dụng khinh khí cầu
có lắp đặt các thiết bị FSO, các khinh khí cầu này có thể bay trong khoảng thời gian
là 7 giờ, đây là số giờ bay thấp, cần liên tục hạ cánh để nạp năng lượng. Việc phát
triển giải pháp sử dụng pin mặt trời đang trong giai đoạn nghiên cứu, chưa được áp
dụng vào thực tiễn. Tuy nhiên, việc sử dụng kết hợp các thiết bị truyền quang không
dây và hạ tầng mạng trên cao đem đến nhiều ưu điểm luận văn tập trung vào giải
quyết các vấn đề liên quan đến thiết kế topo mạng cho việc truyền thông giữa các
thiết bị FSO dưới mặt đất sử dụng các HAP.
Luận văn có các nhiệm vụ tổng quan như sau:
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

10


 Xác định vị trí lắp đặt các HAP.
 Thiết kế topo mạng cho các HAP.
Luận văn được thực hiện trong q trình thực tập tại phịng thí nghiệm Cơng
nghệ mạng và truyền thơng, tịa nhà B1 – Đại học Bách Khoa Hà Nội. Với môi trường

nghiên cứu thuận lợi, chuyên nghiệp, trang thiết bị được cung cấp đầy đủ các thiết bị
FSO thực tế, cùng sự hướng dẫn tận tình của PGS.TS. Trương Thị Diệu Linh, tác giả
đã thu được những kiến thức và kinh nghiệm quý báu trong thời gian thực tập tại đây.
Bố cục của luận văn bao gồm các phần 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 thuật toán thiết kế topo mạng FSO sử dụng HAP.
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 toá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 và phát triể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 đề.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

11


CHƯƠNG 1: 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ở,…
Qua q trình nghiên cứu, tác giả nhận ra việc triển khai hệ thống truyền thông
quang không dây trên một thành phố, đảo cần phải sử dụng nhiều các thiết bị truyền
quang, lắp đặt trên độ cao lớn (>18km). Giải pháp đặt ra là sử dụng các thiết bị truyền
thông quang không dây FSO, đặt trên các HAP tham khảo Hình 1.1. Để bao phủ một
khu vực có diện tích lớn, cần sử dụng nhiều thiết bị FSO cũng như HAP. Tuy nhiên,
giá thành các thiết bị FSO và HAP là đắt, không thể lắp đặt quá nhiều. Mặt khác, mỗi
thiết bị FSO đặt trên HAP chỉ có thể bao phủ một khoảng diện tích nhất định, dó đó
cũng khơng thể lắp đặt q ít. Với u cầu trên cần có mơ hình xem xét về việc xây
dựng vị trí điểm đặt các HAP cũng như mơ hình truyền thơng giữa các HAP.

Hình 1.1: Mơ hình mạng multi-HAP kết hợp FSO
Bài tốn được đặt ra như sau: Giả sử có một số điểm thu thập dữ liệu dưới mặt
đất cần truyền tín hiệu cho nhau, các điểm này được trang bị các thiết bị quang không
dây như: máy thu phát quang FSO. Các thiết bị này được giới hạn về băng thông, các
điểm này nằm các xa nhau, không thể kết nối trực tiếp. Để truyền tín hiệu giữa các
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018
12



thiết bị FSO này, ta sẽ sử dụng các HAP làm điểm kết nối trung gian, các HAP này
cần được kết nối với nhau và giao tiếp với các thiết bị FSO bên dưới mặt đất. Ta cần
xác định vị trí các HAP để các thiết bị FSO đều được kết nối đến một HAP và nhu
cầu truyền tin giữa các FSO mặt đất được thỏa mãn. Vấn đề về tỉ lệ lỗi bit BER đầu
cuối cũng cần được giải quyết khi thiết kế topo mạng cho hệ thống này.
Bài toán được phát biểu cụ thể như sau:










Cho trước vị trí các điểm đặt thiết bị FSO dưới mặt đất.
Cho trước băng thông tối đa của mỗi thiết bị FSO.
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 yêu cầu kết nối giữa các thiết bị FSO dưới mặt đất dưới
dạng ba tham số: điểm đầu, điểm cuối, băng thông yêu cầu.
Cho trước băng thông tối đa giữa các HAP
Yêu cầu đặt ra là:
Thực hiện chia các thiết bị FSO mặt đất về các HAP phụ trách sao cho thỏa
mãn các yêu cầu về băng thông, độ phủ của một HAP. Từ đó xác định vị trí
đặt các HAP.
Với các vị trí điểm đặt HAP có được, thiết kế mơ hình topo mạng cho các HAP
sao cho thỏa mãn các yêu cầu băng thông giữa các HAP và thỏa mãn ngưỡng

BER đầu cuối.

Với các dữ liệu đầu vào, yêu cầu của bài tốn như trên, có thể thấy rõ ràng hai
nhiệm vụ của luận văn:
Nhiệm vụ 1: Trong nhiệm vụ thứ nhất, tác giả thiết kế chương trình phân cụm
các nút mạng dưới mặt đất, tìm vị trí điểm lắp đặt HAP với một số ràng buộc.
 Nhiệm vụ 2: Trong nhiệm vụ thứ hai, yêu cầu bài toán đặt ra là thiết kế mơ
hình liên kết mạng cho các HAP với một số điều kiện ràng buộc cho trước.


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 với nhiều ràng buộc nên việc tìm
kiếm một giải thuật để giải quyết là khó khăn. Do đó, để giải quyết các vấn đề trên,
tác giả cần nghiên cứu về các mơ hình phân cụm dữ liệu, các mơ hình bài tốn thiết
kế mơ hình mạng khơng dây, mơ hình tính BER cho các liên kết quang khơng dây.
Đã có bài báo [1] giải quyết vấn đề phân chia các điểm mạng dưới mặt đất
bằng thuật toán K-mean. Tuy nhiên, bài báo không đề cập đến các điều kiện ràng
buộc về độ bao phủ của HAP, số lượng điểm mạng tối đa trong một cụm, cũng như
chưa thiết kế topo mạng giữa các HAP
Để giải quyết nhiệm vụ thứ nhất, tác giả sử dụng thuật toán K-mean để thực
hiện phân cụm các thiết bị FSO về các HAP. Tuy nhiên, K-mean khơng tích hợp các
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

13


ràng buộc về khoảng cách tối đa giữa các thiết bị FSO với hình chiều của HAP. Do

đó, tác giả cần điều chỉnh thuật tốn K-mean để tích hợp các điều kiện. Tác giả sẽ
thêm điều kiện ràng buộc về khoảng cách giữa FSO và HAP, điều kiện ràng buộc về
băng thơng giữa của HAP kết nối đến mỗi nhóm FSO mà HAP đó quản lý.
Để giải quyết nhiệm vụ thứ hai, tác giả sử dụng kết quả của thuật toán trong
đồ án tốt nghiệp [2]

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

14


CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
2.1. Hệ thống quang không dây
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, tham khảo theo luận văn [6]. Đâ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.

FSO là cơng nghệ truyền thơng có tầm nhìn thẳng (LOS) nên hệ thống thường
được cài đặt trên các địa hình cao như nóc các tịa nhà cao tầng.

Hình 2.1: Mơ hình truyền quang giữa 2 thiết bị FSO
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 u cầu cấp phép phổ tần.
 Hệ thống triển khai dễ dàng, nhanh chóng.
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

15




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.
 Yê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 2.2: Mơ hình hệ thống truyền thơng quang khơng dây

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

16


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) được tham khảo trong bài báo [7] 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.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

17


Hình 2.3: Máy bay khơng người lái Proteus

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.

Hình 2.4: Tốc độ gió theo độ cao

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 để

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

18


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.

Hình 2.5: Cấu hình cơ bản của hệ thống mạng trong trường hợp 1 HAP
Hình 2.5 mơ tả cấu hình cơ bản của hệ thống truyền thông quang không dây
sử dụng hạ tầng mạng trên cao trong trường hợp sử dụng 1 HAP. Trong trường hợp
này, các thiết bị FSO dưới mặt đất liên kết với FSO đặt trên HAP để truyền dữ liệu
với nhau.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

19


Hình 2.6: Cầu hình mạng cơ bản trong trường hợp sử dụng nhiều HAP
Hình 2.6 mơ tả cấu hình mạng cơ bản của hệ thống truyền thông quang không
dây sử dụng hạ tầng mạng trên cao trong trường hợp sử dụng nhiều HAP. Trong
trường hợp này, các HAP kết nối với nhau. Khi một thiết bị FSO dưới mặt đất muốn
truyền dữ liệu đến một thiết bị FSO dưới mặt đất thuộc một cụm khác, thì dữ liệu sẽ
được truyền trung gian qua các HAP.

2.4.

Phân cụm nút mạng bằng thuật toán K-mean

2.4.1. Tổng quan về thuật toán K-mean – Các khái niệm cơ bản
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.
Thuật tốn K-mean có các bước chính như sau:
 Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại
diện bằng các tâm của cụm.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

20


 Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng
khoảng cách Euclidean).
 Nhóm các đối tượng vào nhóm gần nhất.
 Xác định lại tâm mới cho các nhóm.
 Thực hiện lại bước 2 cho đến khi khơng có sự thay đổi nhóm nào của các
đối tượng.

Hình 2.7: Mơ hình thuật tốn K-mean

2.4.2. Các điều kiện ràng buộc khi thực hiện phân cụm các thiết bị FSO
dưới mặt đất bằng thuật tốn K-mean
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ả nhận thấy cần mở rộng thuật toán, đưa thêm các điều kiện ràng
buộc để giải quyết nhiện vụ thứ nhất của bài toá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 [5], 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
đấ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
Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

21


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 [5], 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.

Thiết kế topology mạng HAP bằng thuật toán Dijkstra và Heuristic

2.5.1. Tổng quan về thuật toán Dijkstra và giải thuật Heuristic
Thuật toán Dijkstra là một thuật toán giải quyết bài toán đường đi ngắn nhất
nguồn đơn trong một đồ thị có hướng, thuật tốn thường được áp dụng trong định
tuyến.
Thuật tốn Dijkstra thích hợp cho việc tìm đường đi ngắn nhất từ một nút i tới
tất cả các nút cịn lại, dó đó phù hợp với việc xây dựng mơ hình mạng giữa các HAP.
Giải thuật Heuristic là một sự mở rộng khái niệm thuật toán, thường sử dụng
để giải các bài tốn có đặc tính: thường tìm được lời giải tốt (nhưng khơng chắc là tốt
nhất), bài toán được giải quyết một các đơn giản, nhanh chóng đưa ra kết quả, chi phí

thấp.

2.5.2. Các điều kiện ràng buộc khi xây dựng mơ hình mạng HAP sử dụng
thuật toán Dijkstra và giải thuật Heuristic
Điều kiện 1: Các ma trận băng thông yêu cầu đều được thỏa mãn. Băng thông
tối đa cho mỗi liên kết HAP là Bwmax = 1000Mb/s.
Điều kiện 2: Tổng BER đầu cuối của từng kết nối nhỏ hơn ngưỡng cho trước.
Thông thường, ngưỡng BER đầu cuối mỗi liên kết HAP là δ = 0.001.

2.5.3. Tỉ lệ lỗi bit – BER
Tỉ lệ lỗi bit BER là một thông số quan trọng được sử dụng trong việc đánh giá
các hệ thống truyền dữ liệu số giữa các địa điểm. BER được áp dụng để đánh giá các
liên kết cáp quang hoặc liên kết quang không dây dưới các ảnh hưởng của yếu tố môi
trường. Khi dữ liệu đưuọc truyền qua mơi trường có nhiễu, sẽ tiềm ẩn khả năng xảy
ra lỗi về dữ liệu thu nhận được. Vì vậy, để đánh giá một liên kết có nhiễu thì BER là
một đại lượng quan trọng. Cơng thức tính BER giữa các liên kết quang khơng dây
được tham khảo trong bài báo [3]. Định nghĩa của BER tham khảo trong đồ án [2],
được thể hiện như sau:
𝐵𝐸𝑅 =

𝑆ố𝑏𝑖𝑡𝑙ỗ𝑖
𝑇ổ𝑛𝑔𝑠ố𝑏𝑖𝑡𝑡𝑟𝑢𝑦ề𝑛đ𝑖

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

(1)
22


Tỉ lệ lỗi bit của một liên kết gồm nhiều liên kết được tính là tỉ lệ lỗi bit nhận

được tại điểm đầu và điểm cuối của một liên kết.
Xét một liên kết gồm nhiều liên kết T = t1, t2,…,tn. Giả sử tỉ lệ lỗi bit trên liên
kết ti là BERti thì tỉ lệ khơng có lỗi trên liên kết này là 1 - BERti. Do đó, khả năng
khơng có lỗi trên tồn liên kết là ∏𝑡∈𝑇(1 − 𝐵𝐸𝑅𝑡 ). Vậy tỉ lệ lỗi trên liên kết ti là
𝐵𝐸𝑅𝑡𝑖 = 1 − ∏𝑡∈𝑇(1 − 𝐵𝐸𝑅𝑡 )
Ta có tỉ lệ lỗi bit đầu cuối là BERT :
𝐵𝐸𝑅𝑇 = 1 − ∏(1 − 𝐵𝐸𝑅𝑡 )

(2)

𝑡∈𝑇

Ta có, điều kiện BER cho mỗi liên kết phải nhỏ hơn một ngưỡng BER cho
trước δ:
𝐵𝐸𝑅𝑇 ≤ 𝛿

(3)

Từ cơng thức (2), ta có:
1 − ∏(1 − 𝐵𝐸𝑅𝑡 ) ≤ 𝛿

(4)

𝑡∈𝑇

⇔ ∏(1 − 𝐵𝐸𝑅𝑡 ) ≤ 1 − 𝛿

(5)

𝑡∈𝑇


⇔ 𝑙𝑜𝑔⁡(∏(1 − 𝐵𝐸𝑅𝑡 )) ≤ 𝑙𝑜𝑔⁡(1 − 𝛿 )

(6)

𝑡∈𝑇

⇔ ∑(𝑙𝑜𝑔⁡(1 − 𝐵𝐸𝑅𝑡 )−1 ) ≤ 𝑙𝑜𝑔⁡(1 − 𝛿 )−1

(7)

𝑡

Như vậy, liên kết có BERT ≤ δ là liên kết có tổng 𝑙𝑜𝑔⁡(1 − 𝐵𝐸𝑅𝑡 )−1 dọc theo
các liên kết nhỏ hơn hoặc bằng ngưỡng δ cho trước.

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

23


Hình 2.8: Sơ đồ liên kết mạng ví dụ tính BER
Ví dụ, ta cần tính tỉ lệ lỗi bit từ điểm A đến điểm D trong hình 2.8, qua các
liên kết (A, B), (B, C), (C, D), ta cần tính tỉ lễ lỗi bit trên từng liên kết. Ta có, tỉ lệ
không lỗi bit trên liên kết (A, B) là 1 − 𝐵𝐸𝑅𝐴𝐵 . Tương tự, với các liên kết (B, C), (C,
D).
Từ đó, ta có tỉ lệ khơng lỗi bit trên các liên kết là :
(1 − 𝐵𝐸𝑅𝐴𝐵 )(1 − 𝐵𝐸𝑅𝐵𝐶 )(1 − 𝐵𝐸𝑅𝐶𝐷 )

(8)


Do đó, ta có cơng thức tỉ lệ lỗi bit từ A đến D là :
𝐵𝐸𝑅𝐴𝐵𝐶𝐷 = 1 − (1 − 𝐵𝐸𝑅𝐴𝐵 )(1 − 𝐵𝐸𝑅𝐵𝐶 )(1 − 𝐵𝐸𝑅𝐶𝐷 )

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

(9)

24


CHƯƠNG 3: XÂY DỰNG THUẬT TOÁN THIẾT KẾ TOPO MẠNG
FSO SỬ DỤNG HAP
3.1. Ý tưởng chung
Trong luận văn, có hai nhiệm vụ rõ ràng. Thứ nhất: xác định vị trí các HAP
bằng cách phân chia các thiết bị FSO mặt đất. Thứ hai: thiết kế topo mạng cho các
HAP:
Để giải quyết hai nhiệm vụ trên, tác giả cần xây dựng một thuật toán cho phép
chia các thiết bị FSO mặt đất thành các nhóm, được quản lý bởi các HAP. Từ đó, xác
định hình chiếu vị trí của HAP chính là tâm của các thiết bị FSO trong mỗi nhóm.
Sau khi tìm được vị trí của HAP, tác giả sẽ thiết kế topo mạng cho các HAP. Dựa
theo yêu cầu của bài toán, tác giả lựa chọn thuật toán K-mean có điều chỉnh, thêm
các ràng buộc để giải quyết nhiệm vụ chia nhóm các thiết bị FSO.
Sau khi thực hiện nhiệm vụ phân chia các thiết bị FSO dưới mặt đất về các
HAP tương ứng, tác giả sử dụng giải thuật trong đồ án [2] để thiết kế topo mạng HAP.
Đồ án [2] sử dụng thuật toán Dijkstra kết hợp giải thuật Heuristic có điều chỉnh, thêm
các điều kiện ràng buộc để thực hiện thiết kế topo mạng cho các HAP trên không.
Giải thuật Heuristic phù hợp với việc giải quyết các bài tốn có các điều kiện đầu vào
phức tạp, cần đưa ra lời giải trong thời gian ngắn.
Sau khi phân tích đề bài, xác định các điều kiện đầu vào, yêu cầu đầu ra của

bài toán, tác giả thiết kế thuật toán để giải quyết vấn đề trên. Sơ đồ thuật tốn được
mơ tả như Hình 3.1:

Học viên thực hiện: Vũ Phạm Minh Hiển – CBC17018

25