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