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

Nội dung text: 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

1. 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 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 Công nghệ mạng truy nhập không dây đã và đang được mạch của mạng nội bộ để chuyển tiếp đến gateway. Điều nghiên cứu và ứng dụng rộng rãi trong giai đoạn hiện nay. này dẫn đến việc lãng phí tài nguyên và khó khăn trong Với mô hình mạng không dây hiện tại của hầu hết các việc thi công hạ tầng, đặc biệt là đối với các hệ thống mạng cơ quan, doanh nghiệp, trường học, tôpô mạng (network nhiều lớp và sử dụng nhiều AP. 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 Để giải quyết vấn đề này, việc nghiên cứu và triển khai tập trung về gateway của mạng nội bộ để truy cập Internet hệ thống mạng không dây đa chặng (Multihop Wireless thông qua các thiết bị chuyển mạch hoặc định tuyến. Mô Networks) là điều cần thiết. Đây là công nghệ mạng không hình này có nhiều nhược điểm trong việc khai thác tài dây tiên tiến hiện đang được nhiều nhà nghiên cứu trong nguyên mạng. Đặc biệt là khi tải lưu lượng trong mạng nước cũng như trên thế giới quan tâm. Mạng không dây phát sinh không đồng đều dẫn tới tình trạng nghẽn cục bộ đa chặng được phân thành bốn loại chính bao gồm mạng tại các điểm truy nhập thường xuyên xảy ra và việc thiết không dây tùy biến (Wireless Adhoc Network), mạng cảm lập kết nối vào mạng là rất khó khăn. Một nhược điểm biến không dây (Wireless Sensor Network), mạng không 59
2. 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 Để triển khai mạng WMN một cách hiệu quả, việc nghiên AP1 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 đề ISP này. Các mục tiếp theo của bài báo được bố cục như sau: AP 2 Mục II trình bày các công trình nghiên cứu đã công bố Hệ thống các đường liên quan đến các giao thức điều khiển và quy trình thiết kết nối đến Gateway 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. AP3 Mục IV trình bày các kết quả thực thi thuật toán trên mô APn 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. Hình 1. Mô hình mạng không dây phổ biến của các cơ quan, doanh nghiệp. II. CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN ĐẾN VIỆC THIẾT KẾ MẠNG WMN ISP Để nâng cao hiệu quả triển khai mạng WMN trong thực Client tế, trong thời gian gần đây đã có nhiều nhóm nghiên cứu Client Wireless Mesh Network trong nước cũng như trên thế giới tập trung nghiên cứu MR/GW Client về công nghệ này. Có nhiều hướng nghiên cứu đã được MR/GW MR/GW triển khai như các kỹ thuật định tuyến tối ưu, kỹ thuật cân MR bằng tải, chất lượng dịch vụ, quy trình thiết kế và triển MR MR khai mạng. Trong các hướng nghiên cứu đó, hướng nghiên MR MR Client Client cứu về quy trình thiết kế và triển khai mạng WMN được Client nhiều nhà nghiên cứu quan tâm trong thời gian gần đây. Client Client Nhóm tác giả trong [3] đã nghiên cứu bài toán bố trí các Client Client nút trong mạng WMN sao cho hiệu quả về mặt chi phí Hình 2. Cấu trúc tổng quát của mạng WMN. (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 dây hình lưới (WMN: Wireless Mesh Network) và mạng bài toán quy hoạch tuyến tính nguyên. Sau đó, các tác giả không dây hỗn hợp [1]. Trong các mô hình đó, WMN đang đã đề xuất một phương pháp bố trí nút mạng hiệu quả có ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực, đặc tên CeNP LSA, trong đó có chức năng lựa chọn các nút biệt là trong hệ thống mạng nội bộ của các doanh nghiệp, làm geteway, các nút làm bộ định tuyến (Mesh Router) phù trường học, các cơ quan nhà nước. hợp. Hiệu quả thực thi của phương pháp CeNP LSA được Cấu trúc tổng quát của một mạng WMN được minh họa đánh giá bằng mô phỏng, kết quả đã cho thấy rằng phương như ở Hình 2, trong đó, các AP được kết nối với nhau pháp CeNP LSA mang lại hiệu quả cao trong việc bố trí qua môi trường không dây tạo thành một tôpô hình lưới. nút mạng WMN. Một công trình nghiên cứu khác đã tập Một nút của mạng WMN có thể chỉ là một bộ định tuyến trung vào các hệ thống mô phỏng bài toán bố trí nút trong không dây (MR: Mesh Router), hoặc là một bộ định tuyến mạng WMN [4], các hệ thống mô phỏng được xem xét là không dây kết hợp với gateway (MR/GW: Mesh Router with WMN-SA [5] và WMN-PSO [6]. Thông qua kết quả mô gateway) [2]. Trong bài báo này, các nút mạng WMN được phỏng, các tác giả đã kết luận rằng, WMN-SA thực thi tốt gọi chung là AP. Các clients kết nối đến các AP qua môi hơn WMN-PSO, tuy nhiên, khi kích thước mạng lớn thì trường không dây để truy cập Internet. WMN-SA cần nhiều thời gian tính toán hơn. Với công nghệ WMN, tình trạng nghẽn cục bộ tại các Một hướng nghiên cứu khác về mạng WMN cũng đã điểm truy cập sẽ được giải quyết nhờ chức năng cân bằng được triển khai là tập trung vào việc thiết kế và triển khai tải, điều khiển lưu lượng và định tuyến tại mỗi nút. Điều mạng. Nhóm tác giả trong [7] đã đề xuất một phương pháp này cho phép giảm thiểu số yêu cầu thiết lập kết nối bị từ thiết kế và triển khai mạng WMN gồm có 10 bước với mục chối, hiệu quả sử dụng tài nguyên mạng được nâng cao. Mô tiêu giảm thiểu chi phí đầu tư. Các bước thiết kế bao gồm hình WMN cho phép giảm thiểu số cổng kết nối từ các AP phân tích khu vực, xác định yêu cầu, xác định ứng dụng và đến gateway, nghĩa là giảm thiểu chi phí đầu tư cho việc dịch vụ, ước lượng chất lượng dịch vụ, ước lượng độ cao, lắp đặt cơ sở hạ tầng. xác định vị trí lắp đặt thiết bị bên trong, lựa chọn công 60
3. 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 Vị trí khả thi với AP và người dùng giải bài toán tối ưu trong mạng WMN. Vị trí khả thi vớingười dùng Từ các kết quả nghiên cứu đã được công bố như đã đề Hình 3. Mô hình hóa vùng không gian lắp đặt mạng WMN thành cập ở trên, chúng tôi nhận thấy rằng, việc nghiên cứu về các khối chức năng. 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 mạng và vị trí cụ thể để lắp đặt tất cả các AP đó. Thuật tín hiệu truyền dẫn cho đến các quy trình thiết kế mạng. toán được đề xuất dựa trên bài toán ILP. Để có thể triển khai mạng WMN một cách hiệu quả, việc Xét vùng diện tích của cơ quan, doanh nghiệp cần triển nghiên cứu các vấn đề liên quan đến thiết kế mạng là điều khai hệ thống mạng WMN chứa các tòa nhà, văn phòng là cần thiết. Trong bài báo này, chúng tôi tiếp tục phát triển nơi có thể lắp đặt các AP. Vùng diện tích này có thể được hướng nghiên cứu này, cụ thể là tập trung vào bài toán thiết mô hình thành một không gian 3D với chiều cao là độ cao kế tôpô mạng. Mục tiêu của công trình nghiên cứu này là của toà nhà cao nhất. Chia vùng không gian này thành từng xây dựng một mạng WMN đạt hiệu quả tốt nhất với các khối đơn vị với thể tích a (m3), a chính là sai số chọn vị trí điều kiện về thiết bị và về cơ sở hạ tầng cho trước. Chúng trong thuật toán của chúng tôi. Với phương pháp này, một tôi đề xuất một phương pháp thiết kế tôpô mạng WMN sử vùng diện tích chứa các toà nhà cần lắp đặt các thiết bị AP dụng bài toán quy hoạch tuyến tính nguyên (ILP) với hàm của mạng WMN được mô hình thành một không gian 3D mục tiêu là cực tiểu hóa tổng số AP cần thiết cho một hệ là tập hợp của các khối có thể tích a (m3) như cho thấy trên thống mạng. Các điều kiện ràng buộc được xem xét sao Hình 3. Các khối đơn vị có thể tích a (m3) này được gọi là cho người sử dụng luôn được phủ sóng khi ở trong vùng các vị trí khả thi. Có hai loại vị trí khả thi trong mô hình không gian diện tích đang xét. Sau khi giải bài toán ILP, này. Loại vị trí thứ nhất là vị trí có thể lắp đặt AP, đồng kết quả thu được là tổng số AP yêu cầu, đồng thời vị trí thời có thể xuất hiện người sử dụng (các khối màu trắng cụ thể để lắp đặt mỗi AP cũng được xác định thông qua trong Hình 3). Các vị trí này chỉ có thể nằm trong các toà giá trị của các biến trong bài toán ILP. Chi tiết về phương nhà vì các AP trong trường hợp này là loại indoor, chỉ có pháp này được trình bày trong các mục tiếp theo. 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), III. THUẬT TOÁN XÁC ĐỊNH SỐ LƯỢNG AP VÀ nghĩa là chỉ có các người sử dụng có thể ở các vị trí này, VỊ TRÍ LẮP ĐẶT 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 1. Mô hình hóa thành bài toán ILP trong tổng số các vị trí khả thi với AP, chúng tôi gán cho Xét bài toán cần triển khai hệ thống mạng nội bộ cho mỗi vị trí khả thi với AP là một biến x xx, yx, zx , với xx, ( ) một cơ quan, doanh nghiệp sử dụng công nghệ WMN. Vấn yx và zx là tọa độ của vị trí x trong không gian 3 chiều. đề đặt ra đối với người thiết kế hệ thống là với một địa hình Để xác định giá trị của tất cả các biến x xx, yx, zx , chúng ( ) cho trước, cần phải xác định được tổng số AP tối thiểu cần tôi định nghĩa một hàm chọn vị trí như sau: cung cấp, các vị trí lắp đặt AP sao cho vùng phủ sóng là 1, nếu xx, yx, zx được lắp AP, tối ưu theo nghĩa ở bất kỳ vị trí nào trong cơ quan, người x xx, yx, zx = ( ) (1) sử dụng đều có thể sử dụng được các dịch vụ trong mạng ( ) (0, trong trường hợp khác. nội bộ, truy cập được Internet qua hệ thống mạng không Gọi X = x xx, yx, zx là tập tất cả các biến được gán cho { ( )} dây. Hiện nay, việc lựa chọn các vị trí để lắp đặt AP hầu tất cả các vị trí có thể lắp đặt AP trong vùng không gian hết là theo cảm tính, phụ thuộc vào ý kiến chủ quan của 3D đang xét. Với hàm chọn vị trí được xác định bởi (1), bài người thiết kế. Vì vậy, tôpô mạng được xây dựng hoàn toàn toán xác định tổng số AP yêu cầu tối thiểu và vị trí để lắp không có cơ sơ khoa học. Tổng số thiết bị AP cần thiết cho đặt AP được mô hình hóa thành bài toán tối ưu ILP như sau: một hệ thống mạng là do người thiết kế tự chọn, dẫn đến minimize x xx, yx, zx , (2) có lúc thiếu, có lúc thừa mà người thiết kế không hề hay ( ) x xx,yx,zx X 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ới các điều kiện ràng buộc sau đây. 61
4. 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: trong thuật toán. Gọi P là tập tất cả các vị trí cần được ưu Để đảm bảo người dùng có thể sử dụng các dịch vụ của tiên, khi đó điều kiện ràng buộc này được xác định bởi mạng nội bộ và truy cập Internet ở bất kỳ vị trí nào trong α u xu, yu, zu , x xx, yx, zx N, (8) cơ quan, tại mỗi vị trí khả thi đối với người sử dụng (các ( ( ) ( )) ≥ u xu,yu,zu P khối màu đen trong Hình 3) phải nằm trong vùng phủ sóng ∀ ( Õ )∈ trong đó α u xu, yu, zu , x xx, yx, zx được xác định theo 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 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. 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: 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 α u xu, yu, zu , x xx, yx, zx 1, (3) ( ( ) ( )) ≥ được tập nghiệm X . Dựa trên tọa độ của các biến xác x xx,yx,zx X { } ( Õ )∈ định vị trí trong tập X , sẽ tìm được tập vị trí cần lắp đặt ∀ { } trong đó α u xu, yu, zu , x xx, yx, zx là một hàm xác định AP thỏa mãn các điều kiện ràng buộc từ (3) đến (8). Ngoài ( ( ) ( )) phạm vi phủ sóng từ vị trí x xx, yx, zx đến vị trí người sử ra, giá trị của hàm (2) thu được chính là tổng số AP yêu ( ) dụng u xu, yu, zu . Hàm này được xác định như sau: 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 α u xu, yu, zu , x xx, yx, zx = ( ( ) ( )) có thể xem như hai mục tiêu: một là tổng số AP yêu cầu 1, nếu d u xu, yu, zu , x xx, yx, zx D, tối thiểu cho một hệ thống mạng (giá trị của hàm (2)), hai ( ( ) ( )) ≤ (4) là vị trí để lắp đặt mỗi AP (tọa độ của các biến x có giá (0, trong trường hợp khác, trị bằng 1). Đây là ưu điểm của phương pháp đề xuất và trong đó D là bán kính vùng phủ sóng của loại AP sẽ được chứng minh bởi các kết quả thực nghiệm ở mục đang xét, d u xu, yu, zu , x xx, yx, zx là khoảng cách từ tiếp theo. ( ( ) ( )) 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 ( ) 2. Thuật toán xác định số lượng AP và vị trí lắp đặt d u xu, yu, zu , x xx, yx, zx = Thuật toán xác định tổng số AP theo yêu cầu và vị trí cụ ( ( ) ( )) 2 2 2 thể để lắp đặt chúng được thực thi theo lưu đồ ở Hình 4. xx xu + yx yu + zx zu . (5) ( − ) ( − ) ( − ) Khi giải bài toán ILP theo (2), tùy theo đặc điểm của vùng q không gian cần triển khai mạng WMN mà có trường hợp 2) Ràng buộc nguyên: tìm được tập nghiệm X , nhưng cũng có trường hợp không Các biến trong tập X chỉ nhận các giá trị nguyên 1 hoặc { } tìm được tập nghiệm X thỏa mãn các điều kiện ràng buộc 0 tương ứng với các trường hợp vị trí đang xét được chọn { } từ (3) đến (8). Các trường hợp không tìm được tập nghiệm hoặc không được chọn để lắp đặt AP theo phương trình (1), X là vùng không gian cần triển khai mạng WMN có các nên điều kiện ràng buộc nguyên được xác định bởi { } tòa nhà ở xa nhau. Trong trường hợp này, khoảng cách của 0 x xx, yx, zx 1, x xx, yx, zx X. (6) 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 3) Ràng buộc về dung lượng của mỗi AP: được phủ sóng. Hay nói cách khác, điều kiện ràng buộc (4) Với mỗi AP, tại mỗi thời điểm chỉ có thể cho phép một số của bài toán ILP không thỏa mãn. Khi đó, kỹ thuật tối ưu lượng người sử dụng kết nối đồng thời đến AP, giá trị này được sử dụng để tìm nghiệm, cụ thể là tăng giá trị D trong nằm trong khoảng từ 25 đến 50 tùy theo loại AP. Để đảm điều kiện ràng buộc (4) một khoảng ∆D sao cho bài toán bảo chất lượng dịch vụ cho người sử dụng, ràng buộc này ILP theo (2) tìm được nghiệm. Bằng phương pháp chia đôi, phải được xem xét trong hệ thống mạng WMN. Gọi M là chúng ta sẽ tìm được ∆D là giá trị nhỏ nhất cần tăng thêm số người sử dụng cho phép kết nối đồng thời đến mỗi AP, cho D với độ chính xác  cho trước sao cho bài toán ILP C là tổng số người sử dụng đồng thời trong hệ thống mạng, theo (2) có nghiệm. Phương pháp chia đôi để tìm ∆D được khi đó ràng buộc về dung lượng AP được xác định bởi 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 M x xx, yx, zx C. (7) ◦ ( ) ≥ điều kiện ràng buộc từ (3) đến (8) không tìm được x xx,yx,zx X ∀ ( Õ )∈ nghiệm. Khi đó, cần tăng giá trị D trong ràng buộc (4) 4) Ràng buộc về các vùng ưu tiên (nếu có): một khoảng ∆D; Trong trường hợp có một số vị trí của người sử dụng trong Gọi D là khoảng cách lớn nhất giữa các tòa nhà ◦ max cơ quan cần phải được ưu tiên do đặc thù công việc, điều trong vùng không gian cần triển khai WMN, khi đó kiện ràng buộc về các vùng ưu tiên cần phải được xác định ∆D là một giá trị nằm trong nửa đoạn 0, D ; ( max] 62
5. 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 Vị trí khả thi với AP và người dùng các ràng buộc từ (3) đến (8) Vị trí khả thi vớingười dùng ∆D = 0; D− = 0 Hình 5. Mô hình hóa vùng diện tích của Trường Cao đẳng Công + 3 D = Dmax;  = 10− 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. Giải bài toán ILP (2) với các ộ ừ đế D = D + ∆D ràng bu c t (3) n (8) 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 D + D+ ∆D = − mặt trước (cổng chính) là 183,5 m, mặt sau (cổng phụ) là 2 195,8 m, chiều rộng phía đường Hai Bà Trưng là 129,3 m Tìm được Sai D = ∆D và phía đường Nguyễn Trường Tộ là 183,7 m. Có tất cả 17 tập nghiệm X ? − { } 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 Đúng 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 Sai + D− ∆D  D = ∆D 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 Đúng 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 Lắp đặt AP tại tọa độ của các Kết thúc điểm x X có giá trị bằng 1 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 đó. Range R Pt ( index) Hình 4. Lưu đồ thuật toán xác định tổng số và vị trí để lắp đặt 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 + Gọi D và D− là hai giá trị mà khi tăng thêm cho ràng thiết lập như sau: ◦ buộc (4) thì bài toán ILP (2) có nghiệm và không có Phạm vi phủ sóng của AP: 40 m (giá trị D trong ràng nghiệm. Ở trạng thái khởi tạo, ta gán D là giá trị nhỏ ◦ − buộc (4)), đây là vùng phủ sóng đảm bảo cho người nhất (D = 0) và D+ là giá trị lớn nhất (D+ = D ); − max sử dụng truy cập mạng tốt; Chọn ∆D = D + D+ 2, tăng giá trị D của ràng ◦ ( − )/ Sai số vị trí: 5 m; buộc (4) một khoảng ∆D (D = D + ∆D), sau đó tiến ◦ Số người sử dụng có thể kết nối đồng thời đến mỗi hành giải lại bài toán ILP; ◦ AP: 40 (giá trị M trong ràng buộc (7)); Nếu không tìm được nghiệm thì vùng tìm kiếm ∆D ◦ Tổng số người sử dụng trung bình tại mỗi thời điểm được giới hạn trong nửa đoạn ∆D, D , từ đó gán ◦ ( max] của toàn trường: 1137 (giá trị C trong ràng buộc (7), D = ∆D và giải lại bài toán ILP; − tham số này được chọn dựa trên quá trình thống kê Nếu tìm được nghiệm nhưng sai số giữa ∆D và D lớn ◦ − lưu lượng trên hệ thống mạng của Nhà trường); hơn độ chính xác  cho trước thì vùng tìm kiếm được Không thiết lập các vùng ưu tiên (ràng buộc (8)). 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 Kết quả thực thi phương pháp đề xuất được so sánh với hiện tại là giá trị nhỏ nhất với độ chính xác  cần tìm. 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 IV. KẾT QUẢ THỰC NGHIỆM theo kinh nghiệm này, vị trí lắp đặt các AP được xác định Chúng tôi đã áp dụng phương pháp được đề xuất ở theo lưu đồ thuật toán ở Hình 6. Để đảm bảo vùng phủ mục III vào việc triển khai hệ thống mạng không dây theo sóng cho toàn khuôn viên Trường và đáp ứng lưu lượng 63
6. 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 Bắt đầu 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 Phân tích độ phủ sóng tại tất cả các vị trí của người sử dụng Sai Định vị lại Đạ ầ t yêu c u? vị trí của AP Đúng Lắp đặt cố định AP Kết thúc tại vị trí hiện hành 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 Hình 7. Kết quả giải bài toán ILP trên Matlab tìm tổng số AP phương pháp được đề xuất trong bài báo này, số lượng AP yêu cầu và vị trí lắp đặt chúng. 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 Hình 8. Độ phủ sóng đến các vị trí của người sử dụng trên mặt mô tả chi tiết về các vị trí để lắp đặt toàn bộ 36 AP. đấ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. Để 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à, phương pháp được đề xuất (kết quả trên Hình 9), mặc dù kết quả thu được như cho thấy trên Hình 8 và Hình 9. Kết vị trí có nhiều AP phủ sóng nhất không đạt bằng phương quả phân thích cho thấy rằng, với phương pháp lắp đặt theo pháp kinh nghiệm, nhưng tất cả các vị trí đều có AP phủ kinh nghiệm (kết quả trên Hình 8), một số vị trí của người sóng đến. Điều này đặc biệt quan trọng trong việc đảm bảo sử dụng có đến 15 AP có thể phủ sóng đến, nhưng cũng tính liên tục đối với việc cung cấp dịch vụ cho người sử có một số vị trí không có AP nào phủ sóng đến, chẳng dụng. Để thấy rõ hơn độ phủ sóng đến các vị trí, chúng tôi hạn như ví trí có tọa độ x = 5 m và y = 100 m. Đối với vẽ biểu đồ trên Hình 10. Từ biểu đồ này ta thấy rằng, có 64
7. 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 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. 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 V. KẾT LUẬN theo phương pháp đề xuất. Để 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à 4 vị trí không có AP nào phủ sóng đến trong trường hợp trong trường hợp hệ thống mạng không dây có vùng diện triển khai theo kinh nghiệm. Với phương pháp đề xuất, tất tích rộng, tải lưu lượng lớn. Nội dung bài báo đã tập trung cả các vị trí đều nhận được sóng của các AP. Có 1 vị trí nghiên cứu những vấn đề cơ bản nhất về công nghệ WMN. chỉ có 1 AP phủ sóng đến, 3 vị trí có 2 AP phủ sóng đến, Từ đó, chúng tôi đã đề xuất một phương pháp xác định tổng các vị trí khác có từ 3 đến 12 sóng phủ đến. Ngoài ra, với số thiết bị AP yêu cầu tối thiểu của một hệ thống mạng, phương pháp kinh nghiệm, tổng số AP được chọn để lắp đồng thời xác định được vị trí cụ thể để lắp đặt các AP đặt là 38. Trong khi đó, với phương pháp đề xuất, giá trị này thỏa mãn các điều kiện ràng buộc cho trước. Chúng này được tìm ra là 36. Như vậy, với số lượng AP ít hơn tôi cũng đã thực thi thuật toán trên hệ thống mạng nội bộ nhưng vẫn đảm bảo vùng phủ sóng cho tất cả các vị trí của tại cơ sở 1 của Trường Cao đẳng Công nghiệp Huế, đã người sử dụng. xác định được tổng số AP yêu cầu và vị trí cụ thể để lắp Trên Hình 11, chúng tôi so sánh xác suất yêu cầu thiết lập đặt chúng. 65
8. 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. [5] S. Sakamoto, A. Lala, T. Oda, V. Kolici, L. Barolli, and Phương pháp kinh nghiệm F. Xhafa, “Application of WMN-SA simulation system for Phương pháp đề xuất node placement in wireless mesh networks: a case study for i a realistic scenario,” International Journal of Mobile Com- ố puting and Multimedia Communications (IJMCMC), vol. 6, ch ừ t no. 2, pp. 13–21, 2014. ị i b [6] S. Sakamoto, T. Oda, M. Ikeda, L. Barolli, and F. Xhafa, ố t n “Implementation of a new replacement method in WMN- ế PSO simulation system and its performance evaluation,” in t k ấ Proceedings of the IEEE 30th International Conference on Advanced Information Networking and Applications (AINA). Xác su 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- Số người dùng lems and resolution methods for node placement in wireless mesh networks,” in Proceedings of the 14th International 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 Conference on Network-Based Information Systems (NBiS). pháp lắp đặt theo kinh nghiệm và phương pháp đề xuất. IEEE, 2011, pp. 126–134. 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 Lê Hữu Bình sinh năm 1978 tại Quảng Trị. [1] Y. Zhang, J. Luo, and H. Hu, Wireless Mesh Networking: Ông tốt nghiệp Trường Đại học Bách Khoa Architectures, Protocols and Standards. CRC Press, 2007. Đà Nẵng năm 2001, chuyên ngành Điện tử [2] I. F. Akyildiz and X. Wang, Wireless Mesh Networks. John - Viễn thông và nhận bằng Thạc sĩ chuyên Wiley & Sons, 2009, vol. 3. ngành Công nghệ Thông tin tại Trường Đại [3] W. Wu, J. Luo, and M. Yang, “Cost-effective placement of mesh nodes in wireless mesh networks,” in Proceedings of học Khoa học, Đại học Huế, năm 2007. Từ the 5th International Conference on Pervasive Computing and năm 2015 đến nay, ông là nghiên cứu sinh Applications (ICPCA). IEEE, 2010, pp. 261–266. chuyên ngành Hệ thống Thông tin tại Học [4] S. Sakamoto, T. Oda, M. Ikeda, L. Barolli, F. Xhafa, and viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công I. Woungang, “Node Placement in Wireless Mesh Networks: nghệ Việt Nam. Hiện nay, ông là Trưởng khoa Công nghệ Thông A Comparison Study of WMN-SA and WMN-PSO Sim- tin, Trường Cao đẳng Công nghiệp Huế. Hướng nghiên cứu quan ulation Systems,” in Proceedings of the 19th International Conference on Network-Based Information Systems (NBiS). tâm của ông là công nghệ mạng không dây thế hệ mới, SDN IEEE, 2016, pp. 1–8. (Software Defined Networking), mô phỏng và thiết kế mạng. 66