Tối ưu hoá gán kênh cố định trong mạng di động tế bào

1 TỐI ƯU HOÁ GÁN KÊNH CỐ ĐỊNH TRONG MẠNG DI ĐỘNG TẾ BÀO Trần Anh Tấn - Đỗ Quốc Trinh 1. Giới thiệu Nhu cầu các dịch vụ di động của mạng tế bào đang tăng với tốc độ rất cao trong mỗi năm và tại những vùng đô thị nhu cầu này đã vượt quá dung lượng khả dụng. Nhiều kỹ thuật khác nhau được sử dụng để tăng dung lượng hệ thống bao gồm: chia nhỏ tế bào, chỉ định phổ tần mới, các phương pháp đa truy cập mới (TDMA, CDMA) và gán kênh động. Đối với hệ thống tế bào, dung lượng của một hệ thống phụ thuộc vào hiệu quả của chiến lược gán kênh sử dụng. Mặc dù có rất nhiều đề xuất đối với chiến lược gán kênh động, nhưng tất cả các hệ thống tế bào hiện có đều sử dụng gán kênh cố định vì hiệu quả chi phí của nó và chất lượng dịch vụ có thể dự đoán trước. Trong bài báo này, chúng ta quan tâm tới ý tưởng cơ bản của việc sắp xếp các tế bào thành danh sách có thứ tự, sau đó thực hiện gán kênh. Tổng cộng có 6 thuật toán gán kênh mới, cụ thể là các thuật toán F/CR, F/DR, R/CR, R/DR, FR/CR và FR/DR đã được đề xuất. 2. Xây dựng bài toán Ba điều kiện bắt buộc thường xuyên được lưu ý trong vấn đề gán kênh: - Hạn chế xuyên nhiễu đồng kênh: một kênh được gán cho một tế bào không thể tái sử dụng trong các tế bào lân cận. Những tế bào này nằm trong phạm vi xuyên nhiễu đồng kênh. - Hạn chế xuyên nhiễu kênh lân cận: các kênh được gán cho các tế bào lân cận phải duy trì một sự phân cách cực tiểu là a kênh. - Hạn chế xuyên nhiễu kênh cùng tế bào: các kênh được gán cho cùng một tế bào phải duy trì sự phân cách cực tiểu là s kênh. Với hệ thống tế bào gồm N tế bào và ma trận tương thích kênh N x N, C = [cij] có thể được sử dụng để biểu diễn 3 loại ràng buộc, cij biểu thị của sự phân cách kênh tối thiểu giữa các kênh được gán cho tế bào i và tế bào j. Rất dễ nhận thấy rằng cij= 0 có nghĩa là một kênh được gán cho tế bào i có thể được tái sử dụng tại tế bào j. cij = s có nghĩa là hạn chế xuyên nhiễu kênh cùng trạm là s kênh. cij = a có nghĩa là hạn chế xuyên nhiễu kênh lân cận bằng a kênh. Trên thực tế, ma trận tương thích thường nhận được bằng việc đo hệ thống thực không có một cấu trúc lục giác đều lí tưởng. Giả sử vector M = (m1, m2… mN) biểu thị các yêu cầu kênh của mạng N tế bào. Giả sử một tổ hợp kênh tần số được xếp hạng bởi một tập số nguyên dương {1, 2, 3…} theo tần số sóng mang của chúng (hình 1). Giả sử fik là kênh được gán cho cuộc gọi thứ k trong tế bào i. Việc gán kênh có thể nhận được trong [1] là sự tập hợp của các số nguyên F = (fik), với i = 1, 2, …, N và k = 1, 2,… mi , sao cho: |fik - fjl| ≥ cij với mọi i, j, k và l (ngoại trừ i = j và k = l). Một thuật toán gán kênh hiệu quả sẽ cho gán kênh F* với N(F*) = max i, k, fik càng nhỏ càng tốt. N(F*) được hiểu như là phạm vi tần số của việc gán kênh. Kênh 1 2 3 4 5 . . . . . . x Mhz y Mhz Phổ tần 2 Hình 1. Gán kênh cố định trong hệ thống di động tế bào 3. Những quy tắc kinh nghiệm cơ bản 3.1. Hai phương pháp sắp xếp tế bào Gọi di là số đo độ khó gán kênh cho tế bào i. Trong [2], di được định nghĩa: di = ∑Nj=1 mj cij - cii 1 ≤ i ≤ N (1) nếu mi ≠ 0; ngoài ra, di = 0. Vì số hạng cii ở vế phải của phương trình (1) là như nhau đối với tất cả các tế bào, ta có thể bỏ nó để có dạng đơn giản hơn: di = ∑Nj=1 mj cij 1 ≤ i ≤ N (2) 3.2. Hai chiến lược gán kênh Chiến lược vét cạn tần số (F) và chiến lược vét cạn yêu cầu (R) [3] có thể sử dụng để sắp xếp các kênh cho các tế bào. Trong chiến lược vét cạn tần số, bắt đầu với tế bào đầu tiên trong trật tự danh sách, mỗi tế bào với yêu cầu kênh không phù hợp nào đó được gán một kênh với hạng thấp nhất (tất cả các kênh được xếp hạng theo các tần số sóng mang của chúng) và phù hợp với tất cả việc gán kênh trước. Trong chiến lược vét cạn yêu cầu, kênh 1 được gán cho tế bào đầu tiên trong trật tự danh sách với yêu cầu kênh không phù hợp nào đó. Sau đó thử kênh như vậy cho tế bào kế tiếp trong danh sách có yêu cầu kênh không phù hợp. Tiếp tục việc thử này cho đến khi kênh này không thể được chấp nhận bởi tế bào nào nữa. Tiếp sau đó làm thủ tục tương tự để gán kênh 2. Lặp lại thủ tục này cho đến khi tất cả yêu cầu kênh được thoả mãn. 4. Thuật toán gán kênh với việc sắp xếp lại tế bào * Thuật toán F/CR hay F/DR Input: C = [ cij] và M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; 2. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 3. Sắp xếp tế bào thành danh sách có trật tự sử dụng thứ tự màu nút hay thứ tự cấp bậc nút; 4. Nếu bậc của tế bào đầu tiên trong danh sách di ≠ 0 tìm kênh g với hạng thấp nhất sao cho việc gán kênh g cho tế bào i là phù hợp với tất cả việc gán kênh trước. m’i = m’i – 1 , k = mi – m’i và fik = g; nhảy đến bước 2; 5. Ngược lại N(F*) = maxi,kfik và EXIT; * Thuật toán R/CR hay R/DR Input: C = [ cij] và M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; 2. f = 1; 3. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 4. Sắp xếp các tế bào thành danh sách thứ tự sử dụng phương pháp thứ tự màu nút hay phương pháp thứ tự bậc nút. 5. Tìm i tế bào thứ nhất trong danh sách sao cho gán kênh f cho tế bào i là phù hợp với tất cả việc gán trước. 3 6. Nếu tế bào i tìm được nếu di ≠ 0 m’i = m’i – 1, k = mi – m’i và fik = f; nhảy đến bước 3; ngược lại N(F*) = maxi,kfik và EXIT; 7. Ngược lại f = f + 1; nhảy đến bước 4. 5. Tối ưu việc gán kênh tại các điểm nóng 5.1. Chiến lược vét cạn tần số (F) và chiến lược vét cạn yêu cầu (R). - Nhận xét đầu tiên là khi sử dụng chiến lược R để gán kênh, số các tế bào đồng kênh của kênh được gán có xu hướng lớn hơn so với việc sử dụng chiến lược F. Không mất tính tổng quát, giả sử hạn chế xuyên nhiễu kênh cùng trạm giá trị lớn hơn hay bằng tổn hao của việc hạn chế xuyên nhiễu kênh lân cận, tức là s ≥ a. Khi gán kênh f cho một tế bào sử dụng chiến lược R, việc gán kênh sẽ thành công nếu việc hạn chế xuyên nhiễu đã nêu ra bởi việc gán kênh đó trước từ (f – s + 1) đến f không bị vi phạm. Chú ý rằng kênh có hạng cao nhất được gán là kênh hiện thời được gán, tức là kênh f. - Nhận xét thứ hai là không như chiến lược F, khi sử dụng chiến lược R kênh được gán không bám chính xác theo độ khó của việc gán các tế bào riêng lẻ. Giả thiết chiến lược R được sử dụng để gán kênh f cho hệ thống. Nếu không có ràng buộc nào bị vi phạm, tế bào đầu tiên trong danh sách được sắp xếp sẽ nhận kênh f. Sau đó kênh f được gán cho tất cả các tế bào có thể trong danh sách trước khi xem xét kênh f + 1. Tuy nhiên, việc gán tiếp kênh f cho các tế bào còn lại không bám chính xác theo độ khó của việc gán. 5.2. Chiến lược FR Để kết hợp những ưu điểm của chiến lược R và F, chiến lược FR đã được đề xuất. Đó là một chiến lược gán kênh 2 mức bao gồm gán kênh toàn bộ sử dụng chiến lược R và gán kênh cục bộ sử dụng chiến lược F. Việc gán kênh toàn bộ sẽ nhận dạng các điểm nóng và sẽ sử dụng chiến lược R để tối đa hoá các tế bào đồng kênh. Việc gán cục bộ tập trung gán các kênh cho điểm nóng đã được xác nhận và để sắp xếp các kênh này một cách chặt chẽ sử dụng chiến lược F. Khi kênh f được gán cho tế bào i (tế bào đầu tiên trong danh sách đã được sắp xếp) bởi gán toàn bộ, một điểm nóng có tâm là tế bào i (hoặc điểm nóng i) được xác nhận. Để đơn giản hoá tiến trình của việc xác định các tế bào với các yêu cầu kênh tương đối cao, chúng ta định nghĩa một tham số Y. Giả sử tất cả các tế bào xuyên nhiễu của tế bào i tạo thành một danh sách được sắp xếp với độ khó gán kênh giảm dần. Y tế bào đầu tiên trong danh sách được sắp xếp, hay tế bào điểm nóng, được chọn ra để tham gia gán cục bộ tiếp sau. Giá trị của Y có thể được thay đổi để đạt được những chất lượng khác nhau. Trong gán kênh cục bộ, mỗi tế bào điểm nóng được phép nhận nhiều nhất là một kênh và hạng của kênh đó phải nhỏ hơn hoặc bằng f + X , với X là tham số nguyên khác được tạo ra/ điều chỉnh. Trong thực tế, không thể tìm được kênh với hạng nhỏ hơn hay bằng f (vì gán kênh toàn bộ sử dụng chiến lược R) và do vậy, một kênh chỉ có thể được chọn từ dãy f + 1 đến f + X trong gán cục bộ. Mục đích của việc thiết lập giới hạn f + X là để cực tiểu hoá xuyên nhiễu sẽ được tạo ra bởi các kênh được gán một cách cục bộ đối với việc gán kênh tiếp theo. Khi việc gán kênh cục bộ được hoàn thành, việc gán kênh toàn bộ được bắt đầu lại để gán kênh f đối với tế bào có thể tiếp theo trong danh sách đã sắp xếp (sử dụng chiến lược R). Nếu không có một tế bào nào nữa có thể chấp nhận kênh f, thì tiếp tục với kênh f + 1. Tiếp tục thủ tục này cho đến khi tất cả các yêu cầu kênh được thoả mãn. Việc kết hợp chiến lược FR với 2 phương pháp sắp xếp lại tế bào, có hai thuật toán gán kênh FR/CR và FR/DR đã đạt được. Lưu ý rằng khi sắp xếp lại tế bào được sử dụng, các 4 tế bào được sắp xếp lại sau mỗi lần gán kênh bất chấp đó là gán kênh toàn bộ hay gán kênh cục bộ. Tiếp theo, chúng ta sẽ tóm tắt các thuật toán FR/CR và FR/DR như sau: Gán toàn bộ Input: C = [ cij] và M = (m1, m2, …, mN) Output: N(F*) 1. For i = 1 to N do m’i = mi; f = 1; 2. For i = 1 to N do if m’i = 0, di = 0 else di = ∑Nj=1 m’j cij ; 3. Sắp xếp các tế bào thành danh sách có thứ tự sử dụng thứ tự màu nút hoặc thứ tự bậc nút. 4. Tìm tế bào thứ nhất i trong danh sách, sao cho việc gán kênh f cho tế bào i là phù hợp với tất cả việc gán trước. 5. Nếu tế bào i tìm được nếu di ≠ 0 m’i = m’i – 1, k = mi – m’i và fik = f; nhảy đến bước 1 của gán cục bộ; ngược lại N(F*) = maxi,kfik và EXIT; 6. Ngược lại f = f + 1 và nhảy đến bước 4 Gán cục bộ 1. counter = 1 2. Khi counter ≤ Y thực hiện cho mỗi tế bào j với cij ≥ 1 thực hiện nếu m’j = 0, dj = 0 ; else dj = ∑Nk=1 m’k cjk ; sắp xếp các tế bào với cij ≥ 1 trong danh sách có thứ tự sử dụng thứ tự màu nút hoặc thứ tự bậc nút; nếu bậc của tế bào thứ nhất trong danh sách dj ≠ 0, tìm kênh g với hạng nhỏ nhất sao cho gán g cho tế bào j là phù hợp với tất cả việc gán trước đó và f < g ≤ f + X nếu g tìm được m’j = m’j – 1, k = mj - m’j và fik = g counter = counter + 1 ngược lại nhảy đến bước 2 của việc gán toàn bộ. 3. Nhảy đến bước 4 của gán toàn bộ. Giả thiết giá trị của X và Y là cố định, giả sử kênh f được gán cho tế bào k bởi việc gán toàn bộ. Xác định giá trị X và Y thích hợp được tóm tắt ở dưới đây. * Nếu X = 0, gán cục bộ được bỏ qua. * Nếu X = 1, chỉ các tế bào với ckj = 1 có thể tham gia vào việc gán cục bộ. * Nếu X ≤ s – a, việc gán kênh f tiếp theo đến phần còn lại hệ thống sẽ không bị ảnh hưởng bởi xuyên nhiễu được gây ra cho gán kênh cục bộ hiện thời. * Nếu X ≤ s + 1, mọi xuyên nhiễu của tế bào k có thể đạt tại một kênh trong gán cục bộ. * 0 ≤ Y ≤ tổng số các kênh xuyên nhiễu của tế bào k * Nếu Y = 0, việc gán cục bộ được bỏ qua. * Y cần nhận giá trị mà có thể so sánh được với số tế bào điểm nóng trong điểm nóng được tập trung tại tế bào k. 6. Đánh giá chất lượng 6.1. Chất lượng của thuật toán F/CR, F/DR, R/CR và R/DR Đối với cấu hình mạng khác nhau, phạm vi tần số có được nhờ sử dụng các thuật toán F/CR, F/DR, R/CR và R/DR. Từ kết quả thực nghiệm chúng ta có thể thấy các thuật toán 5 F/CR luôn thực hiện tốt hơn F/DR. Điều này chỉ ra thứ tự tế bào màu nút là hiệu quả hơn so với thứ tự bậc nút. 6.2. Ảnh hưởng của X và Y đối với chất lượng của các thuật toán FR/CR và FR/DR Tiếp theo chúng ta nghiên cứu chất lượng của các thuật toán FR/CR và FR/DR với những giá trị khác của X và Y. Xét hệ thống với cấu hình (7, 2, 5) và các yêu cầu kênh trường hợp I. Kết quả phạm vi tần số trong khoảng 1 ≤ X ≤ 5 và 1 ≤ Y ≤ 3: khi X = 3 và Y = 2, cả hai thuật toán đều cho phạm vi tần số tối thiểu là 428 và 438. Kết quả tốt nhất đạt được bởi các thuật toán trong [2] chỉ là 447 và trong [4] chỉ là 446. 6.3. Chất lượng của các thuật toán FR/CR và FR/DR Với 0 ≤ X ≤ 5 và 1 ≤ Y ≤ 3. Phạm vi tối thiểu tìm được bởi các thuật toán FR/CR và FR/DR, có thể thấy rằng thuật toán FR/CR luôn luôn tốt hơn các thuật toán trong [2]. Bên cạnh đó, nó tạo ra một phạm vi nhỏ hơn thuật toán FR/DR ngoại trừ đối với trường hợp I với (7, 2, 3) và trường hợp II với (7, 2, 5). So sánh thuật toán FR/CR với các thuật toán F/CR và R/CR thì FR/CR cho giá trị phạm vi nhỏ nhất trong các trường hợp, ngoại trừ đối với trường hợp II với (12, 2, 7) nhưng sự khác nhau này chỉ là một kênh. 7. Kết luận Hai vấn đề với các thuật toán gán kênh kinh nghiệm thông thường đã được xác định trong bài báo này. Sắp xếp lại tế bào và chiến lược gán kênh tập trung vào các điểm nóng được đề xuất sau đó để giải quyết cả hai vấn đề. Kết quả là 6 thuật toán gán kênh mới là những sự kết hợp của 3 chiến lược gán kênh và 2 phương pháp sắp xếp lại tế bào đã được đề cập và nghiên cứu. Xác định giá trị tối ưu cho các tham số X và Y trong các thuật toán FR/CR và FR/DR là rất quan trọng. Trong bài báo này, chúng ta chỉ nghiên cứu trường hợp X và Y là cố định. Cần phải nghiên cứu sâu hơn nữa việc làm thế nào để cải thiện chất lượng bởi điều chỉnh linh hoạt giá trị X và Y trong việc đáp ứng những yêu cầu kênh còn lại của các tế bào riêng rẽ. Các từ viết tắt: F: frequency exhaustive strategy (chiến lược vét cạn tần số) R: requirement exhaustive strategy (chiến lược vét cạn yêu cầu) CR: node-color re-ordering (thứ tự lại màu nút) DR: node-degree re-ordering (thứ tự lại cấp bậc nút) Tài liệu tham khảo [1]. A. GAMST AND W. RAVE, On frequency assignment in mobile automatic telephone systems, IEEE Proc. GLOBECOM ’82, pp .309 –315, 1982. [2]. K.N. Sivarajan, R.J. McEliece, and J.W. Ketchum, Channel assigment in cellular radio, IEEE Veh. Tech. Conf, VTC’ 89, pp .846-850, 1989. [3]. J.A ZOELLNER and C.A. BEALL, A breakthrough in spectrum conserving frequency assignment technology, IEEE Trans. Electromagn. Comput, vol.EMC-19, pp.313-319, Aug, 1997. [4]. X.R CAO and J.C.I. CHUANG, A set theory approach to the channel assignment problem, Proc, IEEE Globecom, pp. 1647-1651, San Francisco, Nov.1994.