MÔ HÌNH TOÁN HỌC VÀ SO SÁNH 4 THUẬT TOÁN Heuristic
ĐỐI VỚI QUY HOẠCH MẠNG VÔ TUYẾN WCDMA
I- GIỚI THIỆU
WCDMA: hay còn lại là đa truy nhập phân chia theo mã băng rộng
(WCDMA 5MHz), mà ở đó mỗi kênh được cung cấp một cặp tần số và một mã duy
nhất. Phương thức đa truy nhập này dựa trên nguyên lý trải phổ.
Các đặc tính của mạng WCDMA
- Điều khiển công suất
- Chuyển giao mềm
- Mối liên hệ giữa vùng phủ sóng và năng lực mạng
- ….
Đối với công nghệ CDMA khi thực hiện việc quy hoạch hệ thống mạng viễn thông
cần chú ý những đặc điểm sau đây:
- Hiệu năng của hệ thống mạng có thể đáp ứng lưu lượng thuê bao và giảm
thiểu ảnh hưởng trễ với chi phí nhỏ nhất
- Khả năng bao phủ của hệ thống mạng, duy trì các dịch vụ chất lượng cao
- Về chất lượng QoS qua hệ thống mạng
Trong phần bài viết này, ta sẽ trình bày một mô hình toán học mà nó có các
đặc tính của mạng vô tuyến WCDMA. Đồng thời, trình bày và so sánh đặc tính của
4 thuật toán tối ưu hóa dựa trên giải thuật meta-heuristics mà có thể sử dụng để tìm
kiếm các giải pháp để quy hoạch và tối ưu hóa mạng vô tuyến WCDMA. Nhiệm vụ
của thuật toán tối ưu hóa hệ thống trong bài báo là vấn đề tìm ra được tập các trạm
site với hàm chi phí đạt được nhỏ nhất
II- HIỆN TRẠNG CỦA VẤN ĐỀ
2.1 Những thành tựu đạt được
Trong các bài báo nghiên cứu , các tác giả thường tập trung đi nghiên cứu mô
hình hiệu năng cho hệ thống mạng dựa trên nhu cầu khách hàng, khả năng đáp ứng
lưu lượng người dùng (cải thiện tốc độ downlink; uplink) công suất downlink/
uplink cho các thiết bị đầu cuối và cả bài toán về diện tích bao phủ trong hệ thống
mạng dựa trên thuật toán meta-heuristics
VD Thuật toán GA để tìm hiểu không gian thiết kế,tối ưu QoS đối với chuẩn IEEE

rộng và triển khai nhanh chóng. Vấn đề quy hoạch đã làm cho mạng WCDMA
triển khai và mở rộng thành công được. Trong hoạt động của nó, mạng vô tuyến
WCDMA phải chịu sự tối ưu hóa thường xuyên tùy thuộc vào các yêu cầu thay đổi
và các mô hình dịch vụ kinh doanh mới, nó giống như là quy hoạch nhưng có loại
trừ những vị trí site đã được cố định từ trước. Một mạng vô tuyến WCDMA được
quy hoạch và tối ưu hóa tốt có thể tăng thêm khoảng 30% dung lượng so với cùng
một chi phí xây dựng cơ sở hạ tầng cho một mạng cùng cấu trúc. Do đó, quy hoạch
và tối ưu hóa mạng là một vai trò sống còn - cực kỳ quan trọng đối với việc triển
khai và bảo dưỡng mạng vô tuyến WCDMA.
Việc quy hoạch và tối ưu hóa mạng tế bào không còn là vấn đề mới, nhưng
với sự phát triển của công nghệ mới, những vấn đề này lại trở nên nổi bật. Nó đã
chứng minh rằng việc quy hoạch mạng vô tuyến WCDMA là một vấn đề rất khó
Trần Thị Minh Huệ - K17DTVT
2
khăn (NP-hard problem). Vì thế, meta-heuristics được đánh giá cao hơn bất kỳ một
phương pháp tối ưu hóa chính xác nào và phù hợp đối với việc tối ưu hóa mạng
WCDMA.
Tác giả trình bày một mô hình toán học mà nó có các đặc tính của mạng vô
tuyến WCDMA. Đồng thời, trình bày và so sánh đặc tính của 4 thuật toán tối ưu hóa
dựa trên meta-heuristics mà có thể sử dụng để tìm ra các giải pháp để quy hoạch và
tối ưu hóa mạng vô tuyến WCDMA.
3.2 Nội dung phương pháp
3.2.1 Mô hình quy hoạch tổng thể cho vấn đề quy hoạch mạng vô tuyến WCDMA:
Khi hệ thống được chia theo chiều, thì toàn bộ khu vực sẽ được chia theo λ
vùng, và mỗi vùng i (i = 1… λ) sẽ chứa n
i
vị trí có thế lắp đặt BS (vị trí ứng cử),
giả sử tập ứng cử là S {1, …, p},
1
i

ij
là các thông số truyền
nhận của kết nối Up-Link và Down-Link giữa trạm BSi và MSj tương ứng. Độ lợi
thu phát cũng được ước lượng theo các kiểu kinh nghiệm truyền nhận như là mô
hình Hata hoặc theo mô hình dò theo đường quyết định ( deterministic ray tracing)
là chính xác hơn nhưng phức tạp trong kỹ thuật tính toán hơn.
Giả thiết rằng tín hiệu CPICH (Common Pilot Channel - Kênh thử nghiệm
chung) có thể dò được khi và chỉ khi E
c
I
0
(energy per chip to interference density
ratio – tỉ số năng lượng trên mật độ nhiễu trong một đơn vị nhỏ ) là không bé hơn
giá trị ngưỡng đưa ra γ
0
. Biến nhị phân t
ij
thể hiện cho việc nhận dạng được tín hiệu
CPICH được tính bởi điều kiện sau:
Trần Thị Minh Huệ - K17DTVT
3
- t
ij
= 1 khi (E
c
/I
0
)
CPICH
ij

ijk
như sau:
- s
ijk
= 1 Nếu MSj là trong SHO với BSi và BSk, BSi là trạm tốt nhất
- b
ij
= 0 Ngược lại.
Với i, k∈S, j∈M
Và cũng định nghĩa si là:
- s
i
= 1 MSj là trong SHO Với i∈M
- b
ij
= 0 Ngược lại.
Có bốn loại độ lợi SHO: SHO thu được qua công suất được nhận trên đường
uplink, SHO thu được qua APR trên đường uplink, SHO thu được qua dự trữ pha
đinh (headroom) trên đường uplink, và SHO thu được qua công suất truyền dẫn trên
đường downlink. Tất cả các độ lợi SHO là hàm số của tốc độ di chuyển của MS và
độ sai khác của mức công suất nhận được giữa BSi và BSk, các hàm số đó lấy được
từ các chương trình mô phỏng.
Đối với việc tối ưu và quy hoạch mạng vô tuyến WCDMA trên thực tế thì
cần đưa ra các điều kiện bắt buộc sau:
1, Để được phục vụ, MS cần phải nhận được ít nhất 1 tín hiệu CPICH với E
c
I
0
vượt quá ngưỡng giá trị của tín hiệu CPICH dò được.
2, Mỗi MS được phục vụ phải có 1 BS tốt nhất, cái mà có tín hiệu CPICH nhận

 
+ − + −
 
 ÷
 ÷
 
 
 
 
∑
∑
n
covered
là số lượng của các MSs được phục vụ bởi mạng, T
total
là toàn bộ các
lưu lượng yêu cầu, T
severed
là lưu lượng được cấp bởi mạng, λ
1,
λ
2
, λ
3
trọng số được
kết hợp cho chi phí lắp đặt thông thường, tỉ lệ phần trăm của các MSs không được
phủ sóng và tỉ lệ phần trăm các MSs không được kết nối do lưu lượng. Một số các
chỉ số vận hành khác như là hệ số tải trên đường uplink và downlink, công suất hoa
tiêu, chất lượng của tín hiệu nhận và vùng SHO, …. có thể cũng được đưa vào trong
thành phần trong hàm chi phí với các trọng số thích hợp (proper weighting factor),

thông số giới hạn cho việc tối ưu quá trình. SA đã được triển khai với cách tiếp cận
đã được đề xuất trong thời gian gần đây, được gọi là quá trình tiến hóa SA (ESA),
trong khi đó thuật toán GA và TS được giữ gần với tiêu chuẩn hơn.
Thuật toán greedy (Greedy Algorithm) thường được sử dụng để thực hiện tạo
ra đặc tính chuẩn cho các phương pháp thực nghiệm khác. thuật toán tìm kiếm leo
đồi với việc sử dụng cấu trúc lân cận xung quanh vùng nghiên cứu. Với ý tưởng tìm
kiếm một giải pháp trạng thái tốt hơn, nếu trạng thái hiệu chỉnh là tốt hơn so với
trạng thái gốc, quá trình thay đổi sẽ được chấp nhận. Nếu không thì nó sẽ được loại
bỏ và chuyển tới trạng thái lân cận khác. Bằng cách sử dụng các thuật toán đơn giản,
chúng ta kiểm tra mức độ bé nhất của quá trình tối ưu hóa thực hiện được, nó sẽ là
tiêu chuẩn cho các phương pháp thực nghiệm khác, và sẽ chặt chẽ hơn đối với các
vấn đề đặc biệt.
IV-NGHIÊN CỨU THỰC NGHIỆM
4.1, Cấu hình mô phỏng:
Dựa trên mô hình toán học trên, chúng ta đã phát triển một chương trình mô
phỏng tĩnh cho WCDMA để đánh giá sự vận hành của các thuật toán tối ưu thực
nghiệm khác nhau.
Một ví dụ cho việc lắp đặt một mạng WCDMA (hình 1). Chúng ta xem một
vùng dịch vụ là một hình chữ nhật 18km x 16km chứa K = 19 trạm BS với 3 anten
sector, nghĩa là có tổng cộng 57 cells. Tất cả 3 anten sector được lắp đặt từ góc
phương vị 0
0
bù từ phía Bắc và nghiêng xuống 0
0
. Với mỗi BS, các site ứng cử ni =
n = 5 được giữ giá trị và một site sẽ được lựa chọn để lắp BS. q=3600 nút lưu lượng
(traffic nodes - TN) được phân bố đồng đều trong vùng và tất cả các TN có hệ số
lưu lượng hoạt động 1.0
Trần Thị Minh Huệ - K17DTVT
6

200
Xác suất thay đổi GA - GA mutation probability
0.9
Xác suất xuyên chéo GA - GA crossover probability
0.1
Kích thước tập hợp ESA - ESA population size
1
Số lặp lại cho mỗi toán tử SA trong ESA - Iteration
number for each SA operator in ESA
200
Trần Thị Minh Huệ - K17DTVT
7
Số lần lặp lại bên trong cho ESA - Number of inner
iterations for ESA
15
Kích thước danh mục TS Tabu / kích thước danh
muck lân cận - TS Tabu list size/Neighbourhood list
size
13
4.3. Kết quả thực nghiệm:
Hình vẽ sau thể hiện kết quả thu được từ 6000 lần thí nghiệm (ns=6000), đó
là một giá trị rất nhỏ của sự lặp lại đối với thuật toán tìm kiếm thực nghiệm
(heuristic search algorithms) để đưa ra giải pháp hợp lý. Nó tương đương với quá
trình tìm kiếm nhanh. Mỗi thí nghiệm này được làm lặp lại tới 100 lần với cùng điều
kiện như nhau. Do đó với 100 kết quả tối ưu thu được với mỗi thuật toán cho các
mạng riêng biệt và cụ thể. Tất cả các kết quả đã được lọc và hiển thị theo giá trị tăng
dần. Do đó kết quả tốt nhất sẽ được thể hiện trước, sau đó sẽ đến các kết quả khác,
và mọi các kết quả không mong đợi cũng sẽ được xuất hiện cuối cùng trên hình vẽ
như sau:
Kết quả: