TỔNG QUAN
Tổng quan về BTS
BTS là thiết bị hỗ trợ thông tin liên lạc không dây giữa các thiết bị như điện thoại và các thiết bị kết nối internet không dây.
BTS thực hiện các chức năng thu phát liên quan đến giao diện vô tuyến GSM và xử lý tín hiệu Có thể coi BTS như một mođem vô tuyến phức tạp, nhận tín hiệu từ MS và chuyển đổi thành dữ liệu để truyền đến các thiết bị khác trong mạng GSM, đồng thời nhận dữ liệu từ mạng và phát tín hiệu đến MS Vị trí của các BTS quyết định dung lượng và vùng phủ sóng của mạng.
Hình dạng phủ sóng của BTS:
Hình dạng phủ sóng của BTS có búp sóng chính là hình vòng cung, tương tự như cánh quạt với hai búp ở phía sau Mỗi trạm BTS phát sóng trong một bán kính xác định và theo ba hướng cố định: 0 độ, 120 độ và -120 độ Ngoài búp sóng chính, còn có hai nhánh búp sóng phụ nằm ở hai hướng chính từ -90 độ đến -150 độ và từ 90 độ đến 150 độ Nếu khoảng cách từ tâm phát đến vị trí xa nhất của búp chính là 40 đơn vị, thì bán kính trung bình của hai búp xung quanh là 15 đơn vị.
Hình 2.1 Hình dạng phủ sóng của BTS
Khi gọi điện bằng điện thoại di động, tín hiệu sóng vô tuyến được phát và gửi đến trạm BTS gần nhất Tại trạm BTS, tín hiệu sẽ được xử lý và truyền tiếp đến trạm BTS khác, cuối cùng đến trạm BTS gần với thuê bao mà bạn muốn gọi.
Hình 2.2 Nguyên lý hoạt động
Khu vực nghiên cứu
2.1 Tổng quan về Hà Nội
Thủ đô Hà Nội, trung tâm kinh tế và văn hóa của Việt Nam, có dân số đông đảo, do đó, sự phát triển của lĩnh vực truyền thông - thông tin cần được chú trọng để đáp ứng nhu cầu thông tin và liên lạc của người dân.
Vị trí địa lý nằm trong khoảng từ 20°53' đến 21°23' vĩ độ Bắc và 105°44' đến 106°02' kinh độ Đông
Phía Bắc giáp với tỉnh Thái Nguyên, Vĩnh Phúc
Phía Nam giáp với tỉnh Hà Nam, Hòa Bình
Phía Đông giáp với tỉnh Bắc Giang, Bắc Ninh, Hƣng Yên
Phía Tây giáp với tỉnh Hòa Bình, Phú Thọ
Với vị trí địa lý thuận lợi, thủ đô Hà Nội có cơ hội phát triển về mọi mặt, kể cả lĩnh vực truyền thông
Sau khi mở rộng địa giới hành chính vào tháng 8 năm 2008, diện tích Hà Nội đạt 3.324,92 km², nằm ở cả hai bên bờ sông Hồng, nhưng chủ yếu tập trung bên hữu ngạn.
Hình 2.3 Dữ liệu về thủ đô Hà Nội
2.2 Hiện trạng đối tƣợng nghiên cứu tại khu vực
Tính đến ngày 29/4/2014, Hà Nội có tổng cộng 5.700 trạm BTS, trong đó gần 1.200 trạm sử dụng chung cơ sở hạ tầng giữa các doanh nghiệp viễn thông hoặc được thuê từ các công ty xây dựng hạ tầng Các nhà mạng đang hoạt động bao gồm Viettel, Mobifone, VinaPhone, Vietnam Mobile và G-mobile, với Viettel, Mobifone và VinaPhone là những nhà mạng có số lượng trạm lớn nhất.
Bảng 2.1 Bảng thống kê một số khu vực hành chính từ dữ liệu thu thập được về hệ thống BTS Viettel tại Hà Nội
Diện tích (km 2 ) và tỉ lệ trạm/km2
Ba Đình 105 9.22; tỉ lệ: 11.38 trạm/km2
Cầu Giấy 119 12.04; tỉ lệ: 9.88 trạm/km2 Đông Anh 61 182.30; tỉ lệ: 0.33trạm/km2 Đống Đa 131 9.96; tỉ lệ: 13.15trạm/km2
Sơn Tây 30 113.47; tỉ lệ: 0.26trạm/km2
Cở sở lý thuyết
Phân tích không gian là quá trình sử dụng các phép toán để sắp xếp dữ liệu và thuộc tính liên quan, thường được áp dụng để giải quyết các vấn đề cụ thể như nhận diện vùng an ninh cao, xác định các đoạn đường cần sửa chữa, và tìm vị trí kinh doanh phù hợp Các phép toán không gian có thể được sử dụng liên tiếp để giải quyết vấn đề, với mỗi phép toán tạo ra sản phẩm đầu ra có thể áp dụng cho các phép toán khác Do đó, việc lựa chọn các phép toán không gian thích hợp và áp dụng chúng theo trình tự đúng là rất quan trọng trong phân tích không gian.
Xử lý thông tin không gian đóng vai trò quan trọng trong hệ thống thông tin địa lý (GIS), vì nó giúp cấu hình dữ liệu thành định dạng phù hợp cho việc hiển thị và phân tích không gian hiệu quả.
Hai nhóm phương pháp xử lý:
Phân tích đơn lớp: đề cập đến chức năng áp dụng mỗi lần một lớp dữ liệu
Phân tích đa lớp cho phép áp dụng các chức năng trên nhiều lớp dữ liệu, trong khi bài viết này sẽ tập trung vào phương pháp phân tích đơn lớp thông qua các thủ tục cụ thể.
Thủ tục xóa (erase): Bỏ đi phần giao giữa lớp đầu vào (input) và lớp clip Kết quả là ta đƣợc phần đầu vào
Hình 2.4 Thủ tục erase trong phân tích đơn lớp
Tạo vùng đệm (buffer): Tạo lớp vùng đệm với khoảng cách cho trước Kết quả đầu ra là vùng đồng khoảng cách
Bề rộng của vùng đệm là một hằng số, xác định cách áp dụng cho tất cả các đối tượng hoặc dựa trên giá trị thuộc tính cụ thể.
Hình 2.5 Ảnh minh họa tạo vùng đệm không gian
Một đồ thị có hướng G=(X, U) được định nghĩa bởi:
Tập hợp X ≠ ∅ đƣợc gọi là tập các đỉnh của đồ thị;
Tập hợp U là tập các cạnh của đồ thị;
Mỗi cạnh u∈U đƣợc liên kết với một cặp đỉnh (i, j) ∈ X2
Hình vẽ bên là minh họa hình học của một đồ thị có:
Ánh xạ φ định nghĩa gồm:
u1 và u2 liên kết với cặp (A, B)
Hình 2.6 Đồ thị có hướng
Nếu không phân biệt thứ tự của cặp đỉnh liên kết với mỗi cạnh, ta sẽ có đồ thị vô hướng Đồ thị vô hướng G = (X,E) được định nghĩa bởi tập hợp các đỉnh X và các cạnh E.
Tập hợp X ≠ ∅ đƣợc gọi là tập các đỉnh của đồ thị
Tập hợp E là tập các đỉnh của đồ thị
Mỗi cạnh e ∈ E đƣợc liên kết với một cặp đỉnh {i, j} không phân biệt thứ tự
Hình vẽ dưới là minh họa hình học của một đồ thị có
Ánh xạ φ định nghĩa gồm:
u1 và u2 liên kết với cặp (A, B)
Một số từ ngữ và quy ƣớc:
Khi một cạnh u liên kết với cặp đỉnh (i, j):
Cạnh u kề với đỉnh i và j( hay nói đỉnh i và đỉnh j kề với cạnh u)
Ta có thể nói u=(i, j), nhƣ vậy có lúc ta viết u=(i, j) và v=(i, j) nhƣng lại hiểu u
Nếu đồ thị vô hướng, ta nói hai đỉnh i và j được nối với nhau Nếu đồ thị có hướng, ta nói đỉnh i được nối với đỉnh j
Trong đồ thị có hướng, cạnh được xác định bởi đỉnh bắt đầu i và đỉnh kết thúc j Cạnh này được mô tả là đi ra khỏi đỉnh i và đi vào đỉnh j.
Hình 2.7 Đồ thị vô hướng
3.2.2 Tập bền vững trong (independent set)
Tập bền vững trong một đồ thị không liền kề nhau, còn gọi là tập độc lập, bao gồm các đỉnh mà giữa chúng không có cạnh kết nối Điều này có nghĩa là, trong một tập hợp I các đỉnh của đồ thị G, không tồn tại cạnh nào liên kết hai đỉnh trong tập đó Mỗi cạnh trong đồ thị sẽ chứa ít nhất một đỉnh thuộc tập I Kích thước của một bộ độc lập được xác định bởi số lượng đỉnh mà nó chứa, và trong một đồ thị có thể tồn tại nhiều tập độc lập với kích thước khác nhau.
Hình 2.8 Ảnh minh họa tập bền vững trong (Independent set)
Theo ví dụ trong ảnh, tập bền vững trong là một tập hợp các điểm màu xanh
3.2.3 Tập bền vững trong cực đại (Maximum Independent set)
Trong đồ thị G, các tập I1, I2, I3,… được gọi là các tập bền vững trong Tập bền vững trong cực đại là tập có số phần tử nhiều nhất Tối ưu hóa bằng phương pháp Maximum Independent Set luôn là một bài toán khó, thuộc loại NP (Non-deterministic Polynomial).
Ta xét ví dụ sau, cho một đồ thị G có dạng:
Hình 2.9 Ví dụ về Maximum Independent set
Ta có các tập độc lập đƣợc liệt kê trong bảng sau:
Bảng 2.2 Tổng hợp các phần tử độc lập
Vậy ta có hai tập I 2 và I 5 là tập Maximum Indepent set
3.3 Phép biến đổi trong không gian hai chiều
Một phép biến đổi hai chiều chuyển đổi điểm P trong mặt phẳng thành điểm mới Q theo một quy luật nhất định Cụ thể, phép biến đổi này thực hiện việc chuyển đổi tọa độ của điểm P thành tọa độ mới Q, và điều này có thể được mô tả bằng một phương trình cụ thể.
Trong khuôn khổ đề tài, chúng ta chỉ khảo sát các phép biến đổi affine
Một phép biến đổi affine hai chiều (2D) có tên T sẽ biến điểm P(P x , P y ) thành Q(Q x ,Q y ) theo hệ phương trình sau:
Q y = bP x + dP y + tr y Viết dưới dạng ma trận, ta có:
) + (tr x ,tr y ) Hay ở dạng rút gọn hơn là : Q = PM + tr
Phép biến đổi affine được định nghĩa với các điểm Q = (Q x , Q y ), P = (P x , P y ), và tr = (tr x , tr y ) trong không gian, cùng với ma trận M Để đảm bảo tính không suy biến, cần giả sử rằng a*d ≠ b*c Thực chất, phép biến đổi affine là một phép biến đổi tuyến tính, nhưng có thêm độ dời tr, được gọi là vector offset hay vector tịnh tiến.
Phép biến đổi affine được hình thành từ việc kết hợp bốn phép biến đổi cơ bản: tịnh tiến, biến đổi tỉ lệ, quay và biến dạng.
Trong phạm vi của đề tài này, ta chỉ ứng dụng phép Quay
Phép quay quanh gốc tọa độ:
Lúc này vector offset tr = 0 và Q = T(P) có dạng:
Q y = P x * sin(α) – P y * cos(α) Giá trị dương của góc α được xác định theo ngược chiều kim đồng hồ
Ma trận M trong trường hợp này là:
Hình 2.10 Phép quay quanh gốc tọa độ một góc α
Phép quay quanh một điểm:
Phép làm cho điểm P(P x , P y ) quay quanh điểm V(V x , V y ) thành Q(Q x , Q y ), đƣợc xây dựng từ những phép biến đổi sau:
Tịnh tiến (-V x , V y ) (Đưa về trường hợp quay quanh gốc tọa độ), ta được hai điểm P ’ và Q ’
Quay góc α quanh O (gốc tọa độ)
Tịnh tiến (V x , V y ) về lại vị trí cũ
Ta có công thức biến đổi:
Q = (P – tr)M + tr Hay: (Q x , Q y ) = (P x , P y )M + (1 - M)tr Trong đó: tr = (V x , V y )
Hình 2.11 Phép quay quanh một điểm V một góc α
SQL là ngôn ngữ máy tính dùng để giao tiếp với hệ quản trị cơ sở dữ liệu, cho phép người quản lý thực hiện các thao tác như thêm, xóa và sửa dữ liệu Hiện nay, SQL đã được mở rộng với nhiều chức năng mới, đặc biệt là khả năng truy vấn kiểu dữ liệu không gian, đáp ứng nhu cầu ngày càng cao về trực quan hóa dữ liệu.
Tình hình nghiên cứu
Nhiều nghiên cứu trong và ngoài nước đã chỉ ra rằng ở Việt Nam, các công trình nghiên cứu thường được thực hiện sau quá trình xây dựng Điều này dẫn đến việc nhiều trạm BTS được xây dựng không đúng tiêu chuẩn về khoảng cách đặt trạm.
Nhiều bài báo cáo về ứng dụng GIS để quy hoạch quản lý:
Vincenzo Barrile đã phát triển một dự án tại Ý, sử dụng GIS để hỗ trợ quy hoạch các trạm phát sóng BTS cho mạng di động trong môi trường đô thị Dự án này áp dụng các công cụ và thuật toán GIS nhằm tối ưu hóa hoạt động bằng cách xác định vị trí thích hợp để lắp đặt các trạm BTS, đồng thời sử dụng dữ liệu không gian ba chiều để nâng cao hiệu quả quy hoạch.
Kuboye B M., Dada O.A., và Akinwonmi F.C đã sử dụng GIS để giám sát vị trí các trạm gốc GSM, nhằm quản lý hiệu quả các trạm BTS trong khu vực Nghiên cứu này tại Thụy Sĩ cung cấp một tập hợp dữ liệu trực quan giúp theo dõi và quản lý các trạm một cách dễ dàng hơn.
SunZou, a base station information management system based on GIS in China, utilizes ARCGIS tools to effectively manage large volumes of information This system supports visual and efficient spatial data analysis and evaluation.
Ngày càng nhiều trạm BTS được xây dựng nhằm nâng cao chất lượng cuộc sống, nhưng vẫn tồn tại một số vấn đề về vị trí không hợp lý Nhiều dự án ứng dụng GIS có thể hỗ trợ giải quyết những bất cập này, mang lại hiệu quả cho việc quy hoạch và phát triển hạ tầng viễn thông.
TS Đoàn Bảo Hùng (2011) đã trình bày ứng dụng GIS trong quản lý hạ tầng ngầm cáp viễn thông và quy hoạch trạm BTS tại TP Huế Báo cáo nhấn mạnh việc sử dụng khả năng phân tích không gian của GIS kết hợp với công nghệ thông tin, lý thuyết đồ thị và phương pháp quy hoạch đô thị Điều này giúp quản lý hiệu quả tình trạng sử dụng chung đường cổng cáp của nhiều nhà mạng và nâng cao khả năng chia sẻ thông tin trong ngành viễn thông.
Công ty cổ phần công nghệ thông tin địa lý eK đã phát triển ứng dụng WebGIS để quản lý cơ sở hạ tầng bưu chính viễn thông tại Quảng Ninh Ứng dụng này hỗ trợ quy hoạch mạng lưới, cấp phép viễn thông và tạo điều kiện chia sẻ thông tin giữa các doanh nghiệp hoạt động trong khu vực.
Đào Minh Tâm đã xây dựng hệ thống quản lý hạ tầng Bưu chính – Viễn thông ứng dụng GIS, thông qua hội thảo ứng dụng GIS toàn quốc Hệ thống này bao gồm việc phát triển phần mềm độc lập bằng ArcEngine để quản lý dữ liệu trên SQL Server 2008, nhằm hỗ trợ thiết kế mạng lưới, giám sát mạng, quản lý cơ sở hạ tầng và quản lý khách hàng.
Tổng quan về phần mềm sử dụng trong đề tài
PostgreSQL là hệ quản trị cơ sở dữ liệu quan hệ và đối tượng, có hơn 20 năm lịch sử phát triển từ dự án của Đại học California tại Berkeley, Mỹ Hiện nay, PostgreSQL đảm bảo tuân thủ cao với các tiêu chuẩn ANSI-SQL 92/99 và hoàn toàn tuân thủ các nguyên tắc ACID.
PostgreSQL hỗ trợ phần lớn tiêu chu n SQL và đƣa ra nhiều tính năng hiện đại:
Các truy vấn phức tạp
Các khóa phụ (foreign keys)
Tính toàn vẹn của giao dịch
Kiểm soát đồng thời nhiều phiên bản
Hơn nữa, PostgreSQL có thể được người sử dụng mở rộng theo nhiều cách thức, ví dụ bằng việc bổ sung thêm mới
các hàm tổng hợp (aggregate functions)
các phương pháp đánh chỉ số
các ngôn ngữ thủ tục
PostgreSQL là một hệ quản trị cơ sở dữ liệu mã nguồn mở với giấy phép tự do, cho phép người dùng tự do sử dụng, sửa đổi và phân phối mà không mất phí Điều này mang lại sự linh hoạt cho các mục đích cá nhân, thương mại hoặc học thuật.
5.1.2 So sánh Postgresql và các HQTCSDL khác
So sánh hệ quản trị PostgreSQL với các hệ quản trị cơ sở dữ liệu khác giúp chúng ta hiểu rõ hơn về ưu điểm và nhược điểm của PostgreSQL Thông tin so sánh bao gồm hệ điều hành hỗ trợ, từ đó cung cấp cái nhìn tổng quan về khả năng tương thích và hiệu suất của PostgreSQL trong môi trường khác nhau.
Trang 26 hiệu suất lưu trữ số liệu, so sánh tính năng bảo mật , sự so sánh giữa Posgresql với các HQTCSDLQH nhƣ: DB2, Microsoft SQL Server, Oracle, MySQL
Hệ điều hành hỗ trợ
Bảng 2.3 So sánh tính năng hệ điều hành hỗ trợ
DB2 Có Không Có Có
Microsoft SQL Server Có Không Không Không
MySQL Có Có Có Có
Oracle Có Có Có Có
Postgresql Có Có Có Có
Bảng 2.4 So sánh hiệu suất lưu trữ dữ liệu Độ lớn CSDL tối đa Độ lớn bảng tối đa Độ lớn hàng tối đa
Số cột tối đa cho mỗi hàng
524258 TB 524258 TB Không giới hạn 20000
MySQL Không giới hạn 16 TB 64 KB 4096
Postgresql Không giới hạn 32 TB 1.6 TB 1600
Bảng 2.5 So sánh tính năng bảo mật
Mã hóa mạng có nguồn gốc
Quy định mật kh u phức tạp
Microsoft SQL Server Có Có Có
Postgresql hỗ trợ tất cả các hệ điều hành phổ biến và là phần mềm mã nguồn mở, khác với các hệ quản trị cơ sở dữ liệu thương mại như Microsoft SQL, Oracle và DB2 Mặc dù khả năng lưu trữ dữ liệu của Postgresql rất lớn, vấn đề bảo mật của nó không hoàn hảo như các phần mềm thương mại, nhưng vẫn đảm bảo an toàn cho dữ liệu Do đó, chúng tôi đã chọn Postgresql làm phần mềm quản trị cơ sở dữ liệu để lưu trữ và quản lý dữ liệu.
PostGIS, được phát triển bởi Refraction Research Inc, là một dự án nghiên cứu công nghệ cơ sở dữ liệu không gian Nó cung cấp hỗ trợ cho các đối tượng địa lý trong cơ sở dữ liệu quan hệ.
PostgreSQL với PostGIS "kích hoạt khả năng không gian", biến PostgreSQL thành một cơ sở dữ liệu không gian hỗ trợ cho GIS PostGIS không chỉ sở hữu đầy đủ các đặc điểm của cơ sở dữ liệu không gian mà còn cung cấp những tính năng đặc biệt khác, giúp nâng cao hiệu suất và khả năng xử lý dữ liệu không gian.
Geometric data types such as Point, Linestring, Polygon, Multipoint, Multilinestring, Multipolygons, and Geometrycollection are stored as geometric objects.
Cung cấp các toán tử áp dụng trong đề tài:
ST_Difference: trả về phần không giao nhau giữa lớp đối tƣợng A và lớp đối tƣợng B
ST_Geomfromtext: trả về lớp đối tƣợng hình học(geometry)
ST_Buffer: tạo vùng đệm cho đối tƣợng hình học
ST_Rotate: xoay đối tượng theo chiều ngược chiều kim đồng hồ tương ứng với tâm
ArcGIS là phần mềm GIS của ESRI, cung cấp nhiều tính năng khác nhau tùy thuộc vào loại bản quyền, bao gồm ArcView, ArcEditor và ArcInfo Trong số này, ArcInfo có chi phí bản quyền cao nhất và sở hữu nhiều chức năng vượt trội nhất.
ERSI có những sản ph m chủ yếu sau:
ArcGIS gồm các ứng dụng chính ArcMap, ArcCatalog, ArcToolbox
ArcIMS dùng để đƣa dữ liệu GIS lên Web
ArcPad dùng cho các thiết bị Mobile
ArcSDE dùng làm cầu nối truy xuất vào các hệ quản trị cơ sở dữ liệu
ArcExplore dùng truy cập nguồn dữ liệu trên Web
ArcGIS server hỗ trợ các chức năng bên phía server cũng nhƣ triển khai các ứng dụng qua mạng
ArcGIS cung cấp nhiều phần mở rộng (Extension) với các chức năng chuyên biệt, bao gồm phân tích không gian (Spatial Analyst), phân tích 3D (3D Analyst), phân tích mạng (Network Analyst), xử lý dữ liệu và thống kê không gian Những phần mở rộng này giúp tối ưu hóa khả năng phân tích và xử lý dữ liệu địa lý trong các ứng dụng GIS.
ArcGIS hỗ trợ đọc đƣợc nhiều định dạng dữ liệu khác nhau (khoảng 300 định dạng) nhƣ shapefile, geodatabase, AutoCad, Raster, Coverage,
Hiện nay, ArcGIS được áp dụng phổ biến trong các lĩnh vực của Hệ thống thông tin địa lý, bao gồm quản lý môi trường, đất đai, xã hội và kinh tế.
ArcGIS Engine là phần mềm phát triển cho phép tạo ra các ứng dụng GIS tùy chỉnh, hoạt động trên Desktop Nó bao gồm các thành phần cốt lõi để xây dựng sản phẩm cho ArcGIS Desktop Với ArcGIS Engine, bạn có thể phát triển ứng dụng độc lập hoặc mở rộng các ứng dụng hiện có, nhằm cung cấp giải pháp không gian cho cả người dùng GIS và những người không sử dụng GIS.
ArcGIS Engine cung cấp các giao diện lập trình (APIs) cho các ngôn ngữ như COM, NET, Java và C++ Những APIs này không chỉ đi kèm với tài liệu chi tiết mà còn bao gồm nhiều thành phần hỗ trợ, giúp lập trình viên dễ dàng phát triển ứng dụng ArcGIS.
Cấu trúc GIS chu n, ArcObjects, trên đó họ phần mềm ArcGIS đƣợc xây dựng
Tiết kiệm chi phí trong khi sử dụng: chỉ một license ArcGIS Engine Runtime hay một ArcGIS Desktop trên một máy
Người phát triển dễ dàng điều khiển trên ActiveX, NET và Java
Ngôn ngữ chu n nhƣ COM, NET, Java, and C++ và nền Windows, Linux, Solaris
Mô hình đối tượng, tiện ích, mẫu và tài liệu cho người pháp triển
Sản phẩm này được phát triển bởi Ashay Dharwadker tại Viện Toán Học Ấn Độ, sử dụng nền tảng C++ Phần mềm giúp xác định các tập bền vững cực đại thông qua việc xây dựng tập các đỉnh thành ma trận, với kết quả được xuất ra theo cột của ma trận.
Hình 2.11 Giao diện phần mềm
Tổng quan về bài toán hỗ trợ vận hành trạm BTS
Bài toán chọn k BTS từ m BTS với mỗi BTS có v hướng phát tương đương với việc tính số tổ hợp chập k từ (mv) phần tử, trong đó v là số không đổi Do đó, số lượng nghiệm tối đa có thể đạt được là rất lớn, tùy thuộc vào giá trị của m, k và v.
Giả sử có 100 BTS với 3 hướng và chọn được 70 BTS, số lượng nghiệm có thể đạt được sẽ tăng lên Việc chọn nhiều BTS hơn và đảm bảo các tiêu chí về vùng phủ trùng sẽ dẫn đến việc mở rộng vùng phủ sóng.
Do đó, định hướng bài toán sẽ tìm vùng phủ sóng lớn nhất thông qua việc tìm kiếm tập BTS (bao gồm hướng mỗi BTS) là lớn nhất
6.2 Mô hình hóa bài toán
Bài toán của đề tài thực hiện gồm hai ràng buộc:
Ràng buộc thứ nhất liên quan đến hướng phát sóng, trong đó mỗi BTS chỉ được phép chọn một trong ba hướng phát sóng duy nhất Đây là một quy định nghiêm ngặt và không thể thay đổi.
Ràng buộc thứ hai trong việc chọn hướng phủ sóng khi có hai BTS cùng phục vụ một khu vực liên quan đến diện tích phủ sóng Điều kiện này có thể được xác định dựa trên kinh nghiệm của chuyên gia cũng như thực tế sử dụng và lựa chọn Các tham số quan trọng có thể bao gồm công suất, số lượng cuộc gọi trong khu vực và diện tích phủ sóng Trong tiểu luận này, diện tích sẽ được chọn làm tham số ràng buộc thứ hai, với chỉ số được điều chỉnh theo yêu cầu của người quản lý.
Hai ràng buộc có thể được mô tả bằng các phương trình
x i,k là BTS thứ i có hướng k, k = {0, 120, -120}
f(x i,k ), f(x j,k ) là diện tích vùng không gian của xi và x j có cùng hướng k
S(f(x i,k ), f(x j,k )) là diện tích vùng chung giữa hai BTS xi và x j
||g(x i,k ), g(x j,k )|| là tiêu chu n diện tích phần chung đặt ra
Dựa trên phân tích, mỗi vùng phát sóng của trạm BTS có thể được coi là một đỉnh trong đồ thị, trong khi các cạnh giữa hai đỉnh tương ứng đại diện cho các vùng phủ sóng giao nhau Điều này tạo ra một đồ thị phẳng hai chiều, cho phép áp dụng bài toán tìm tập độc lập cực đại Cụ thể, trong một đồ thị G với các đỉnh và cạnh, tập độc lập cực đại là tập hợp các đỉnh mà không có hai đỉnh kề nhau Tập độc lập này sẽ thỏa mãn các điều kiện ràng buộc và phần chọn nghiệm sẽ dựa trên các thuộc tính của tập nghiệm.
Dữ liệu và phương pháp nghiên cứu
Mô tả dữ liệu
Dữ liệu nền: shapefile Hà Nội, trong đó chứa thông tin về tên quận/huyện và cột kiểu dữ liệu không gian
Bảng 3.1 Bảng dữ liệu nền
Tên trường của bảng dữ liệu Kiểu dữ liệu Chú giải
Id Serial Mã quận/huyện của Hà Nội
Quan_huyen Character varying Quận/huyện
Ten Character varying Tên quận/huyện geom Geometry(polygon) Chứa thông tin không gian
Dữ liệu trạm BTS được thu thập từ dự án “Ứng dụng WebGIS trong quản lý cơ sở hạ tầng bưu chính Viễn Thông” của đội ngũ ekgis, chủ yếu tập trung vào vị trí địa lý của các trạm BTS.
Bảng 3.2 Bảng dữ liệu trạm BTS
The data table includes the following fields: "malienket," which is a character varying type representing the link code; "madoituong," an integer type denoting the object code; and "kinhdobts," a double precision type indicating the coordinates of the BTS station.
Trang 34 vidobts Double precision bản đồ loaitram Character varying Loại trạm
Vitribts Geometry(point) Chứa thông tin không gian
Dữ liệu thông số kỹ thuật:
Dữ liệu trong bài viết được thu thập từ dự án “Ứng dụng WebGIS trong quản lý cơ sở hạ tầng bưu chính Viễn Thông” của đội ngũ ekgis, bao gồm các thông số quan trọng như bán kính phát sóng và công suất hoạt động của BTS.
Bảng 3.3 Bảng dữ liệu về các thông số kỹ thuật
Tên trường của bảng dữ liệu
Kiểu dữ liệu Chú giải
Chieucaoangten double precision Chiều cao của cột BTS
Congsuat double precision Công suất hoạt động của trạm BTS Tansothuphat double precision Tần số thu phát trạm BTS
Tamphusong double precision Bán kính phát sóng của trạm BTS
Đồng bộ dữ liệu
Dữ liệu thu thập trong đề tài chưa được đồng bộ hóa hoàn toàn Cần chuyển đổi dữ liệu bán kính phát sóng từ mét sang độ thập phân (Decimal Degrees) bằng cách thực hiện các phép tính cụ thể.
Bán kính chuyển đổi = Bán kính thu thập * 9.7982 / 1100000
Dữ liệu phủ sóng
Bảng dữ liệu này có đƣợc thông qua quá trình xử lý dữ liệu thu thập
Bảng 3.4 Bảng dữ liệu phủ sóng
Tên trường của bảng dữ liệu
Kiểu dữ liệu Chú giải
Dữ liệu không gian bao gồm các thông tin quan trọng như mã đối tượng kinhdobts và tọa độ của trạm BTS trên bản đồ (vidobts) Các tọa độ của điểm A (kinhdo_a, vido_a) và điểm B (kinhdo_b, vido_b) cũng được ghi lại Thêm vào đó, tọa độ tâm i (kinhdo_i, vido_i) cùng với bán kính phát sóng (bankinh) và sóng phát hướng 0 độ (phu_song_0) được lưu trữ dưới dạng hình học (Geometry).
Trang 36 phu_song_120 Geometry(polygon) Sóng phát hướng 120 độ phu_song_am_120 Geometry(polygon) Sóng phát hướng -120 độ
2.1 Nội dung thực hiện đề tài
Thu thập dữ liệu đầu vào: tọa độ địa lý các trạm BTS, bản đồ nền Hà Nội,… và đƣa vào hệ quản trị CSDL Postgresql để quản lý
Ứng dụng SQL không gian để thực hiện việc truy vấn các dữ liệu không gian - địa lý, đồng thời cũng xử lý dữ liệu thu thập đƣợc
Thiết kế phần mềm thực hiện quy trình xây dựng mô hình phủ sóng, mô hình hóa mạng lưới phủ sóng BTS, khung nhìn dữ liệu không gian
Giải toán độc lập cực đại (independent set)
Chọn nghiệm từ kết quả đã giải và hiển thị dữ liệu không gian
Dựa trên các phân tích đã thực hiện, quy trình đề xuất cho một ứng dụng ban đầu nhằm giải quyết bài toán không gian phủ sóng hai chiều được thực hiện như sau:
Bước đầu tiên trong quá trình thu thập dữ liệu điểm phát sóng BTS là ghi nhận các thông tin quan trọng như vị trí kinh độ và vĩ độ (lon/lat), bán kính phát sóng (R), cường độ phát sóng (W), cũng như cấu hình và hình dạng phát sóng, bao gồm số lượng hướng phát và hình dạng sóng phát ra từ một BTS.
Bước 2: Xấp xỉ hình học dạng phát sóng
Bước 3: Xây dựng mô hình lớp dữ liệu không gian phủ sóng trên tất cả các hướng của m điểm phát sóng BTS
Bước 4: Mô hình hóa lớp phủ sóng thành đồ thị (graph) với:
Các đỉnh đại diện cho các vùng phủ sóng;
Các đỉnh vùng phủ sóng cùng 1 BTS sẽ kết nối với nhau trong đồ thị;
Các vùng phủ sóng có chung vùng phủ sẽ là các đỉnh có cạnh nối với nhau trong đồ thị;
Bước 5: Giải bài toán tập độc lập cực đại (maximum independent set) cho đồ thị
Bước 6: Chọn nghiệm, ánh xạ sang bản đồ tập nghiệm tìm được ở bước 5
Sơ đồ quy trình thực hiện đề tài
2.3 Chi tiết quy trình thực hiện
Xây dựng mô hình phủ sóng
Giải bài toán độc lập cực đại
Chọn nghiệm và hiển thị không gian
Số lƣợng dữ liệu thu thập là 1682 BTS Viettel Loại BTS đƣợc sử dụng là loại AGISSON DX-890-960-65-18i-0F
Hình dạng sóng phát của BTS (theo loại BTS)
Các thông tin về BTS về: bán kính phủ sóng
Dữ liệu không gian đƣợc thu thập với thông tin kinh vĩ độ
2.3.2 Xấp xỉ hình học dạng phát sóng phủ
Mỗi BTS có tầm hoạt động theo bán kính nhất định, có thể phân loại thành ba dạng: sóng phủ tối đa, sóng phủ thông thường và sóng phủ tối thiểu Dạng tối đa cho phép sóng phủ xa nhất, trong khi dạng tối thiểu cho phép sóng phủ gần nhất Tầm hoạt động của sóng phụ thuộc vào nhiều yếu tố như thời tiết, độ ẩm, bụi, khí thải và thời gian sử dụng của BTS Trong nghiên cứu này, chúng tôi giả định tầm hoạt động của sóng ở trường hợp tối thiểu do Hà Nội có nhiều hoạt động có thể làm giảm chất lượng sóng.
Với dạng BTS tại Hà Nội đƣợc khảo sát ở phần trên, chúng ta chọn xấp xỉ hình học nhƣ sau đối với vùng phủ sóng (vùng sậm) nhƣ sau:
Từ tâm I, nơi đặt BTS, đến vị trí phát sóng xa nhất có thể chia thành 08 phần bằng nhau (tổng 08 phần là tầm hoạt động của sóng);
Vùng phủ xem nhƣ là một phần cung tròn lớn với tâm i đặt tại điểm cách tâm I một khoảng theo hướng Đông là: ( ) phần, (mỗi phần là bán kính R);
Phần cung tròn được giới hạn bởi hai đường thẳng từ tâm I và lần lượt có góc là
150 độ và -150 độ (nhƣ hình);
Hình 3.1 Xấp xỉ hình học cho vùng phủ sóng
Việc xấp xỉ hình học bằng các hình tương đương và thay thế sóng phức tạp bằng đường thẳng giúp giảm thiểu khối lượng tính toán Đồng thời, lựa chọn xử lý trong trường hợp tầm sóng phủ ngắn nhất sẽ đảm bảo xấp xỉ hình học không vượt quá vùng phủ thực tế, đồng thời vẫn đảm bảo tính toán chính xác Hơn nữa, xấp xỉ hình học còn là cơ sở để tính toán các giá trị khác từ hai đại lượng hình học, bao gồm tâm I và bán kính phủ sóng ban đầu R.
Từ tâm i của cung tròn sóng;
Bán kính r của cung tròn tâm i
Vị trí tọa độ chi tiết của tam giác đều IAB, với một đỉnh I và 2 đỉnh thuộc đường tròn tâm I, chắn ở các góc 150 độ và -150 độ
Các bước cụ thể được thực hiện trong quy trình
Từ dữ liệu thu thập sau khi đã đồng bộ, các bước thực hiện được trình bày cụ thể nhƣ sau:
Bước đầu tiên là tạo buffer cho từng điểm BTS (tâm I), với bán kính của buffer tương ứng với từng dòng trong dữ liệu bảng Kết quả thu được sẽ như hình sau:
Hình 3.2 Buffer của từng điểm BTS
Bước 2: Tạo điểm A và B Trong đó, điểm A và B được tạo ra bằng cách:
Điểm A: kinh độ điểm A= kinh độ BTS – bán kính phủ sóng * √ vĩ độ điểm A= vĩ độ BTS – bán kính phủ sóng * 0.5
Điểm B kinh độ điểm B = kinh độ BTS – bán kính phủ sóng * √ vĩ độ điểm B = vĩ độ BTS + bán kính phủ sóng * 0.5
Hình 3.3 Điểm A, B và điểm BTS
Bước 3: Ta tạo Polygon từ 3 điểm polygon vừa tạo được Ở bước này ta dùng toán tử ST_Geomfromtext Kết quả, ta có đƣợc:
Bước 4: Ta tạo điểm i làm tâm của cung tròn thể hiện dạng hình học phủ sóng cho BTS
Kinh độ i = kinh độ của bts + bán kính phủ sóng *
Vĩ độ i = vĩ độ của bts
Hình 3.5 Kết quả tạo điểm i
Bước 5: Tạo buffer cho điểm i
Hình 3.5 Tạo buffer của điểm i
Bước 7: Trên bản đồ, tạo vùng phủ sóng cho từng BTS bằng toán tử ST_Different để xác định phần buffer_i không giao với tam giác IAB Mỗi trạm có ba hướng xoay, dẫn đến việc mỗi dòng dữ liệu sẽ bao gồm ba cột kiểu geometry tương ứng: phu_song_0, phu_song_120, và phu_song_am_120.
Hình 3.6 Điểm BTS và hướng phát sóng 0 o
2.3.3 Xây dựng mô hình lớp dữ liệu không gian phủ sóng trên tất cả các hướng của m điểm phát sóng BTS
Dựa vào quy trình xấp xỉ hình học và các hướng xoay của một BTS, chúng ta có thể tạo ra cơ sở dữ liệu không gian về các vùng phủ sóng của mạng lưới BTS Khi thay đổi hướng, vùng phủ sóng của BTS vẫn giữ nguyên hình học, chỉ thay đổi về phương hướng Do đó, việc xây dựng cơ sở dữ liệu sẽ bắt đầu bằng cách xác định một hướng cho tất cả các BTS, sau đó thực hiện các phép xoay cần thiết.
Tại Hà Nội, các loại BTS có thể được điều chỉnh theo hai hướng: 120 độ và -120 độ (hoặc 240 độ) Điều này cho phép tối ưu hóa vùng phủ sóng của các BTS.
Trang 47 đẳng hướng nên việc định vùng phủ sóng chỉ cần xác định và tính toán đối với một hướng và vùng phủ của hai hướng còn lại sẽ thu được bằng phép xoay hình học như sau:
Tâm xoay: tâm I của BTS;
Góc xoay: và tương ứng với việc xoay 120 độ hoặc -120 độ (240 độ)
Với phép xoay trên, ta có ma trận xoay là (với k=±2 tương ứng với việc xoay 120 độ hoặc -120 độ):
Mô hình hóa mạng lưới phủ sóng BTS
Mô hình hóa mạng lưới phủ sóng BTS thành đồ thị sử dụng ma trận kề Ma trận kề hai chiều a[,] được định nghĩa sao cho nếu hai đỉnh i và j của đồ thị có kết nối, thì a[i,j] = a[j,i] = 1; ngược lại, giá trị sẽ là 0 Do đó, các giá trị trên đường chéo của ma trận sẽ bằng 0, tức là a[i,i] = 0.
2.3.4 Giải bài toán độc lập cực đại trong đồ thị
Trong bài viết này, chúng tôi áp dụng gói phần mềm Independent Set Algorithm đã được trình bày ở chương 2 để xác định phương án tối ưu cho việc phát sóng của từng trạm BTS.
Dựa trên kết quả của ma trận đã xây dựng trong quy trình trước, chúng ta áp dụng thuật toán Independent Set để tìm ra nghiệm Cuối cùng, mặc dù có thể có nhiều nghiệm, nhưng chúng ta chỉ chọn một nghiệm để thực thi vào bảng dữ liệu.
Hình 3.7 Kết quả giải bài toán tập độc
Ví dụ một kết quả chạy thử nghiệm nhƣ trong hình Trong đó:
Số thứ tự nghiệm 1., 2., 3.,… tương ứng với số dòng, mỗi dòng là một nghiệm
Independent set (27): số cột lấy đƣợc từ ma trận có đƣợc từ quy trình trên, ở đây là 27 cột
1 5 7 11 17 …: số thứ tự các cột ma trận tính từ trái sang
2.3.5 Hiển thị dữ liệu không gian
Chọn ra một nghiệm trong tập nghiệm từ kết quả giải toán để hiển thị lên khung nhìn
Tập nghiệm bao gồm các phương án khả thi, và từ đó, việc sắp xếp các thuộc tính đã chọn giúp đạt được kết quả nghiệm tốt nhất Các tiêu chuẩn nghiệm đóng vai trò quan trọng trong quá trình này.
Nghiệm có tổng công suất P lớn nhất;
Nghiệm có diện tích vùng phủ lớn nhất;
Nghiệm có tổng khách hàng phục vụ lớn nhất: bằng cách thực hiện việc chồng lớp (overlay) với cơ sở dữ liệu không gian vị trí khách hàng
Hình 3.8 cho thấy việc hiển thị dữ liệu không gian trên Form Ánh xạ bản đồ được thực hiện thông qua các phần mềm GIS tích hợp, cho phép đọc nghiệm tương ứng với các hình phủ của các BTS và thể hiện chúng lên bản đồ một cách trực quan.