Thiết kế tôpô mạng không dây hình lưới: Một phương pháp mới sử dụng bài toán quy hoạch tuyến tính nguyên

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Thiết kế tôpô mạng không dây hình lưới:
Một phương pháp mới sử dụng bài toán
quy hoạch tuyến tính nguyên
Lê Hữu Bình1,2, Nguyễn Đăng Khoa1, Nguyễn Đình Hoàng Phương1
1Khoa Công nghệ Thông tin, Trường Cao đẳng Công nghiệp Huế
2Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
E-mail: lhbinh@hueic.edu.vn, ndkhoa@hueic.edu.vn, ndhphuong@hueic.edu.vn
Tác giả liên hệ: Lê Hữu Bình
Ngày nhận: 21/07/2017, ngày sửa chữa: 12/09/2017, ngày duyệt đăng: 13/10/2017
Tóm tắt: Khi triển khai mạng nội bộ sử dụng công nghệ mạng không dây hình lưới (WMN), một trong những yếu tố ảnh
hưởng lớn nhất đến hiệu năng của hệ thống là tôpô mạng. Trong bài báo này, chúng tôi đề xuất một thuật toán thiết kế
tôpô mạng WMN sử dụng bài toán quy hoạch tuyến tính nguyên (ILP). Phương pháp của chúng tôi là chia vùng không
gian cần thiết kế mạng thành các khối đơn vị là các vị trí có thể lắp đặt các điểm truy cập (AP). Dựa trên tọa độ của
các khối đã chia và các điều kiện ràng buộc về tổng số AP, vùng phủ sóng và độ ưu tiên, chúng tôi mô hình hóa thành
bài toán ILP. Bằng cách giải bài toán ILP, chúng tôi tìm được tổng số AP yêu cầu cho một hệ thống mạng và vị trí để
lắp đặt chúng. Hiệu quả thực thi của thuật toán đề xuất được kiểm nghiệm trên mạng nội bộ của Trường Cao đẳng Công
nghiệp Huế.
Từ khóa: Thiết kế tôpô, mạng không dây hình lưới, quy hoạch tuyến tính nguyên.
Title: Design the Topology of Wireless Mesh Networks: A New Method using Integer Linear Programming
Abstract: When deploying a local area network using wireless mesh network (WMN) technology, one of major factors influencing
the performance of the network is the network topology. In this paper, we propose a topology design algorithm of
WMN using the integer linear programming (ILP) problem. Our method is to divide the spatial area of the designed
network into unit blocks which can be used to place access points (APs). Based on the coordinates of the divided
blocks and the constraint conditions of the number of APs, radio range and priority, we formulate the topology design
as the ILP problem. The number of required APs and their installation location are determined by solving the ILP
problem. The performance of the proposed algorithm is verified on the local area network of Hue Industrial College.
Keywords: Topology design, wireless mesh network, integer linear programming.
I. GIỚI THIỆU
Công nghệ mạng truy nhập không dây đã và đang được
nghiên cứu và ứng dụng rộng rãi trong giai đoạn hiện nay.
Với mô hình mạng không dây hiện tại của hầu hết các
cơ quan, doanh nghiệp, trường học, tôpô mạng (network
topology) đang được sử dụng phổ biến là dạng hình cây
mở rộng như cho thấy trên Hình 1. Các AP được kết nối
tập trung về gateway của mạng nội bộ để truy cập Internet
thông qua các thiết bị chuyển mạch hoặc định tuyến. Mô
hình này có nhiều nhược điểm trong việc khai thác tài
nguyên mạng. Đặc biệt là khi tải lưu lượng trong mạng
phát sinh không đồng đều dẫn tới tình trạng nghẽn cục bộ
tại các điểm truy nhập thường xuyên xảy ra và việc thiết
lập kết nối vào mạng là rất khó khăn. Một nhược điểm
lớn khác của mô hình mạng không dây như ở Hình 1 là
mỗi AP cần phải có một cổng kết nối đến hệ thống chuyển
mạch của mạng nội bộ để chuyển tiếp đến gateway. Điều
này dẫn đến việc lãng phí tài nguyên và khó khăn trong
việc thi công hạ tầng, đặc biệt là đối với các hệ thống mạng
nhiều lớp và sử dụng nhiều AP.
Để giải quyết vấn đề này, việc nghiên cứu và triển khai
hệ thống mạng không dây đa chặng (Multihop Wireless
Networks) là điều cần thiết. Đây là công nghệ mạng không
dây tiên tiến hiện đang được nhiều nhà nghiên cứu trong
nước cũng như trên thế giới quan tâm. Mạng không dây
đa chặng được phân thành bốn loại chính bao gồm mạng
không dây tùy biến (Wireless Adhoc Network), mạng cảm
biến không dây (Wireless Sensor Network), mạng không
59
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
ISP 
Hệ thống các đường 
kết nối đến Gateway
AP1 
AP2 
AP3 
APn 
Hình 1. Mô hình mạng không dây phổ biến của các cơ quan,
doanh nghiệp.
MR/GW
MR
MR
MR/GW
MR/GW
MR
MR
MR
ISP
Client
Client
Client
Client
Client
Client
Client
Client
Client
Client
Wireless Mesh 
Network
Hình 2. Cấu trúc tổng quát của mạng WMN.
dây hình lưới (WMN: Wireless Mesh Network) và mạng
không dây hỗn hợp [1]. Trong các mô hình đó, WMN đang
ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực, đặc
biệt là trong hệ thống mạng nội bộ của các doanh nghiệp,
trường học, các cơ quan nhà nước.
Cấu trúc tổng quát của một mạng WMN được minh họa
như ở Hình 2, trong đó, các AP được kết nối với nhau
qua môi trường không dây tạo thành một tôpô hình lưới.
Một nút của mạng WMN có thể chỉ là một bộ định tuyến
không dây (MR: Mesh Router), hoặc là một bộ định tuyến
không dây kết hợp với gateway (MR/GW: Mesh Router with
gateway) [2]. Trong bài báo này, các nút mạng WMN được
gọi chung là AP. Các clients kết nối đến các AP qua môi
trường không dây để truy cập Internet.
Với công nghệ WMN, tình trạng nghẽn cục bộ tại các
điểm truy cập sẽ được giải quyết nhờ chức năng cân bằng
tải, điều khiển lưu lượng và định tuyến tại mỗi nút. Điều
này cho phép giảm thiểu số yêu cầu thiết lập kết nối bị từ
chối, hiệu quả sử dụng tài nguyên mạng được nâng cao. Mô
hình WMN cho phép giảm thiểu số cổng kết nối từ các AP
đến gateway, nghĩa là giảm thiểu chi phí đầu tư cho việc
lắp đặt cơ sở hạ tầng.
Để triển khai mạng WMN một cách hiệu quả, việc nghiên
cứu các phương pháp, thuật toán thiết kế mạng là điều cần
thiết. Nội dung của bài báo tập trung nghiên cứu vấn đề
này. Các mục tiếp theo của bài báo được bố cục như sau:
Mục II trình bày các công trình nghiên cứu đã công bố
liên quan đến các giao thức điều khiển và quy trình thiết
kế mạng WMN. Mục III trình bày một phương pháp xác
định số lượng AP và vị trí lắp đặt do chúng tôi đề xuất.
Mục IV trình bày các kết quả thực thi thuật toán trên mô
hình mạng thực của Trường Cao đẳng Công nghiệp Huế.
Cuối cùng là kết luận và đề xuất hướng phát triển tiếp theo,
được trình bày trong mục V.
II. CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
ĐẾN VIỆC THIẾT KẾ MẠNG WMN
Để nâng cao hiệu quả triển khai mạng WMN trong thực
tế, trong thời gian gần đây đã có nhiều nhóm nghiên cứu
trong nước cũng như trên thế giới tập trung nghiên cứu
về công nghệ này. Có nhiều hướng nghiên cứu đã được
triển khai như các kỹ thuật định tuyến tối ưu, kỹ thuật cân
bằng tải, chất lượng dịch vụ, quy trình thiết kế và triển
khai mạng. Trong các hướng nghiên cứu đó, hướng nghiên
cứu về quy trình thiết kế và triển khai mạng WMN được
nhiều nhà nghiên cứu quan tâm trong thời gian gần đây.
Nhóm tác giả trong [3] đã nghiên cứu bài toán bố trí các
nút trong mạng WMN sao cho hiệu quả về mặt chi phí
(CeNP: Cost effective Node Placement). Để phân tích bài
toán CeNP, các tác giả đã định nghĩa các hàm mục tiêu,
các điều kiện ràng buộc và mô hình bài toán CeNP thành
bài toán quy hoạch tuyến tính nguyên. Sau đó, các tác giả
đã đề xuất một phương pháp bố trí nút mạng hiệu quả có
tên CeNP LSA, trong đó có chức năng lựa chọn các nút
làm geteway, các nút làm bộ định tuyến (Mesh Router) phù
hợp. Hiệu quả thực thi của phương pháp CeNP LSA được
đánh giá bằng mô phỏng, kết quả đã cho thấy rằng phương
pháp CeNP LSA mang lại hiệu quả cao trong việc bố trí
nút mạng WMN. Một công trình nghiên cứu khác đã tập
trung vào các hệ thống mô phỏng bài toán bố trí nút trong
mạng WMN [4], các hệ thống mô phỏng được xem xét là
WMN-SA [5] và WMN-PSO [6]. Thông qua kết quả mô
phỏng, các tác giả đã kết luận rằng, WMN-SA thực thi tốt
hơn WMN-PSO, tuy nhiên, khi kích thước mạng lớn thì
WMN-SA cần nhiều thời gian tính toán hơn.
Một hướng nghiên cứu khác về mạng WMN cũng đã
được triển khai là tập trung vào việc thiết kế và triển khai
mạng. Nhóm tác giả trong [7] đã đề xuất một phương pháp
thiết kế và triển khai mạng WMN gồm có 10 bước với mục
tiêu giảm thiểu chi phí đầu tư. Các bước thiết kế bao gồm
phân tích khu vực, xác định yêu cầu, xác định ứng dụng và
dịch vụ, ước lượng chất lượng dịch vụ, ước lượng độ cao,
xác định vị trí lắp đặt thiết bị bên trong, lựa chọn công
60
Tập V-2, Số 18 (38), 12/2017
nghệ mạng, xác định vị trí lắp đặt thiết bị bên ngoài, quy
hoạch mạng và ước lượng tổng chi phí. Trong [8], bài toán
sắp xếp nút trong mạng WMN được mô hình hóa thành bài
toán tối ưu đa mục tiêu. Các mục tiêu được xem xét bao
gồm cực đại hóa số lượng kết nối trong mạng và vùng phủ
sóng đối với người sử dụng. Các tác giả cũng phân tích sự
phù hợp của các phương pháp khác nhau sử dụng cho việc
giải bài toán tối ưu trong mạng WMN.
Từ các kết quả nghiên cứu đã được công bố như đã đề
cập ở trên, chúng tôi nhận thấy rằng, việc nghiên cứu về
công nghệ WMN đã được triển khai theo nhiều hướng khác
nhau, từ việc nghiên cứu các giao thức điều khiển, định
tuyến để cải thiện hiệu năng, chất lượng dịch vụ, chất lượng
tín hiệu truyền dẫn cho đến các quy trình thiết kế mạng.
Để có thể triển khai mạng WMN một cách hiệu quả, việc
nghiên cứu các vấn đề liên quan đến thiết kế mạng là điều
cần thiết. Trong bài báo này, chúng tôi tiếp tục phát triển
hướng nghiên cứu này, cụ thể là tập trung vào bài toán thiết
kế tôpô mạng. Mục tiêu của công trình nghiên cứu này là
xây dựng một mạng WMN đạt hiệu quả tốt nhất với các
điều kiện về thiết bị và về cơ sở hạ tầng cho trước. Chúng
tôi đề xuất một phương pháp thiết kế tôpô mạng WMN sử
dụng bài toán quy hoạch tuyến tính nguyên (ILP) với hàm
mục tiêu là cực tiểu hóa tổng số AP cần thiết cho một hệ
thống mạng. Các điều kiện ràng buộc được xem xét sao
cho người sử dụng luôn được phủ sóng khi ở trong vùng
không gian diện tích đang xét. Sau khi giải bài toán ILP,
kết quả thu được là tổng số AP yêu cầu, đồng thời vị trí
cụ thể để lắp đặt mỗi AP cũng được xác định thông qua
giá trị của các biến trong bài toán ILP. Chi tiết về phương
pháp này được trình bày trong các mục tiếp theo.
III. THUẬT TOÁN XÁC ĐỊNH SỐ LƯỢNG AP VÀ
VỊ TRÍ LẮP ĐẶT
1. Mô hình hóa thành bài toán ILP
Xét bài toán cần triển khai hệ thống mạng nội bộ cho
một cơ quan, doanh nghiệp sử dụng công nghệ WMN. Vấn
đề đặt ra đối với người thiết kế hệ thống là với một địa hình
cho trước, cần phải xác định được tổng số AP tối thiểu cần
cung cấp, các vị trí lắp đặt AP sao cho vùng phủ sóng là
tối ưu theo nghĩa ở bất kỳ vị trí nào trong cơ quan, người
sử dụng đều có thể sử dụng được các dịch vụ trong mạng
nội bộ, truy cập được Internet qua hệ thống mạng không
dây. Hiện nay, việc lựa chọn các vị trí để lắp đặt AP hầu
hết là theo cảm tính, phụ thuộc vào ý kiến chủ quan của
người thiết kế. Vì vậy, tôpô mạng được xây dựng hoàn toàn
không có cơ sơ khoa học. Tổng số thiết bị AP cần thiết cho
một hệ thống mạng là do người thiết kế tự chọn, dẫn đến
có lúc thiếu, có lúc thừa mà người thiết kế không hề hay
biết. Trong phần này, chúng tôi đề xuất một phương pháp
xác định tổng số AP yêu cầu tối thiểu cho một mô hình
Vị trí khả thi với AP và người dùng
Vị trí khả thi với người dùng
Hình 3. Mô hình hóa vùng không gian lắp đặt mạng WMN thành
các khối chức năng.
mạng và vị trí cụ thể để lắp đặt tất cả các AP đó. Thuật
toán được đề xuất dựa trên bài toán ILP.
Xét vùng diện tích của cơ quan, doanh nghiệp cần triển
khai hệ thống mạng WMN chứa các tòa nhà, văn phòng là
nơi có thể lắp đặt các AP. Vùng diện tích này có thể được
mô hình thành một không gian 3D với chiều cao là độ cao
của toà nhà cao nhất. Chia vùng không gian này thành từng
khối đơn vị với thể tích a (m3), a chính là sai số chọn vị trí
trong thuật toán của chúng tôi. Với phương pháp này, một
vùng diện tích chứa các toà nhà cần lắp đặt các thiết bị AP
của mạng WMN được mô hình thành một không gian 3D
là tập hợp của các khối có thể tích a (m3) như cho thấy trên
Hình 3. Các khối đơn vị có thể tích a (m3) này được gọi là
các vị trí khả thi. Có hai loại vị trí khả thi trong mô hình
này. Loại vị trí thứ nhất là vị trí có thể lắp đặt AP, đồng
thời có thể xuất hiện người sử dụng (các khối màu trắng
trong Hình 3). Các vị trí này chỉ có thể nằm trong các toà
nhà vì các AP trong trường hợp này là loại indoor, chỉ có
thể lắp trong nhà. Loại vị trí thứ hai là các vị trí chỉ khả
thi với người sử dụng (các khối màu đen trong Hình 3),
nghĩa là chỉ có các người sử dụng có thể ở các vị trí này,
còn AP không thể lắp đặt tại đây. Các vị trí này thường là
ở ngoài sân, vỉa hè. Để xác định vị trí nào được lắp đặt AP
trong tổng số các vị trí khả thi với AP, chúng tôi gán cho
mỗi vị trí khả thi với AP là một biến x(xx, yx, zx), với xx ,
yx và zx là tọa độ của vị trí x trong không gian 3 chiều.
Để xác định giá trị của tất cả các biến x(xx, yx, zx), chúng
tôi định nghĩa một hàm chọn vị trí như sau:
x(xx, yx, zx) =
{
1, nếu (xx, yx, zx) được lắp AP,
0, trong trường hợp khác.
(1)
Gọi X= {x(xx, yx, zx)} là tập tất cả các biến được gán cho
tất cả các vị trí có thể lắp đặt AP trong vùng không gian
3D đang xét. Với hàm chọn vị trí được xác định bởi (1), bài
toán xác định tổng số AP yêu cầu tối thiểu và vị trí để lắp
đặt AP được mô hình hóa thành bài toán tối ưu ILP như sau:
minimize
∑
∀x(xx,yx,zx )∈X
x(xx, yx, zx), (2)
với các điều kiện ràng buộc sau đây.
61
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
1) Ràng buộc về vùng phủ sóng:
Để đảm bảo người dùng có thể sử dụng các dịch vụ của
mạng nội bộ và truy cập Internet ở bất kỳ vị trí nào trong
cơ quan, tại mỗi vị trí khả thi đối với người sử dụng (các
khối màu đen trong Hình 3) phải nằm trong vùng phủ sóng
của ít nhất một AP. Gọi U = {u(xu, yu, zu)} là tập tất cả các
vị trí khả thi với người sử dụng. Khi đó điều kiện ràng buộc
vùng phủ sóng cho mỗi vị trí khả thi u(xu, yu, zu) được xác
định theo phương trình sau:∑
∀x(xx,yx,zx )∈X
α (u(xu, yu, zu), x(xx, yx, zx)) ≥ 1, (3)
trong đó α (u(xu, yu, zu), x(xx, yx, zx)) là một hàm xác định
phạm vi phủ sóng từ vị trí x(xx, yx, zx) đến vị trí người sử
dụng u(xu, yu, zu). Hàm này được xác định như sau:
α (u(xu, yu, zu), x(xx, yx, zx)) ={
1, nếu d (u(xu, yu, zu), x(xx, yx, zx)) ≤ D,
0, trong trường hợp khác,
(4)
trong đó D là bán kính vùng phủ sóng của loại AP
đang xét, d (u(xu, yu, zu), x(xx, yx, zx)) là khoảng cách từ
vị trí x(xx, yx, zx) có thể đặt AP đến vị trí người sử dụng
u(xu, yu, zu). Khoảng cách này được xác định bởi
d (u(xu, yu, zu), x(xx, yx, zx)) =√
(xx − xu)2 + (yx − yu)2 + (zx − zu)2. (5)
2) Ràng buộc nguyên:
Các biến trong tập X chỉ nhận các giá trị nguyên 1 hoặc
0 tương ứng với các trường hợp vị trí đang xét được chọn
hoặc không được chọn để lắp đặt AP theo phương trình (1),
nên điều kiện ràng buộc nguyên được xác định bởi
0 ≤ x(xx, yx, zx) ≤ 1, ∀x(xx, yx, zx) ∈ X . (6)
3) Ràng buộc về dung lượng của mỗi AP:
Với mỗi AP, tại mỗi thời điểm chỉ có thể cho phép một số
lượng người sử dụng kết nối đồng thời đến AP, giá trị này
nằm trong khoảng từ 25 đến 50 tùy theo loại AP. Để đảm
bảo chất lượng dịch vụ cho người sử dụng, ràng buộc này
phải được xem xét trong hệ thống mạng WMN. Gọi M là
số người sử dụng cho phép kết nối đồng thời đến mỗi AP,
C là tổng số người sử dụng đồng thời trong hệ thống mạng,
khi đó ràng buộc về dung lượng AP được xác định bởi∑
∀x(xx,yx,zx )∈X
Mx(xx, yx, zx) ≥ C. (7)
4) Ràng buộc về các vùng ưu tiên (nếu có):
Trong trường hợp có một số vị trí của người sử dụng trong
cơ quan cần phải được ưu tiên do đặc thù công việc, điều
kiện ràng buộc về các vùng ưu tiên cần phải được xác định
trong thuật toán. Gọi P là tập tất cả các vị trí cần được ưu
tiên, khi đó điều kiện ràng buộc này được xác định bởi∑
∀u(xu,yu,zu )∈P
α (u(xu, yu, zu), x(xx, yx, zx)) ≥ N, (8)
trong đó α (u(xu, yu, zu), x(xx, yx, zx)) được xác định theo
các phương trình (4) và (5), N là số sóng ưu tiên cho các
vị trí của người sử dụng trong tập P.
Bằng cách giải bài toán quy hoạch tuyến tính nguyên
theo (2) với các điều kiện ràng buộc từ (3) đến (8) ta thu
được tập nghiệm {X}. Dựa trên tọa độ của các biến xác
định vị trí trong tập {X}, sẽ tìm được tập vị trí cần lắp đặt
AP thỏa mãn các điều kiện ràng buộc từ (3) đến (8). Ngoài
ra, giá trị của hàm (2) thu được chính là tổng số AP yêu
cầu tối thiểu thỏa mãn điều kiện bài toán. Mặc dù (2) là
bài toán tối ưu một mục tiêu, tuy nhiên kết quả thu được
có thể xem như hai mục tiêu: một là tổng số AP yêu cầu
tối thiểu cho một hệ thống mạng (giá trị của hàm (2)), hai
là vị trí để lắp đặt mỗi AP (tọa độ của các biến x có giá
trị bằng 1). Đây là ưu điểm của phương pháp đề xuất và
sẽ được chứng minh bởi các kết quả thực nghiệm ở mục
tiếp theo.
2. Thuật toán xác định số lượng AP và vị trí lắp đặt
Thuật toán xác định tổng số AP theo yêu cầu và vị trí cụ
thể để lắp đặt chúng được thực thi theo lưu đồ ở Hình 4.
Khi giải bài toán ILP theo (2), tùy theo đặc điểm của vùng
không gian cần triển khai mạng WMN mà có trường hợp
tìm được tập nghiệm {X}, nhưng cũng có trường hợp không
tìm được tập nghiệm {X} thỏa mãn các điều kiện ràng buộc
từ (3) đến (8). Các trường hợp không tìm được tập nghiệm
{X} là vùng không gian cần triển khai mạng WMN có các
tòa nhà ở xa nhau. Trong trường hợp này, khoảng cách của
các tòa nhà lớn hơn 2D (D là bán kính vùng phủ sóng của
loại AP đang xét), nên các vị trí ở giữa của 2 tòa nhà không
được phủ sóng. Hay nói cách khác, điều kiện ràng buộc (4)
của bài toán ILP không thỏa mãn. Khi đó, kỹ thuật tối ưu
được sử dụng để tìm nghiệm, cụ thể là tăng giá trị D trong
điều kiện ràng buộc (4) một khoảng ∆D sao cho bài toán
ILP theo (2) tìm được nghiệm. Bằng phương pháp chia đôi,
chúng ta sẽ tìm được ∆D là giá trị nhỏ nhất cần tăng thêm
cho D với độ chính xác  cho trước sao cho bài toán ILP
theo (2) có nghiệm. Phương pháp chia đôi để tìm ∆D được
trình bày ở lưu đồ thuật toán Hình 4, cụ thể như sau:
◦ Xét trường hợp khi giải bài toán ILP theo (2) với các
điều kiện ràng buộc từ (3) đến (8) không tìm được
nghiệm. Khi đó, cần tăng giá trị D trong ràng buộc (4)
một khoảng ∆D;
◦ Gọi Dmax là khoảng cách lớn nhất giữa các tòa nhà
trong vùng không gian cần triển khai WMN, khi đó
∆D là một giá trị nằm trong nửa đoạn (0,Dmax];
62
Tập V-2, Số 18 (38), 12/2017
Bắt đầu
Mô hình hóa vùng không 
gian mạng WMN thành các 
khối chức năng theo Hình 3
Xây dựng bài toán ILP (2) với 
các ràng buộc từ (3) đến (8)
Giải bài toán ILP (2) với các 
ràng buộc từ (3) đến (8)
Tìm được 
tập nghiệm
Lắp đặt AP tại tọa độ của các 
điểm có giá trị bằng 1
Đúng
Sai
Sai
Kết thúc
Đúng
{X}?
∆D = 0; D− = 0
D+ = Dmax;  = 10−3
|D− − ∆D | ≤ 
x ∈ {X}
D+ = ∆D
D− = ∆D
∆D =
D− + D+
2
D = D + ∆D
Range
R(Ptindex)
Hình 4. Lưu đồ thuật toán xác định tổng số và vị trí để lắp đặt AP.
◦ Gọi D+ và D− là hai giá trị mà khi tăng thêm cho ràng
buộc (4) thì bài toán ILP (2) có nghiệm và không có
nghiệm. Ở trạng thái khởi tạo, ta gán D− là giá trị nhỏ
nhất (D− = 0) và D+ là giá trị lớn nhất (D+ = Dmax);
◦ Chọn ∆D = (D− + D+)/2, tăng giá trị D của ràng
buộc (4) một khoảng ∆D (D = D + ∆D), sau đó tiến
hành giải lại bài toán ILP;
◦ Nếu không tìm được nghiệm thì vùng tìm kiếm ∆D
được giới hạn trong nửa đoạn (∆D,Dmax], từ đó gán
D− = ∆D và giải lại bài toán ILP;
◦ Nếu tìm được nghiệm nhưng sai số giữa ∆D và D− lớn
hơn độ chính xác  cho trước thì vùng tìm kiếm được
giới hạn trong nửa đoạn (D−,∆D], từ đó gán D+ = ∆D
và giải lại bài toán ILP. Ngược lại, ∆D ở thời điểm
hiện tại là giá trị nhỏ nhất với độ chính xác  cần tìm.
IV. KẾT QUẢ THỰC NGHIỆM
Chúng tôi đã áp dụng phương pháp được đề xuất ở
mục III vào việc triển khai hệ thống mạng không dây theo
Vị trí khả thi với AP và người dùng
Vị trí khả thi với người dùng
Hình 5. Mô hình hóa vùng diện tích của Trường Cao đẳng Công
nghiệp Huế thành vùng không gian 3D là tổ hợp của các khối
chức năng có thể tích 5 m3.
công nghệ WMN tại cơ sở 1 của Trường Cao đẳng Công
nghiệp Huế. Vùng diện tích tại cơ sở này có chiều dài
mặt trước (cổng chính) là 183,5 m, mặt sau (cổng phụ) là
195,8 m, chiều rộng phía đường Hai Bà Trưng là 129,3 m
và phía đường Nguyễn Trường Tộ là 183,7 m. Có tất cả 17
tòa nhà tại cơ sở này, tính cả nhà khách và khu ký túc xá.
Chia vùng diện tích này và các tòa nhà thành các khối chức
năng với thể tích 5 m3 ta được một mô hình không gian
3D như ở Hình 5. Trong trường hợp này, sai số vị trí trong
thuật toán của chúng tôi là 5 m. Từ mô hình này, chúng
tôi tiến hành xây dựng thành bài toán quy hoạch tuyến tính
nguyên ILP theo các phương trình từ (1) đến (8) như đã
trình bày ở mục II. Tiến hành giải bài toán ILP này chúng
ta thu được tổng số AP yêu cầu tối thiểu cho hệ thống mạng
WMN tại Trường và vị trí cụ thể để lắp đặt các AP đó.
Chúng tôi đã cài đặt thuật toán trên phần mềm Matlab
R2010b, sử dụng các hàm tối ưu được cung cấp trong phần
mềm này để giải bài toán ILP. Các giả thiết đầu vào được
thiết lập như sau:
◦ Phạm vi phủ sóng của AP: 40 m (giá trị D trong ràng
buộc (4)), đây là vùng phủ sóng đảm bảo cho người
sử dụng truy cập mạng tốt;
◦ Sai số vị trí: 5 m;
◦ Số người sử dụng có thể kết nối đồng thời đến mỗi
AP: 40 (giá trị M trong ràng buộc (7));
◦ Tổng số người sử dụng trung bình tại mỗi thời điểm
của toàn trường: 1137 (giá trị C trong ràng buộc (7),
tham số này được chọn dựa trên quá trình thống kê
lưu lượng trên hệ thống mạng của Nhà trường);
◦ Không thiết lập các vùng ưu tiên (ràng buộc (8)).
Kết quả thực thi phương pháp đề xuất được so sánh với
phương pháp lắp đặt theo kinh nghiệm mà chúng tôi đã
triển khai trên hệ thống mạng không dây của Trường Cao
đẳng Công nghiệp Huế trước đây. Với phương pháp lắp đặt
theo kinh nghiệm này, vị trí lắp đặt các AP được xác định
theo lưu đồ thuật toán ở Hình 6. Để đảm bảo vùng phủ
sóng cho toàn khuôn viên Trường và đáp ứng lưu lượng
63
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Xác định các vị trí có thể lắp đặt 
AP dựa trên sơ đồ các tòa nhà 
Lắp đặt tạm thời các AP 
Đạt yêu cầu?
Lắp đặt cố định AP
tại vị trí hiện hành 
Đúng
Sai
Phân tích độ phủ sóng tại tất 
cả các vị trí của người sử dụng 
Định vị lại
vị trí của AP
Bắt đầu
Kết thúc
Hình 6. Lưu đồ thuật toán chọn vị trí lắp đặt AP cho mạng không
dây theo kinh nghiệm.
của hệ thống mạng nội bộ, chúng tôi đã lắp đặt 38 AP. Với
phương pháp được đề xuất trong bài báo này, số lượng AP
và vị trí lắp đặt chúng dựa trên kết quả của việc giải bài
toán ILP như đã trình bày ở trên.
Sau khi chạy chương trình tối ưu được cài đặt trên phần
mềm Matlab, kết quả thu được như ở Hình 7. Nhận thấy
rằng, kết quả của hàm cực tiểu hóa theo (2) là 36, nghĩa
là cần tối thiểu AP để lắp đặt mạng WMN tại Trường
Cao đẳng Công nghiệp Huế sao cho tất cả các vị trí trong
khuôn viên của Nhà trường đều thu được sóng trong vùng
phủ 40 m (đây là phạm vi để hoạt động tốt). Vị trí để lắp
đặt 36 AP này là tại tọa độ của các biến có giá trị bằng 1
như ở Hình 6. Ví dụ, AP đầu tiên được lắp đặt tại tọa độ
(20, 25, 5). Đối chiếu với mô hình ở Hình 4, tọa độ này
thuộc nhà E1, lắp đặt tại vị trí cách 20 m tính từ bìa trái
sang, cách 25 m tính từ mặt trước và độ cao 5 m. Vị trí lắp
đặt các AP khác được xác định hoàn toàn tương tự. Bảng I
mô tả chi tiết về các vị trí để lắp đặt toàn bộ 36 AP.
Để thấy rõ hiệu quả ứng dụng của phương pháp đề xuất,
chúng tôi phân tích độ phủ sóng đến tất cả các vị trí của
người sử dụng trên mặt đất và tầng 1 trong các tòa nhà,
kết quả thu được như cho thấy trên Hình 8 và Hình 9. Kết
quả phân thích cho thấy rằng, với phương pháp lắp đặt theo
kinh nghiệm (kết quả trên Hình 8), một số vị trí của người
sử dụng có đến 15 AP có thể phủ sóng đến, nhưng cũng
có một số vị trí không có AP nào phủ sóng đến, chẳng
hạn như ví trí có tọa độ x = 5 m và y = 100 m. Đối với
Hình 7. Kết quả giải bài toán ILP trên Matlab tìm tổng số AP
yêu cầu và vị trí lắp đặt chúng.
Hình 8. Độ phủ sóng đến các vị trí của người sử dụng trên mặt
đất và tầng 1 của các tòa nhà trong trường hợp lắp đặt 38 AP
theo kinh nghiệm.
phương pháp được đề xuất (kết quả trên Hình 9), mặc dù
vị trí có nhiều AP phủ sóng nhất không đạt bằng phương
pháp kinh nghiệm, nhưng tất cả các vị trí đều có AP phủ
sóng đến. Điều này đặc biệt quan trọng trong việc đảm bảo
tính liên tục đối với việc cung cấp dịch vụ cho người sử
dụng. Để thấy rõ hơn độ phủ sóng đến các vị trí, chúng tôi
vẽ biểu đồ trên Hình 10. Từ biểu đồ này ta thấy rằng, có
64
Tập V-2, Số 18 (38), 12/2017
Bảng I
KẾT QUẢ XÁC ĐỊNH VỊ TRÍ LẮP ĐẶT AP CỦA MẠNG WMN SỬ DỤNG PHƯƠNG PHÁP ĐỀ XUẤT
STT x (m) x (m) x (m) Dãy nhà STT x (m) x (m) x (m) Dãy nhà
1 20 25 5 E1 19 170 85 10 D1
2 40 20 5 L 20 125 85 5 D2
3 55 20 5 L 21 150 85 20 D2
4 45 30 10 L 22 170 85 10 D2
5 100 20 5 I 23 190 85 10 D2
6 105 25 5 I 24 190 85 10 X1
7 115 20 5 I 25 195 85 10 X1
8 70 40 5 C 26 25 130 5 TDTT
9 145 25 5 A 27 35 130 5 TDTT
10 170 30 5 A 28 40 135 5 TDTT
11 155 30 10 A 29 35 90 5 B
12 160 40 10 A 30 90 145 5 N
13 10 65 5 K1 31 105 140 5 M
14 15 85 5 K2 32 115 140 5 M
15 55 80 10 D1 33 165 135 15 X2
16 80 80 5 D1 34 180 140 10 X2
17 105 80 10 D1 35 150 135 5 X2
18 70 80 15 D1 36 195 85 10 X0
Hình 9. Độ phủ sóng đến các vị trí của người sử dụng trên mặt
đất và tầng 1 của các tòa nhà trong trường hợp lắp đặt 36 AP
theo phương pháp đề xuất.
4 vị trí không có AP nào phủ sóng đến trong trường hợp
triển khai theo kinh nghiệm. Với phương pháp đề xuất, tất
cả các vị trí đều nhận được sóng của các AP. Có 1 vị trí
chỉ có 1 AP phủ sóng đến, 3 vị trí có 2 AP phủ sóng đến,
các vị trí khác có từ 3 đến 12 sóng phủ đến. Ngoài ra, với
phương pháp kinh nghiệm, tổng số AP được chọn để lắp
đặt là 38. Trong khi đó, với phương pháp đề xuất, giá trị
này được tìm ra là 36. Như vậy, với số lượng AP ít hơn
nhưng vẫn đảm bảo vùng phủ sóng cho tất cả các vị trí của
người sử dụng.
Trên Hình 11, chúng tôi so sánh xác suất yêu cầu thiết lập
kết nối bị từ chối của thuật toán lắp đặt theo kinh nghiệm
và thuật toán đề xuất. Các đồ thị trên Hình 11 đã cho thấy
rằng, khi số người sử dụng nhỏ hơn 700 thì hiệu quả thực
thi của hai thuật toán gần như tương đương nhau, chênh
lệch không đáng kể. Khi số người sử dụng tăng lên, xác
suất từ chối yêu cầu thiết lập kết nối của thuật toán đề xuất
giảm một cách đáng kể so với phương pháp lắp đặt theo
kinh nghiệm. Cụ thể như trường hợp tổng số người sử dụng
là 1200, xác suất từ chối của phương pháp kinh nghiệm là
0,075, trong khi đó giá trị này của thuật toán đề xuất là
0,045. Như vậy, thuật toán đề xuất nâng cao hiệu quả sử
dụng tài nguyên mạng.
V. KẾT LUẬN
Để nâng cao chất lượng mạng không dây trong các cơ
quan, doanh nghiệp, việc nghiên cứu và triển khai hệ thống
mạng theo công nghệ WMN là điều cần thiết, đặc biệt là
trong trường hợp hệ thống mạng không dây có vùng diện
tích rộng, tải lưu lượng lớn. Nội dung bài báo đã tập trung
nghiên cứu những vấn đề cơ bản nhất về công nghệ WMN.
Từ đó, chúng tôi đã đề xuất một phương pháp xác định tổng
số thiết bị AP yêu cầu tối thiểu của một hệ thống mạng,
đồng thời xác định được vị trí cụ thể để lắp đặt các AP
này thỏa mãn các điều kiện ràng buộc cho trước. Chúng
tôi cũng đã thực thi thuật toán trên hệ thống mạng nội bộ
tại cơ sở 1 của Trường Cao đẳng Công nghiệp Huế, đã
xác định được tổng số AP yêu cầu và vị trí cụ thể để lắp
đặt chúng.
65
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Hình 10. So sánh số vị trí đối với số AP trong vùng phủ sóng của phương pháp lắp đặt theo kinh nghiệm và phương pháp đề xuất.
Phương pháp kinh nghiệm 
Phương pháp đề xuất 
Số người dùng 
X
ác
 su
ất k
ết n
ối 
bị 
từ 
ch
ối 
Hình 11. So sánh xác suất thiết lập kết nối bị từ chối của phương
pháp lắp đặt theo kinh nghiệm và phương pháp đề xuất.
Trong các nghiên cứu tiếp theo, chúng tôi sẽ tiếp tục
phát triển thuật toán để bổ sung các chức năng còn thiếu
như xác định các vị trí cần kết nối gateway, tích hợp giao
thức định tuyến trong tôpô mạng. Từ đó, tích hợp thành
một phần mềm hoàn chỉnh sử dụng cho việc thiết kế tôpô
mạng WMN.
TÀI LIỆU THAM KHẢO
[1] Y. Zhang, J. Luo, and H. Hu, Wireless Mesh Networking:
Architectures, Protocols and Standards. CRC Press, 2007.
[2] I. F. Akyildiz and X. Wang, Wireless Mesh Networks. John
Wiley & Sons, 2009, vol. 3.
[3] W. Wu, J. Luo, and M. Yang, “Cost-effective placement of
mesh nodes in wireless mesh networks,” in Proceedings of
the 5th International Conference on Pervasive Computing and
Applications (ICPCA). IEEE, 2010, pp. 261–266.
[4] S. Sakamoto, T. Oda, M. Ikeda, L. Barolli, F. Xhafa, and
I. Woungang, “Node Placement in Wireless Mesh Networks:
A Comparison Study of WMN-SA and WMN-PSO Sim-
ulation Systems,” in Proceedings of the 19th International
Conference on Network-Based Information Systems (NBiS).
IEEE, 2016, pp. 1–8.
[5] S. Sakamoto, A. Lala, T. Oda, V. Kolici, L. Barolli, and
F. Xhafa, “Application of WMN-SA simulation system for
node placement in wireless mesh networks: a case study for
a realistic scenario,” International Journal of Mobile Com-
puting and Multimedia Communications (IJMCMC), vol. 6,
no. 2, pp. 13–21, 2014.
[6] S. Sakamoto, T. Oda, M. Ikeda, L. Barolli, and F. Xhafa,
“Implementation of a new replacement method in WMN-
PSO simulation system and its performance evaluation,” in
Proceedings of the IEEE 30th International Conference on
Advanced Information Networking and Applications (AINA).
IEEE, 2016, pp. 206–211.
[7] J. L. E. K. Fendji and J. M. Nlong, “Rural Wireless Mesh
Network: A Design Methodology,” Int. J. Communications,
Network and System Science, vol. 8, pp. 1–9, 2015.
[8] A. Barolli, F. Xhafa, and M. Takizawa, “Optimization prob-
lems and resolution methods for node placement in wireless
mesh networks,” in Proceedings of the 14th International
Conference on Network-Based Information Systems (NBiS).
IEEE, 2011, pp. 126–134.
Lê Hữu Bình sinh năm 1978 tại Quảng Trị.
Ông tốt nghiệp Trường Đại học Bách Khoa
Đà Nẵng năm 2001, chuyên ngành Điện tử
- Viễn thông và nhận bằng Thạc sĩ chuyên
ngành Công nghệ Thông tin tại Trường Đại
học Khoa học, Đại học Huế, năm 2007. Từ
năm 2015 đến nay, ông là nghiên cứu sinh
chuyên ngành Hệ thống Thông tin tại Học
viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công
nghệ Việt Nam. Hiện nay, ông là Trưởng khoa Công nghệ Thông
tin, Trường Cao đẳng Công nghiệp Huế. Hướng nghiên cứu quan
tâm của ông là công nghệ mạng không dây thế hệ mới, SDN
(Software Defined Networking), mô phỏng và thiết kế mạng.
66