Luận văn Tối ưu hóa gán kênh cố định cho các mạng di động tế bào

bộ giáo dục và đào tạo bộ quốc phòng học viện kỹ thuật quân sự Trần anh tấn tối −u hoá gán kênh cố định cho các mạng di động tế bào luận văn thạc sĩ Kỹ thuật Hà Nội- 2005 bộ giáo dục và đào tạo bộ quốc phòng học viện kỹ thuật quân sự Trần anh tấn tối −u hoá gán kênh cố định cho các mạng di động tế bào Chuyên ngành: Kỹ thuật Vô tuyến điện tử và thông tin liên lạc M∙ số: 2.02.03 luận văn thạc sĩ Kỹ Thuật ng−ời h−ớng dẫn khoa học: TS Đỗ quốc trinh Hà Nội - 2005 bộ giáo dục và đào tạo bộ quốc phòng học viện kỹ thuật quân sự luận văn thạc sĩ kỹ thuật Tên đề tài: Tối −u hoá gán kênh cố định cho các mạng di động tế bào Chuyên ngành: Kỹ thuật Vô tuyến điện tử và thông tin liên lạc Mã số: 2.02.03 Ngày giao đề tài luận văn: 21 - 10 - 2004 Ngày hoàn thành luận văn: 16 - 5 - 2005 Ng−ời thực hiện: Họ và tên : Trần Anh Tấn Lớp: Cao học KT VTĐT và TTLL Khoá:15 Hệ đào tạo: Tập trung Cán bộ h−ớng dẫn: Họ và tên: Đỗ Quốc Trinh Cấp bậc: Th−ợng tá Học hàm, học vị: Tiến sỹ Đơn vị công tác: Học viện KTQS Hà Nội - 2005 Danh mục các ký hiệu, các chữ viết tắt BER Bit Error Ratio Tỷ lệ lỗi bit BS Base Station Trạm cơ sở CDMA Code Division Multiple Access Đa truy nhập phân chia theo mã CR Node-Color Re-ordering Thứ tự lại màu nút CSI Channel State Information Thông tin trạng thái kênh DCA Dynamic Channel Assignment Gán kênh động DPA Dynamic Packet Assignment Gán gói động DR Node-Degree Re-ordering Thứ tự lại cấp độ nút F Frequency Exhaustive Strategy Chiến l−ợc vét cạn tần số FCA Fixed Channel Assignment Gán kênh cố định FDD Frequency Division Duplexing Song công phân chia theo tần số FEC Forward Error Correction Sửa lỗi h−ớng đi FFT Fast Fourier Transform Biến đổi Fourier nhanh GA Genetic Algorithms Thuật toán di truyền LA Link Adaptation Thích nghi đ−ờng truyền LB Lower Bound Cận d−ới LOS Line Of Sight Tầm nhìn thẳng MS Mobile Station Máy di động NP Network Performance Chất l−ợng mạng OFDM Orthogonal Frequency Division Multiplexing Ghép kênh phân chia theo tần số trực giao PN Pseudorandom Noise Tạp âm giả ngẫu nhiên QAM Quadrature Amplitude Modulation Điều chế biên độ cầu ph−ơng QoS Quality of Service Chất l−ợng dịch vụ R Requirement Exhaustive Strategy Chiến l−ợc vét cạn yêu cầu RF Radio Frequency Tần số vô tuyến SA Simulated Annealing Kỹ thuật ủ mô phỏng SMK K.N. Sivarajan, R.J. McEliece and J.W. Ketchum Ba tác giả trong [26] SNR Signal - to - Noise Ratio Tỷ số tín hiệu trên tạp âm SINR Signal - to - Interference Noise Ratio Tỷ số tín hiệu trên tạp âm xuyên nhiễu SIR Signal - to - Interference Ratio Tỷ số tín hiệu trên xuyên nhiễu TDD Time Division Duplexing Song công phân chia theo thời gian TDMA Time Division Multiple Access Đa truy nhập phân chia theo thời gian UMTS Universal Mobile Telecommunications Service Dịch vụ viễn thông di động toàn cầu UTRA UMTS Terrestrial Radio Access Truy nhập vô tuyến mặt đất UMTS Mục lục Trang Danh mục các ký hiệu, các chữ viết tắt I Mục lục IV Danh mục các bảng VIII Danh mục các hình vẽ, đồ thị IX Mở đầu 1 Ch−ơng 1: Giới thiệu chung 3 1.1 Khái niệm tế bào 3 1.1.1 Tái sử dụng kênh trong các mạng tế bào 5 1.1.2 Sự chia tách tế bào 9 1.1.3 Chuyển giao 10 1.2. Gán kênh 11 Ch−ơng 2: Các chiến l−ợc gán kênh 13 2.1 Gán kênh cố định cho các mạng tế bào 13 2.1.1 Tỷ số S/I mục tiêu 15 2.1.2 Khoảng cách sử dụng lại tần số 18 2.1.3 Sắp xếp tế bào và các mẫu gán kênh 19 2.2 Gán kênh động 23 2.2.1 DCA tập trung 25 2.2.2 DCA không tập trung 25 2.2.3 Chia tách kênh 28 2.2.4. Gán gói động 31 2.2.5 DCA đối với các mạng UTRA-TDD 32 2.3 Tối −u hoá gán kênh trong các mạng tế bào 33 2.3.1 Ph−ơng pháp hạ xuống dốc nhất 35 2.3.2 Ph−ơng pháp ủ mô phỏng 35 2.3.3 Ph−ơng pháp thuật toán di truyền 37 2.3.4 Gán kênh trong các hệ thống W- CDMA 37 2.4 Dung l−ợng mạng tế bào và các ph−ơng pháp nâng cao dung l−ợng 38 2.4.1 Anten thích nghi 39 2.4.2 Phát hiện đồng thời 40 2.4.3 Thích nghi đ−ờng truyền 41 2.5 Kết luận 42 Ch−ơng 3: Tối −u hoá gán kênh cố định trong mạng di động tế bào 44 3.1 Giới thiệu 44 3.2 Xây dựng bài toán 47 3.3 Những quy tắc kinh nghiệm cơ bản 50 3.3.1 Hai ph−ơng pháp sắp xếp tế bào 50 3.3.2 Hai chiến l−ợc gán kênh 51 3.4 Gán kênh với việc sắp xếp lại tế bào 51 3.4.1 Bốn thuật toán gán kênh 51 3.4.2 Độ phức tạp 54 3.4.3 Ví dụ 54 3.5 Tối −u việc gán kênh tại các điểm nóng 57 3.5.1 Chiến l−ợc F và chiến l−ợc R 57 3.5.2 Chiến l−ợc FR 59 3.6 Đánh giá chất l−ợng 63 3.6.1 Chất l−ợng của thuật toán F/CR, F/DR, R/CR và R/DR 67 3.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 68 3.6.3 Chất l−ợng của các thuật toán FR/CR và FR/DR 68 3.7 Kết luận 69 Kết luận 70 Tài liệu tham khảo Danh mục các bảng Trang Bảng 3.1 Phạm vi tần số nhận đ−ợc bởi F/CR, F/DR, R/CR và R/DR 65 Bảng 3.2 Phạm vi tần số nhận đ−ợc bởi FR/CR và FR/DR với (7,2,5) và yêu cầu kênh tr−ờng hợp I 66 Bảng 3.3 Phạm vi tần số nhận đ−ợc bởi FR/CR và FR/DR với 0 ≤ X ≤ 5 và 1 ≤ Y ≤ 3 66 Danh mục các hình vẽ, đồ thị Trang Hình 1.1 Mạng tế bào lục giác 5 Hình 1.2 Sử dụng lại kênh 7 Hình 2.1. Cấu trúc mạng tế bào lục giác đều cơ bản 15 Hình 2.2. Phân bố xác suất suy giảm đối với mô hình pha-đinh phân bố Rice với hệ số k biến đổi 17 Hình 2.3 Xác suất mức tín hiệu pha-đinh chuẩn lôga 17 Hình 2.4 Sắp xếp băng tần số trong nhóm 7 tế bào và 3 sector trên một tế bào 22 Hình 2.5 Hiệu quả phổ tần của DCA lý t−ởng đ−ợc so sánh với CDMA 27 Hình 2.6 L−u đồ thuật toán chia tách kênh DCA 30 Hình 2.7 (a) Các đ−ờng tính toán xuyên nhiễu FDD (b) Các đ−ờng tính toán xuyên nhiễu TDD 32 Hình 3.1 Gán kênh cố định trong hệ thống di động tế bào 48 Hình 3.2 Kế hoạch gán kênh cho hệ thống 3 tế bào (a) Hệ thống 3 tế bào A, B, C (b) Không sắp xếp lại tế bào (c) Có sắp xếp lại tế bào và ph−ơng pháp quyết định thứ 55-56 nhất (d) Có sắp xếp lại tế bào và ph−ơng pháp quyết định thứ hai Hình 3.3 Mạng 21 tế bào với 2 tr−ờng hợp yêu cầu kênh (a) Yêu cầu kênh tr−ờng hợp I (b) Yêu cầu kênh tr−ờng hợp II 64 Mở đầu Trong hai thập kỷ qua, nhu cầu phát triển điện thoại vô tuyến và các dịch vụ dữ liệu vô tuyến ngày càng tăng mạnh. Nhu cầu các dịch vụ vô tuyến 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. Các kỹ thuật đ−ợc sử dụ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 với phổ tần cố định đ−ợc gán và sử dụng công nghệ ghép kênh cụ thể, 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, 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. Chính vì vậy, tối −u gán kênh cố định là vấn đề đ−ợc đặc biệt quan tâm đối với các mạng di động tế bào. ở n−ớc ta hiện nay, cùng với sự phát triển mạnh mẽ của mạng viễn thông, mạng thông tin di động tế bào đã trở thành một phần cơ sở hạ tầng thông tin không thể thiếu đ−ợc. Xuất phát từ lý do đó, tôi chọn đề tài: “Tối −u hoá gán kênh cố định cho các mạng di động tế bào” cho luận văn của mình. Bố cục luận văn gồm các phần sau: - Ch−ơng 1: Giới thiệu tổng quan về mạng tế bào, bao gồm các vấn đề cơ bản nh− tái sử dụng kênh, chia tách tế bào, chuyển giao và bài toán gán kênh cho mạng. - Ch−ơng 2: Giới thiệu các chiến l−ợc gán kênh và một số kỹ thuật nâng cao dung l−ợng mạng di động tế bào. Trong đó đi vào phân tích hai chiến l−ợc gán kênh là: gán kênh cố định (FCA) và gán kênh động (DCA). Các ph−ơng pháp tăng dung l−ợng mạng nh− anten thích nghi, phát hiện đồng thời, thích nghi đ−ờng truyền đ−ợc giới thiệu một cách cơ bản nhất. - Ch−ơng 3: Nghiên cứu ý 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. Xem xét bài toán gán kênh cố định, vấn đề gán kênh có sắp xếp lại tế bào, tối −u hoá gán kênh tại các điểm nóng. Tổng cộng có sáu thuật toán gán kênh, 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. Cuối cùng là đánh giá và kết luận về việc tối −u gán kênh cố định cho các mạng di động tế bào. Ch−ơng 1 Giới thiệu chung Thông tin vô tuyến tế bào đã trở thành một phần quan trọng của cơ sở hạ tầng thông tin. Mặt khác, phổ tần vô tuyến cấp phát cho hệ thống di động tế bào là hạn chế. Kết quả là, các tần số vô tuyến phải đ−ợc sử dụng một cách hiệu quả để thoả mãn những yêu cầu ngày càng cao. Trong luận văn này, chúng ta nghiên cứu vấn đề gán kênh: làm thế nào để gán các kênh vô tuyến cho các cuộc gọi trong một mạng thông tin di động tế bào. Sau đây là một số kiến thức cơ bản về các mạng tế bào và trình bày một cách khái quát vấn đề gán kênh. 1.1 Khái niệm tế bào Sự tăng tr−ởng mạnh mẽ của thông tin di động không thể đạt đ−ợc thành tựu nếu không sử dụng khái niệm tế bào. Tr−ớc đó, việc tiếp cận đối với thông tin di động là khá giống với truyền thanh vô tuyến hay truyền hình quảng bá: việc phủ sóng một khu vực đ−ợc cung cấp bằng cách lắp đặt một máy phát công suất cao trên điểm cao nhất của khu vực và truyền đi tín hiệu tới tới toàn bộ vùng phủ sóng. Phổ tần vô tuyến khả dụng đ−ợc chia tách thành nhiều kênh, mỗi kênh đ−ợc dành cho một ng−ời sử dụng cụ thể và tất cả ng−ời sử dụng liên kết tới cùng máy phát. Số ng−ời sử dụng bị giới hạn bởi số l−ợng kênh khả dụng, số l−ợng kênh khả dụng này bị khoá trong toàn bộ khu vực phủ sóng bởi một số l−ợng nhỏ các cuộc gọi. Ví dụ, một nhà cung cấp dịch vụ điện thoại vô tuyến phục vụ 10.000 khách hàng sẽ cần 10.000 kênh khác nhau để thực hiện, mặc dù chỉ có một phần nhỏ trong số chúng sẽ thực sự đ−ợc sử dụng tại thời điểm cho tr−ớc bất kỳ. Số kênh yêu cầu có thể giảm xuống bằng cách tái sử dụng các kênh vô tuyến về thời gian và không gian. Việc tái sử dụng về thời gian (còn đ−ợc gọi là trunking), có nghĩa là sử dụng các kênh nh− nhau cho các ng−ời dùng khác nhau tại các thời điểm khác nhau. Thiết bị đầu cuối sẽ đ−ợc gán một kênh chỉ khi nó yêu cầu cho cuộc gọi. Mặc dù trunking có thể sử dụng tài nguyên phổ tần vô tuyến một cách hiệu quả hơn, dung l−ợng hệ thống vẫn còn khá hạn chế. Số l−ợng các cuộc gọi đồng thời bị giới hạn bởi số l−ợng các kênh khả dụng. Vì phổ tần vô tuyến là một nguồn tài nguyên quý hiếm nên chính điều này giới hạn dung l−ợng hệ thống khá nhiều. Ví dụ, hệ thống di động tế bào Bell của thành phố New York trong những năm 1970 đã sử dụng điện thoại trunking, chỉ có thể hỗ trợ cho 12 cuộc gọi đồng thời. H−ớng tiếp cận khác của việc sử dụng các kênh vô tuyến một cách hiệu quả hơn là việc tái sử dụng kênh về không gian. Các ng−ời dùng có thể sử dụng cùng kênh tại cùng thời điểm trong khu vực địa lý không liền kề. Việc tái sử dụng các kênh về không gian là không thể trong một mạng quảng bá đ−ợc tập trung, nh−ng thay vào đó mạng đ−ợc cấu trúc lại theo một kiểu phân tán. Việc tái sử dụng kênh về không gian là một trong những khái niệm chủ yếu đ−ợc sử dụng bởi một mạng tế bào để đạt đ−ợc hiệu quả trong việc sử dụng tài nguyên phổ tần. Hai đặc điểm chính khác của các mạng tế bào là sự chia tách tế bào để giải quyết những yêu cầu tăng cao và chuyển giao của các cuộc gọi di chuyển từ tế bào này đến tế bào khác. Sau đây ta sẽ miêu tả chi tiết hơn mỗi đặc điểm này. Hình 1.1 Mạng tế bào lục giác 1.1.1 Tái sử dụng kênh trong các mạng tế bào Để đạt một hiệu quả cao hơn trong việc sử dụng kênh thông qua việc tái sử dụng kênh về không gian, vùng phục vụ đ−ợc chia thành nhiều khu liền kề. Một tế bào đ−ợc xem nh− là vùng phủ sóng t−ơng đ−ơng của một khu vực địa lý cụ thể. Mỗi tế bào đều có máy phát riêng đảm bảo thông tin vô tuyến với máy di động trong vùng nội hạt của nó và nối tới trung tâm bằng dây. Khái niệm tế bào đ−ợc miêu tả ở trên đ−ợc giới thiệu đầu tiên bởi MacDonald [21] sử dụng hình tế bào lục giác để biểu diễn một tế bào nh− trong hình 1.1. Lý do chọn cấu trúc tế bào lục giác là trong số tất cả các cấu trúc hình lục cùng có bán kính để có thể bao phủ một vùng mà không cần bất cứ khoảng trống nào, thì hình lục giác có diện tích lớn nhất. Không giống nh− các cách tiếp cận quảng bá truyền thống, ý t−ởng tế bào giải quyết vấn đề phủ sóng hoàn toàn khác. Thay vì bao phủ một vùng rộng với chỉ một máy phát công suất cao, một mạng tế bào cung cấp vùng phủ sóng bằng sử dụng rất nhiều máy phát công suất thấp, mỗi máy phát đ−ợc thiết kế một cách đặc biệt để phục vụ chỉ một vùng (tế bào) nhỏ và bán kính không quá vài trăm mét. Bằng việc chia tách khu vực phủ sóng ra thành nhiều tế bào nhỏ với mỗi máy phát của chính nó, có thể (tối thiểu là về mặt lý thuyết) tái sử dụng các kênh nh− nhau trong các tế bào khác nhau trong phạm vi vùng phục vụ. Các tế bào nhỏ với việc tái sử dụng kênh có thể tăng khả năng l−u l−ợng một cách thực sự. Để hiểu rõ điều này, có thể t−ởng t−ợng rằng có 12 kênh khả dụng trong một thành phố và thành phố đ−ợc bao phủ bởi 100 tế bào. Nếu tất cả các kênh có thể đ−ợc tái sử dụng trong mỗi tế bào, thì với cùng 12 kênh, thay vì 12 cuộc gọi đồng thời trong toàn bộ thành phố sẽ là 12 kênh cho mỗi tế bào và 1200 cuộc gọi đồng thời trong thành phố. Tuy nhiên, trong thực tế việc tái sử dụng nh− thế là không thể. Nếu cùng kênh đ−ợc sử dụng trong 2 tế bào khác nhau mà 2 tế bào này gần nhau về mặt địa lý, thì điều này có thể gây ra can nhiễu vô tuyến, làm méo các tín hiệu. Hiện t−ợng này đ−ợc gọi là xuyên nhiễu đồng kênh, nó có thể làm giảm tỷ số tín hiệu trên tạp âm (SNR) tới một mức độ mà tín hiệu không còn phân biệt đ−ợc nữa từ tạp âm, khi ng−ời sử dụng khác cũng đang sử dụng cùng kênh trong tế bào kế tiếp. Để đạt một SNR có thể chấp nhận đ−ợc, không nên tái sử dụng kênh giống nhau trong hai tế bào khác nhau trong mạng, trừ khi chúng đ−ợc chia tách bởi khoảng cách tối thiểu đ−ợc gọi là khoảng cách tái sử dụng σ. Mặc dù điều kiện về khoảng cách tái sử dụng làm cho việc bỏ qua một hoặc một vài tế bào tr−ớc khi tái sử dụng kênh giống nhau là cần thiết, ý t−ởng cơ bản của việc tái sử dụng kênh trong khái niệm tế bào là có căn cứ. Kênh giống nhau có thể đ−ợc sử dụng để hỗ trợ nhiều hơn một cuộc gọi đang thực hiện trong các phần khác nhau của thành phố. Điều này là có thể bởi vì nhờ sự tổn hao đ−ờng truyền vô tuyến, công suất trung bình nhận đ−ợc từ một máy phát thay đổi tỷ lệ nghịch với luỹ thừa 3 của khoảng cách từ ng−ời gửi, hoặc thậm chí một luỹ thừa cao hơn lên tới 5 hay 6 phụ thuộc vào môi tr−ờng vật lý. Kết quả là nếu nghịch đảo luỹ thừa 4 của khoảng cách đ−ợc chấp nhận, SNR có thể đ−ợc tính nh− sau: Hình 1.2 Sử dụng lại kênh ở đây dS (dN) là khoảng cách giữa nguồn tín hiệu (tạp âm) và ng−ời sử dụng, và α là hằng số vật lý của môi tr−ờng. Nh− chúng ta có thể thấy từ ph−ơng trình (1.1), SNR đ−ợc xác định không phải bởi khoảng cách địa lý dS và dN, mà bởi tỷ số giữa chúng. Nhờ đó có thể sử dụng cách biểu diễn lý thuyết graph về điều kiện khoảng cách dùng lại trong mạng tế bào. Nh− đã chỉ ra ở hình 1.2, giả sử rằng mọi tế bào đều có cùng bán kính r. Khi đó bất cứ ng−ời sử dụng nào trong tế bào A sẽ có khoảng cách lớn nhất r kể từ máy phát của nó. Khoảng cách giữa máy phát của tế bào A và ng−ời sử dụng khác trong tế bào C tối thiểu là 3r. Bởi vậy, nếu công suất của máy phát của tế bào A có giá trị vừa đủ đối với mọi ng−ời sử dụng trong tế bào A để nghe tín hiệu, công suất tín hiệu đ−ợc nhận bởi bất cứ ng−ời sử dụng nào trong tế bào C sẽ là (1/3)4 ≈ 1% của tế bào A. Tạp âm từ máy phát trong tế bào A khó có thể dẫn đến méo tín hiệu một cách đáng kể ảnh h−ởng đến thông tin trong tế bào C. Trong các hệ thống hiện đại, khoảng cách tái sử dụng 2 hay 3 có lẽ là đủ để bảo đảm tín hiệu nhận đ−ợc từ máy phát chính v−ợt trội tạp âm từ máy phát khác sử dụng cùng kênh. Nếu khoảng cách tái sử dụng 2 đ−ợc chấp nhận, các MS trong các tế bào lân cận đ−ợc bảo đảm sử dụng một nhóm các kênh khác nhau. Tuy nhiên các tế bào tSNR = Công suất tín hiệu Công suất tạp âm α (1/dS)4 α (1/dN)4 dN = (1.1)= dS 4 không lân cận có thể sử dụng cùng kênh. Ví dụ trong hình 1.2 các tế bào A và B là kế tiếp nhau, vì vậy chúng không thể sử dụng cùng kênh. Tuy nhiên, các cuộc gọi trong các tế bào A và C có thể sử dụng cùng kênh. Trong thực tế, ảnh h−ởng của việc xuyên nhiễu th−ờng không liên quan đến khoảng cách tuyệt đối, mà đến tỷ số khoảng cách giữa các tế bào với bán kính của các tế bào làm cho ý t−ởng mạng tế bào trở nên hấp dẫn hơn. Bán kính tế bào đ−ợc xác định bởi công suất máy phát và bằng cách tăng hay giảm đơn giản mức công suất của máy phát, các nhà khai thác hệ thống có thể thay đổi số l−ợng các tế bào trong hệ thống và sau đó đến số l−ợng các cuộc gọi sẽ đ−ợc hỗ trợ thông qua việc tái sử dụng. Ví dụ, nếu khoảng cách tái sử dụng bằng 3 là cần thiết cho tỷ số tín trên tạp chấp nhận đ−ợc và một mạng l−ới các tế bào bán kính 10 dặm cho phép tái sử dụng tần số trong một tế bào tại khoảng cách 30 dặm, thì một mạng các tế bào bán kính 5 dặm sẽ cho phép tái sử dụng tại khoảng cách 15 dặm và các tế bào bán kính 1 dặm sẽ cho phép tái sử dụng tại 3 dặm. Không cần bổ sung thêm kênh hệ thống dựa trên các tế bào bán kính 1 dặm sẽ hỗ trợ số l−ợng ng−ời dùng 100 lần lớn hơn hệ thống dựa trên tế bào bán kính 10 dặm. Tất nhiên, nếu chúng ta có thể giảm một cách vô hạn kích th−ớc của các tế bào, vấn đề thiếu hụt phổ tần có thể đ−ợc giải quyết một cách dễ dàng bằng việc lắp đặt số l−ợng không giới hạn các tế bào cực nhỏ. Tuy nhiên, chi phí cho việc lắp đặt và bảo d−ỡng là cao và sự phức tạp trong công việc điều khiển tăng làm cho giải pháp này không có tính khả thi. Vấn đề quan trọng là phải sử dụng tốt hơn các tài nguyên sẵn có trong hệ thống tr−ớc khi chuyển sang một hệ thống tế bào nhỏ hơn. 1.1.2 Sự chia tách tế bào Khi số ng−ời sử dụng tăng lên, có lẽ sẽ không có sự lựa chọn nào khác ngoài việc sử dụng nhiều các tế bào nhỏ hơn để hỗ trợ những đòi hỏi ngày càng tăng trong vài vùng nh− là trung tâm của thành phố. Nh−ng sẽ là quá tốn kém nếu thay thế toàn bộ cơ sở hạ tầng thông tin tế bào bằng một hệ thống tế bào bán kính nhỏ. Tuy nhiên, bằng việc sử dụng một kỹ thuật đ−ợc gọi là chia tách tế bào, các tế bào bán kính lớn có thể chia thành các tế bào bán kính nhỏ trong một khoảng thời gian. Khi mà l−u l−ợng trong một tế bào đã đạt đến điểm mà sự phân phối kênh hiện thời trong tế bào đó không còn khả năng hỗ trợ l−u l−ợng tăng thêm, thì các máy phát mới với công suất phát thấp hơn đ−ợc lắp đặt và mỗi máy phát này phủ sóng một khu vực nhỏ hơn bên trong vùng tế bào tr−ớc đây. Bằng việc phân tế bào thành nhiều tế bào nhỏ hơn, các kênh giống nhau đ−ợc gán với tế bào tr−ớc có thể đ−ợc tái sử dụng trong tế bào ban đầu. Do vậy, số l−ợng ng−ời sử dụng đ−ợc hỗ trợ tăng lên một cách đáng kể mà không làm gián đoạn bất cứ tế bào nào khác trong hệ thống. Quá trình chia tách tế bào này có thể đ−ợc lặp lại để hỗ trợ nhiều ng−ời sử dụng hơn khi cần thiết. Sự linh hoạt trong việc định thời gian và không gian đã làm cho việc chia tách tế bào thành một kỹ thuật đ−ợc −a chuộng để tăng dung l−ợng khi hệ thống mở rộng. Hệ thống có thể bắt đầu với số ít tế bào và sự đầu t− thiết bị ban đầu có thể là rất thấp. Khi số l−ợng khách hàng sinh lợi tăng lên, các tế bào mới và thiết bị có thể đ−ợc bổ sung thêm. Hơn nữa, chi phí của việc bổ sung các tế bào nhỏ hơn sẽ chỉ cần thiết trong các khu vực với mật độ l−u l−ợng cao. Mặt khác, số ít tế bào lớn sẽ đủ để hỗ trợ l−u l−ợng nhỏ trong các khu vực. Việc mở rộng của hệ thống cũng sẽ có thể đ−ợc thực hiện mà không làm lãng phí sự đầu t− tr−ớc, khi một tế bào lớn đ−ợc chia tách thành nhiều tế bào nhỏ, máy phát của tế bào chính thức sẽ không bị giải tán, thay vào đó nó sẽ phù hợp với phạm vi mới bằng cách giảm công suất. Tuy nhiên, sự chia tách tế bào cũng có những nh−ợc điểm hạn chế sự áp dụng rộng rãi của nó trong thực tế. Chi phí của việc thiết lập lên nhiều máy phát nhỏ là đủ lớn để làm cho các nhà khai thác mạng sử dụng thiết bị khả dụng một cách hiệu quả tr−ớc khi thêm nhiều tế bào hơn là hoàn toàn cần thiết. Bên cạnh việc chi phí nhiều về thiết bị, với nhiều tế bào nhỏ hơn trong mạng thì hệ thống trở nên khó khăn hơn cho việc quản lý. 1.1.3 Chuyển giao Sự phức tạp của việc điều khiển hệ thống tăng lên với một hệ thống tế bào nhỏ hơn. Với kích cỡ của các tế bào giảm đến vài trăm mét, một hiện t−ợng xảy ra ngày càng nhiều là một cuộc gọi di động không thể hoàn thành trong phạm vi của một tế bào. Một ng−ời sử dụng trong ô tô đang chạy có thể xuyên qua một vài tế bào rất nhỏ trong một cuộc đàm thoại. Không có một đ−ờng kết nối thông tin một cách chính xác đ−ợc thiết lập giữa ng−ời sử dụng và máy phát trong tế bào mới, cuộc gọi hiện thời sẽ bị mất một cách đột ngột. Để giải quyết vấn đề này, một kỹ thuật chuyển giao phức tạp đ−ợc sử dụng. Sự di chuyển của một cuộc gọi hiện tại đ−ợc giám sát một cách liên tục thông qua việc đo c−ờng độ của tín hiệu nhận đ−ợc từ các máy di động. Hệ thống tế bào sẽ có thể nhận biết khi nào một cuộc gọi di động di chuyển từ một tế bào đến một tế bào khác và có thể chuyển mạch cuộc gọi từ tế bào hiện tại đến tế bào kế tiếp mà không bị rớt hoặc ngắt quãng cuộc gọi đang đàm thoại. 1.2 Gán kênh Tài nguyên phổ tần vô tuyến bị hạn chế, chi phí cao và sự phức tạp của các tế bào nhỏ đã thúc đẩy việc nghiên cứu về việc sử dụng các kênh vô tuyến một cách có hiệu quả trong các mạng tế bào. Nói chung, vấn đề gán kênh trong một mạng tế bào là vấn đề của việc gán các kênh tần số cho các phiên liên lạc sao cho tránh đ−ợc sự xuyên nhiễu. Mục đích là sử dụng số l−ợng kênh càng ít càng tốt để cung cấp cho l−ợng ng−ời sử dụng có thể ở mức tối đa với chất l−ợng dịch vụ có thể chấp nhận đ−ợc. Tại thời điểm bất kỳ cho tr−ớc trong một mạng tế bào, số l−ợng kết nối cuộc gọi hoạt động đ−ợc cung cấp bởi trạm cơ sở gần nhất của chúng (máy phát). Dịch vụ này bao gồm việc gán một kênh vô tuyến tới mỗi cuộc gọi của thuê bao theo một kiểu mà xuyên nhiễu vô tuyến giữa hai cuộc gọi khác biệt trong mạng là ở d−ới mức độ có thể chấp nhận. Thách thức là để tìm ra các chiến l−ợc gán kênh, tìm hiểu nguyên lý của việc tái sử dụng kênh một cách tối đa mà không vi phạm những c−ỡng bức của việc tái sử dụng để nghẽn mạch là tối thiểu. Nh− đã biết, tỷ số tín hiệu trên tạp âm chỉ liên quan tới tỷ lệ của khoảng cách tới nguồn tín hiệu và khoảng cách tới nguồn tạp âm. Bởi vậy, sự c−ỡng bức xuyên nhiễu đồng kênh có thể đ−ợc tách ra một cách t−ơng xứng nh− là sự c−ỡng bức khoảng cách tái sử dụng trong một hình lục giác. Sự dịch chuyển này có thể cung cấp h−ớng tiếp cận có tính lý thuyết graph để nghiên cứu vấn đề gán kênh. Các mạng thông tin tế bào đ−ợc đ−a ra nh− graph hai chiều [5] với mỗi đỉnh đại diện một trạm cơ sở của một tế bào trong mạng và các ranh giới đại diện sự lận cận có tính địa lý của các tế bào. Cụ thể, các mạng tế bào luôn luôn đ−ợc thể hiện d−ới các hình lục giác và các hình lục giác này có thể đ−ợc định nghĩa nh− là các hình nhỏ đ−ợc đ−a ra có giới hạn của mạng tam giác không giới hạn (xem hình 1.1). Ch−ơng 2 các chiến l−ợc gán kênh Thách thức chính trong việc thiết kế một hệ thống thông tin vô tuyến là để đáp ứng nhu cầu sử dụng lớn trong khi tài nguyên phổ tần vô tuyến bị hạn chế. Kỹ thuật cơ bản đ−ợc sử dụng để tăng dung l−ợng của một hệ thống thông tin tế bào là việc tái sử dụng kênh. Tuy nhiên, việc tái sử dụng kênh bị giới hạn bởi hiện t−ợng xuyên nhiễu đồng kênh và chi phí cao liên quan với hệ thống tế bào nhỏ hơn. Các chiến l−ợc gán kênh hiệu quả là rất cần thiết để đạt hiệu quả trong việc tái sử dụng phổ tần. Trong ch−ơng này, tr−ớc tiên chúng ta đ−a ra một tổng quan chung về vấn đề gán kênh trong môi tr−ờng tế bào và sau đó thảo luận các chiến l−ợc gán kênh cơ bản. 2.1 Gán kênh cố định cho các mạng tế bào Cách tiếp cận gán kênh tần số trong mạng tế bào khác nhau cơ bản với cách tiếp cận sử dụng cho mạng LOS. Do sự phân tán trong môi tr−ờng mạng tế bào, việc sử dụng anten có độ tăng ích cao với h−ớng cố định tại MS là điều không thể thực hiện đ−ợc. Hơn nữa, do phân tán, sự phân cực không thể sử dụng hiệu quả để cung cấp các kênh riêng biệt cho các MS riêng rẽ. Thay vào đó, tiến trình gán kênh mạng tế bào là t−ơng tự nh− đối với hệ thống tế bào cung cấp các dịch vụ cho vị trí ng−ời sử dụng ch−a biết trong vùng phục vụ xác định. Mật độ ng−ời sử dụng đ−ợc thiết lập bởi thông tin l−u l−ợng, cùng với QoS, xác định dung l−ợng tốc độ dữ liệu mà mạng cần phải cung cấp. Do một vài khái niệm cơ bản của việc sử dụng lại tần số và xuyên nhiễu là t−ơng tự nh− các hệ thống tế bào, quy tắc tiếp cận thông th−ờng đối với việc quy hoạch kênh trong mạng tế bào sẽ đ−ợc thảo luận đầu tiên. Theo đó, các khía cạnh riêng biệt của đầu cuối xa cố định (chứ không phải là di động) sẽ đ−ợc kết hợp chặt chẽ cùng với các chỉnh sửa phù hợp. Các chỉnh sửa này khai thác các đơn giản hoá mà đầu cuối cố định có thể đem lại cho đầu cuối di động. Cấu trúc tế bào truyền thống cho hệ thống tế bào đ−ợc chỉ ra trong hình 2.1. Cấu trúc l−ới lục giác cơ bản cho các lớp tế bào đ−ợc chấp nhận bởi nó biểu diễn sự phủ sóng liên tục của vùng phục vụ (không nh− hình tròn) và gần giống với vùng phục vụ đối xứng tròn cho mỗi tế bào. Vì các MS ở xa đ−ợc giả thiết có các anten đẳng h−ớng, chúng sẽ nhận đ−ợc xuyên nhiễu từ tất cả các tế bào khác trong mạng, với các tế bào lân cận gần nhất có đóng góp xuyên nhiễu lớn nhất đ−ợc biểu diễn bởi các đ−ờng chấm chấm trong hình 2.1. Khoảng cách giữa các tế bào đ−ợc dùng cùng một tần số (theo đơn vị bán kính tế bào lục giác R) đ−ợc gọi là khoảng cách tái sử dụng. Khoảng cách tái sử dụng phụ thuộc vào hai yếu tố: (1) tỷ số S/I yêu cầu cần cho dịch vụ chấp nhận đ−ợc và (2) tổn thất đ−ờng truyền của tia mong muốn và các tia xuyên nhiễu. Hình 2.1. Cấu trúc mạng tế bào lục giác đều cơ bản 2.1.1 Tỷ số S/I mục tiêu Khoảng cách tái sử dụng kênh phụ thuộc vào tỷ số S/I yêu cầu để đạt đ−ợc dịch vụ có thể chấp nhận đ−ợc tại MS. Dịch vụ chấp nhận đ−ợc có thể đ−ợc miêu tả bởi độ sẵn sàng kết nối đạt đ−ợc trong phần trăm thời gian nào đó (ví dụ 99%) và trong phần trăm vị trí nhất định (ví dụ 95%) của vùng dịch vụ mạng. Giá trị đầu tiên chỉ ra chất l−ợng của tuyến liên kết trong khi giá trị thứ hai chỉ ra bao nhiêu vị trí đ−ợc cung cấp với dịch vụ thích hợp. Nh− đã biết, cả hai tín hiệu mong muốn và tín hiệu xuyên nhiễu là đều chịu sự ảnh h−ởng pha-đinh. Các ảnh h−ởng này đ−ợc mô hình tổng quát bởi hai cơ chế: 1. Sự biến thiên đ−ờng bao điện áp tín hiệu đ−ợc miêu tả bởi phân bố xác suất Rice. 2. Sự biến thiên mức tín hiệu trung bình từ vị trí đến vị trí khác không thể dự đoán tr−ớc bằng các mô hình đ−ờng truyền đơn giản. Pha-đinh che khuất th−ờng đ−ợc miêu tả bởi một phân bố chuẩn lôga của giá trị trung bình. Đ−a pha-đinh chuẩn lôga vào tính toán, tỷ số S/I tính bằng dB đ−ợc miêu tả với một phân bố xác suất đ−ợc cho bởi : ở đây S là tín hiệu mong muốn có phân bố chuẩn lôga và In là các tín hiệu xuyên nhiễu phân bố chuẩn lôga. Xác suất liên kết tới một MS có độ sẵn sàng chấp nhận đ−ợc PA là xác suất mà ρ lớn hơn ng−ỡng S/I yêu cầu ρTH đối với tỷ lệ lỗi bít yêu cầu (BER), hay: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛−= ∑ = I n N n IS 1 10/10ρ [dB] (2.1) )Pr( THAP ρρ >= (2.2) ) Thông th−ờng trong các hệ thống tế bào, tiến trình gán kênh đ−ợc thực hiện sử dụng các giá trị trung bình của tín hiệu mong muốn và xuyên nhiễu chứ không tính đến phân bố pha-đinh. Trong mạng băng rộng cố định có sự mong đợi độ sẵn sàng dịch vụ cao hơn trong hệ thống tế bào, cần phải tính đến phân bố pha-đinh trong giá trị S/I đ−ợc sử dụng để thiết lập gán kênh và tái sử dụng. Thuật toán gán kênh trong hệ thống LOS tính đến pha-đinh bằng cách đ−a vào độ dự trữ pha-đinh thích hợp trong tỷ số S/I mục tiêu khi tìm kiếm một kênh khả dụng. Hình 2.2. Phân bố xác suất suy giảm đối với mô hình pha-đinh phân bố Rice với hệ số k biến đổi Hình 2.3 Xác suất mức tín hiệu pha-đinh chuẩn lôga Một cách tiếp cận t−ơng tự có thể đ−ợc sử dụng ở đây. Nếu điều chế 16- QAM đ−ợc sử dụng, tỷ số S/I yêu cầu cho BER thô cỡ 10-3 là 12 dB (đó là FEC- có thể sửa sai tới 10-6). Nếu độ dự trữ pha-đinh là 16 dB đ−ợc sử dụng để đạt đ−ợc 90% độ sẵn sàng của tuyến với hệ số Rice k là 0 dB (xem hình 2.2), thì chỉ tiêu S/I là 28 dB. Nếu sự biến đổi vị trí theo hàm chuẩn lôga đ−ợc xét tới và giả sử độ lệch tiêu chuẩn là 8 dB, thì việc đạt đ−ợc một tỷ số S/I có thể chấp nhận đ−ợc trong 90% vị trí yêu cầu tỷ số S/I phải tăng hơn 10.5 dB (xem hình 2.3) đến 38.5 dB. Mục tiêu tỷ số tín hiệu trên xuyên nhiễu này (SIR) có thể giảm đi đáng kể nếu giả thiết phân tập anten có thể làm giảm pha-đinh đa đ−ờng, giảm độ dự trữ pha-đinh Rice 10 dB hay nhiều hơn. Mục tiêu SIR của mạng do vậy giảm tới cỡ 28.5 dB. Do yêu cầu độ sẵn sàng đặt ra, chỉ tiêu giá trị S/I này là cao hơn đáng kể các giá trị bình th−ờng sử dụng cho quy hoạch nhóm tế bào trong các hệ thống tế bào. 2.1.2 Khoảng cách sử dụng lại tần số Nếu các BS và các MS đ−ợc giả thiết có các anten đẳng h−ớng, thì yếu tố duy nhất làm suy giảm tín hiệu xuyên nhiễu so với tín hiệu mong muốn từ tế bào gần nhất là khoảng cách. Trong không gian tự do với tổn thất đ−ờng truyền tỷ lệ với 20 logd, tỷ số của khoảng cách đến BS phục vụ và khoảng cách đến BS xuyên nhiễu phải bằng 6.3 để đạt đ−ợc tỷ số S/I là 16 dB. Tuy nhiên, do các đ−ờng truyền này là không trực tiếp, tổn thất đ−ờng truyền thực từ một BS đến một MS sẽ cao hơn đáng kể tổn thất đ−ờng truyền trong không gian tự do. Tổn thất này th−ờng đ−ợc xấp xỉ trong cách tính đơn giản bởi cách tăng giá trị mũ cho số hạng suy hao khoảng cách trong ph−ơng trình tổn thất đ−ờng truyền từ 2 (đối với không gian tự do) đến các giá trị cao hơn. Điều này đ−ợc biểu diễn theo dạng dB nh− sau: L α n 10 log d (2.3) ở đây n>2. Ví dụ mô hình đ−ờng truyền trong IEEE 802.16 cho các tần số mạng tế bào, giá trị mũ này là một hàm đơn giản phụ thuộc vào các loại địa hình (A, B hay C) và độ cao anten trạm gốc trên mặt đất. Đối với một anten trạm gốc có độ cao 30m, các giá trị của số mũ là 4.79, 4.38 và 4.12 đối với các loại địa hình t−ơng ứng là A, B hay C. Giả thiết tổng quát đ−ợc chấp nhận là tán cây và tín hiệu xuyên toà nhà sẽ ảnh h−ởng đến các tín hiệu nhiễu và tín hiệu mong muốn gần nh− nhau, do đó các yếu tố tổn hao này sẽ không ảnh h−ởng đến tỷ số S/I. Nếu giá trị số mũ n = 4.38 đ−ợc sử dụng trong (2.3), thì tỷ số S/I là 16dB có thể đạt đ−ợc với tỷ lệ khoảng cách là 2.3 thay vì 6.3. Tuy nhiên, các MS trong một tế bào có sáu tế bào gần nhất sử dụng cùng một kênh. Giả thiết rằng công suất của tín hiệu xuyên nhiễu đ−ợc cộng lại, thì công suất xuyên nhiễu trên một kênh là gấp sáu lần việc tính toán ở trên. Tính đến điều này thì tỷ lệ khoảng cách tái sử dụng tăng đến 3.5. Tỷ số này chỉ ra rằng các BS xuyên nhiễu sử dụng đồng kênh phải xa xấp xỉ 3.5 lần từ MS so với BS phục vụ. Trong những điều kiện tr−ờng hợp xấu nhất khi MS có vị trí tại biên vùng phục vụ của tế bào, đó là khoảng cách từ BS mong muốn. Sử dụng tỷ số cách ly 3.5, điều này chỉ ra rằng các tế bào sử dụng cùng kênh phải ít nhất là 3.5 R từ tế bào phục vụ MS. Các tế bào màu xám trong hình 2.1 là những ví dụ về sự chia tách tế bào sao cho một kênh có thể sử dụng lại và đạt đ−ợc một tỷ số S/I mục tiêu là 16dB. 2.1.3 Sắp xếp tế bào và các mẫu gán kênh Việc tiếp cận hệ thống tế bào thông th−ờng đối với quy hoạch kênh giả thiết là một l−ới hình lục giác có thể quan sát nh− tập hợp các nhóm tế bào trong đó mỗi nhóm bao gồm số l−ợng tế bào cho tr−ớc và với các kênh có thể đ−ợc sử dụng chỉ một lần. Nhóm tế bào tạo ra các mẫu lát. Đối với mẫu lặp lại này, một số kích cỡ nhóm nhất định đ−ợc xác định nh− sau: M = i2 + ij + j2 (2.4) ở đây i và j là các số nguyên không âm với i > j. Các kết hợp đ−ợc phép của i và j mang lại các giá trị M = 1, 3, 4, 7, 12... Hình 2.1 có kích th−ớc nhóm sử dụng lại bằng 7, l−ới lục giác có thể tiếp tục vô hạn làm bằng lặp lại nhóm này và việc gán kênh của nó. Bằng việc xem xét hình dạng các kích th−ớc nhóm khác nhau, khoảng cách giữa các tế bào D có thể có mối quan hệ với bán kính tế bào R và kích th−ớc nhóm M nh− sau: Việc lựa chọn kích th−ớc nhóm sử dụng lại có thể đ−ợc xác định bởi tỷ số S/I yêu cầu. Từ mục 2.1.2 và các giả thiết của chúng, tỷ số S/I nhận đ−ợc bởi tỷ số mức tín hiệu mong muốn trên tổng các mức tín hiệu xuyên nhiễu, lần l−ợt đ−ợc xác định bởi các giá trị tổn thất đ−ờng truyền đến BS tế bào phục vụ và các BS xuyên nhiễu. Với tất cả các điều kiện khác là nh− nhau, các giá trị tổn thất đ−ờng truyền là tỷ lệ với khoảng cách và số mũ tổn thất đ−ờng truyền n. Đối với một MS ở mép tế bào của vùng phục vụ (tại khoảng cách R từ BS phục vụ), tỷ số tín hiệu trên xuyên nhiễu kí hiệu là ρ, đ−ợc viết d−ới dạng: M R D 3= (2.5) ∑ = − − = IN i n i n D R 1 ρ (2.6) Giả thiết rằng tất cả các xuyên nhiễu NI là cùng khoảng cách từ MS (D1 = D2 = ... = Di = D), thì SIR có thể đ−ợc viết theo kích th−ớc của nhóm: hay Đối với kích th−ớc nhóm là 7, và 6 xuyên nhiễu (NI = 6) và số mũ tổn hao là 4.38, tỷ số S/I nhận đ−ợc từ (2.7) là 21.2 dB. Một chỉ tiêu dung l−ợng mạng C đ−ợc cho bởi: với NS là số kênh khả dụng trong mạng. Thay thế (2.9) vào (2.8) nhận đ−ợc: Một ví dụ gán kênh băng tần số con đ−ợc chỉ ra trong hình 2.4. Trong tr−ờng hợp này, mỗi tế bào đ−ợc phân chia thành 3 sector 1200, đây là một cấu hình tiêu biểu trong các hệ thống tế bào. áp dụng kiểu gán kênh này cho tr−ờng hợp 21 kênh với độ rộng băng 6 MHz sẽ đ−ợc phân chia thành 7 nhóm, mỗi nhóm 3 kênh và I n N M )3(=ρ (2.7) 3 )( /2 nINM ρ= (2.8) C NM M NC SS == , (2.9) 3 )( /2 nIS N C N ρ= (2.10) n I S N NC /2)( 3 ρ= (2.11) một trong ba đ−ợc gán cho mỗi sector α, β hay ɣ. Kết quả là 6 MHz phổ tần khả dụng cho các MS trong vùng phục vụ của sector đó. Độ rộng băng 6 MHz có thể phân chia thêm nữa để phù hợp với công nghệ đ−ợc triển khai. Việc gán kênh này đ−ợc giả thiết phân bố địa lý của l−u l−ợng là đồng đều. Tuy nhiên, phân bố th−ờng là không đồng đều. Hơn nữa, mục tiêu tiếp thị cho việc ứng dụng và phục vụ trong mạng có lẽ thiên về kinh doanh hay h−ớng về vùng dân c− sẽ tạo ra phân bố địa lý l−u l−ợng không đồng đều. Trong tr−ờng hợp này, có thể mong muốn đ−ợc sự chỉ định nhiều kênh hơn trên một vài sector và ít hơn trên các sector khác để phù hợp với các tải khác nhau. Hình 2.4 Sắp xếp băng tần số trong nhóm 7 tế bào và 3 sector trên một tế bào Việc sử dụng các mẫu nhóm tế bào để phân phối các kênh trong hệ thống vô tuyến nh− miêu tả ở đây là cách tiếp cận khá thô sơ song điều đó là hữu ích cho sự hiểu biết các cơ chế xuyên nhiễu phức tạp. Điều đó là không có nhiều giá trị đối với việc gán kênh trong hệ thống thực, mặc dù nó vẫn đ−ợc sử dụng trong ph−ơng pháp này. Các hạn chế lớn nhất của việc tiếp cận này là: - Kích th−ớc nhóm nguyên không cung cấp đầy đủ tính linh hoạt gán kênh để tạo ra quy hoạch kênh có hiệu quả cho phạm vi rộng của các tỷ số S/I. Sự tiến bộ của công nghệ mà có thể hạ thấp mục tiêu S/I đi 3 hay 6 dB có thể tăng dung l−ợng đáng kể, nh−ng từ (2.8), ta thấy sự tiến bộ nh− vậy không thể cho phép kích th−ớc nhóm nhỏ hơn (chẳng hạn, từ 7 xuống 4). - Các tế bào đồng đều không phản ánh hình dáng kỳ cục, đôi khi các vùng phục vụ gián đoạn và các vùng xuyên nhiễu của các tế bào thực. - Việc bố trí hình l−ới lục giác đều của các tế bào có thể hiếm khi đạt đ−ợc dù chỉ là gần đúng. Hơn nữa, việc lựa chọn các vị trí BS bị hạn chế bởi cấu trúc tháp vô tuyến hiện có. Do những hạn chế này, việc tiếp cận nhóm tế bào để gán kênh không phải là một sự lựa chọn tốt cho việc gán các kênh trong hệ thống tế bào. Thay vào đó, tiếp cận tối −u có thể sử dụng mà không đòi hỏi gán kênh đồng đều hay gán kênh theo nhóm. 2.2 Gán kênh động Việc thảo luận gán kênh cho tới nay đã đ−ợc giả thiết là các kênh một khi đã gán, là gán kênh cố định tại sector. Trong vài tr−ờng hợp, có thể nhận thấy rằng phân bố l−u l−ợng địa lý có hai hay ba mẫu riêng biệt trong một ngày, do vậy hai hay ba cách bố trí kênh tĩnh có thể đ−ợc phát triển và chuyển mạch mạng từ kế hoạch chỉ định một kênh tới kênh khác để phù hợp phân bố tải l−u l−ợng tốt nhất. Chẳng hạn, trong hệ thống tế bào nơi tập trung l−u l−ợng lớn suốt cả ngày là các khu vực th−ơng mại và công sở. Kết thúc ngày làm việc, tải l−u l−ợng dịch trong các vị trí dọc theo những con đ−ờng và các hành lang chuyên chở đ−ợc sử dụng bởi ng−ời đi làm. Hai kế hoạch kênh để gán lại kênh từ các sector tế bào trong các khu vực th−ơng mại cho các sector tế bào dọc theo hành lang chuyên chở vào lúc 17 đến 18 giờ là dạng cơ bản của DCA. Trong ví dụ này, gán kênh là đ−ợc lập kế hoạch tr−ớc theo tải l−u l−ợng (đo đ−ợc hoặc −ớc l−ợng). DCA đích thực gán các kênh và nguồn tài nguyên mạng khác trong thời gian thực khi cần thiết để thích hợp với l−u l−ợng ở bất cứ nơi nào trong vùng phục vụ. Đối với các mạng vô tuyến băng rộng cố định, vấn đề tính di động liên quan với các hệ thống điện thoại tế bào là không có, nh−ng các kiểu phân bố lại l−u l−ợng t−ơng tự trong ngày có thể xuất hiện. Việc di chuyển nguồn tài nguyên kênh từ các khu vực th−ơng mại trong suốt cả ngày đến vùng dân c− vào ban đêm cũng đ−ợc áp dụng một cách hợp lý cho các hệ thống băng rộng tế bào cố định. Nếu có sẵn các −ớc l−ợng tải l−u l−ợng t−ơng đối, các kế hoạch gán đa kênh có thể đ−ợc tính toán và thực hiện tự động bởi mạng cho chu kỳ thời gian hàng ngày thích hợp. Sử dụng gán kênh nhiều kế hoạch đặt tr−ớc cho mạng là thuyết phục bởi vì nó không đặt lên bất cứ gánh nặng nào khác cho việc khai thác mạng ngoài việc thực hiện chuyển mạch gán kênh vài lần trong ngày. Tuy nhiên, điều đó thực hiện dựa vào −ớc l−ợng tải l−u l−ợng và số l−ợng kiểu đ−ờng truyền mà dự báo mức tín hiệu và xuyên nhiễu. Các lỗi trong việc đánh giá này hay các dự báo sẽ dẫn đến các kế hoạch gán kênh là tiềm ẩn sự hoà hợp kém trong mạng, tồi tệ nhất là dẫn đến xung đột xuyên nhiễu trầm trọng và gián đoạn dịch vụ. Đối với DCA thời gian thực, các cách tiếp cận khác nhau có thể đ−ợc phân chia thành hai loại dựa trên cơ sở các quyết định nào đ−ợc thực hiện gán các kênh. 2.2.1 DCA tập trung Bằng việc điều khiển tập trung, tất cả các thông tin trong mạng về kênh thông th−ờng, các xung đột xuyên nhiễu, và l−u l−ợng đ−ợc đ−a tới vị trí trung tâm, tại đây quyết định việc thực hiện gán kênh thông qua mạng. Nguồn tài nguyên thông tin giữa các BS là cần thiết để mang thông tin, cũng nh− việc tính toán đ−ợc yêu cầu để thực hiện các quyết định gán kênh. Trong tr−ờng hợp cực đoan, mỗi khi MS yêu cầu dịch vụ (hay một mạch trong một mạng chuyển mạch- kênh), DCA tập trung phải đ−ợc tính toán lại chiến l−ợc gán kênh tối −u cho mạng tổng thể. Độ trễ đ−ợc kể đến trong sự hoàn thành nhiệm vụ này phải đ−ợc thêm vào độ trễ hệ thống. Cách tiếp cận này là không khả thi cho các hệ thống tế bào 2G chuyển mạch kênh [17]. Đối với các hệ thống tế bào chuyển mạch gói, những khó khăn tính toán là trầm trọng hơn. Những trở ngại của việc tính toán và thông tin của điều khiển tập trung đầy đủ có thể đ−ợc giảm nhẹ đến mức độ có ích bằng chia mạng thành các nhóm tế bào lân cận, một ph−ơng pháp đ−ợc biết đến nh− là DCA phân tán. Với cách tiếp cận này, những quyết định về việc gán kênh là hạn chế giữa các nhóm tế bào chứ không phải là đ−ợc thực hiện trên cơ sở toàn mạng. Nh−ợc điểm là hầu hết các mạng làm việc trong môi tr−ờng truyền sóng không đồng nhất của vùng phục vụ và xuyên nhiễu có thể không tiếp giáp là rất lớn. Điều này đặc biệt đúng trong hệ thống vi tế bào trong vùng đô thị nơi mà mỗi chỗ ngoặt của góc phố có thể bắt đầu một sự chuyển giao tế bào. Trong những tr−ờng hợp nh− vậy, sự xung đột xuyên nhiễu là tránh đ−ợc thông qua việc gán kênh động thông minh. 2.2.2 DCA không tập trung Về bản chất điều khiển không tập trung cho phép các sector tạo nên các quyết định cho chính bản thân chúng về các kênh nào có khả năng sử dụng và kênh nào là không dùng đ−ợc tại thời điểm sector phải xử lý l−u l−ợng đến/từ một MS. Cách tiếp cận thông th−ờng là sử dụng ph−ơng pháp nào đó cho các sector riêng rẽ và các MS để cảm nhận hay đo xuyên nhiễu trong các kênh khả dụng cho hệ thống. Trên cơ sở của phép đo này, một sự lựa chọn đ−ợc tạo ra đối với kênh tốt nhất để sử dụng cho việc truyền dẫn. Có vài cách tiếp cận để tìm ra mức độ xuyên nhiễu trên các kênh. Một chu kì rỗi ngắn không truyền dẫn có thể đ−ợc sắp xếp tr−ớc bởi sector phục vụ để các MS có thể phát hiện các tín hiệu đ−ờng xuống từ các sector BS khác bằng việc quét các kênh trong dải băng trong suốt khoảng thời gian rỗi. Một cách t−ơng tự, đối với các kênh đ−ờng lên, sector BS có thể quét các kênh để xác định kênh có mức thấp nhất của công suất xuyên nhiễu. Sector BS và MS có thể chia sẻ kết quả việc quét này để giúp nhau trong sự lựa chọn kênh. Hệ thống ghép kênh phân chia theo tần số trực giao (OFDM) sử dụng công nghệ biến đổi Fourie nhanh (FFT) và khối bộ nhân để sửa pha-đinh chọn lọc tần số đã đ−ợc trang bị đặc tính đo tín hiệu này. Trong [24], kết quả mô phỏng đã đ−ợc trình bày đối với DCA cho l−u l−ợng chuyển mạch kênh thông th−ờng sử dụng một mô hình đ−ờng truyền lý t−ởng hoá với số mũ tổn thất đ−ờng truyền n = 4 cùng với kiểu pha-đinh chuẩn lôga. ở đó cũng sử dụng cảm nhận xuyên nhiễu lý t−ởng không có sự lựa chọn gán kênh xung đột phát sinh do nguyên nhân trễ thời gian khoảng cách đối với các sector đang quét cùng kênh. Việc mô phỏng chứng minh rằng DCA có và không có điều khiển công suất có thể đem lại dung l−ợng mạng v−ợt quá dung l−ợng của cả hai kỹ thuật CDMA không đồng bộ và CDMA đồng bộ. Mô hình hệ thống CDMA đồng bộ thừa nhận việc triệt xuyên nhiễu hoàn toàn trong tế bào nh− có thể đạt đ−ợc với ph−ơng pháp phát hiện đồng thời hoàn hảo. Hình 2.5 biểu diễn một ví dụ của số liệu về hiệu quả phổ tần đ−ợc đ−a ra từ [24] so sánh các kết quả dung l−ợng đối với DCA của kỹ thuật CDMA không đồng bộ và kỹ thuật CDMA đồng bộ. Hiệu quả trong hình 2.5 là hiệu quả đa truy nhập đ−ợc định nghĩa là tỷ số của số các trạm xa hoạt động đồng thời tại một tốc độ dữ liệu đã cho trên một sector trong một cấu trúc tế bào lục giác bán vô hạn so với số ng−ời sử dụng tại cùng một tốc độ dữ liệu đ−ợc phép đối với một sector đơn (không có xuyên nhiễu giữa các tế bào). Sự cải thiện với DCA trên CDMA một phần là vì số trung bình xuyên nhiễu trên độ rộng băng trải rộng xảy ra với CDMA, thậm chí đối với CDMA đồng bộ trong đó xuyên nhiễu nội tế bào đ−ợc loại trừ. DCA đ−a thông tin vào quá trình sử dụng nguồn tài nguyên phổ tần bằng việc lựa chọn các kênh với các giá trị SIR cao hơn chứ không chấp nhận một kênh với SIR trung bình. Do thông tin thêm vào và thông tin đ−ợc xử lý, nên có thể hy vọng rằng việc sử dụng phổ tần sẽ đạt hiệu quả cao hơn nữa. Hình 2.5 Hiệu quả phổ tần của DCA lý t−ởng đ−ợc so sánh với CDMA 2.2.3 Chia tách kênh Một loại khác của DCA đ−ợc gọi là chia tách kênh [3], giống nh− hầu hết các ph−ơng án DCA, chia tách kênh đối với các hệ thống TDMA đòi hỏi mỗi sector có thể truyền tải trong kênh bất kỳ đ−ợc cho phép trong hệ thống. Ph−ơng pháp này sử dụng một cách tiếp cận huấn luyện trong đó danh sách −u tiên của các kênh đ−ợc duy trì cho mỗi sector. Ban đầu, các kênh mong muốn đ−ợc xem xét nh− nhau về l−u l−ợng mang. Thông tin về sự thành công của việc sử dụng một kênh so với kênh khác đ−ợc tập hợp, kênh thành công đ−ợc xếp hạng cao hơn trong danh sách −u tiên. Khi danh sách tăng, đối với mọi truyền dẫn đ−ợc đ−a ra việc lựa chọn thực hiện để sử dụng kênh xếp hạng cao nhất không đ−ợc sử dụng bởi MS khác trên sector đó. Hình 2.6 biểu diễn l−u đồ cho thuật toán chia tách kênh. Mỗi sector xếp hạng mỗi kênh sử dụng một hàm −u tiên P(i): t s N NiP =)( (2.12) với Ns là số l−ợng truy nhập thành công cho kênh cộng với số l−ợng truy nhập kênh khi kênh rỗi nh−ng không thể truy nhập đ−ợc, và Nt là tổng số lần thử cho kênh. Từ hình 2.6, sector chọn ra một kênh từ danh sách kênh hiện thời trên cơ sở của −u tiên cao nhất P(i). Nếu kênh rỗi, nó kiểm tra khả năng truy nhập. Nếu nó có khả năng truy nhập, kênh đ−ợc lựa chọn cho việc sử dụng và −u tiên của nó tăng thêm một. Nếu kênh rỗi nh−ng không thể truy nhập vì không có các máy phát RF khả dụng trên BS, −u tiên của nó cũng đ−ợc tăng thêm một nh−ng thuật toán còn tìm một kênh mới từ danh sách −u tiên. Quá trình đệ quy này tiếp tục cho đến khi việc truyền dẫn đ−ợc xử lý hay việc truyền dẫn bị khoá. Sự mô phỏng trong [3] chỉ ra rằng thuật toán chia tách kênh có thể làm tốt hơn FCA đ−ợc miêu tả tr−ớc đây. Hình 2.6 L−u đồ thuật toán chia tách kênh DCA Chọn kênh −u tiên cao nhất không sử dụng Kênh sử dụng trong các tế bào khác ? Kênh cuối? Tăng −u tiên kênh Giảm −u tiên kênh Chọn kênh −u tiên cao nhất tiếp theo Sử dụng kênh và tăng −u tiên của chúng Kênh không thể truy nhậpđ−ợc? Kết thúc N N Y Y Y N Bắt đầu Cuộc gọi bị khoá 2.2.4 Gán gói động Khi các quyết định gán kênh đ−ợc thực hiện trên cơ sở gói - gói hay phiên gói - phiên gói, DCA đ−ợc gọi là gán gói động (DPA). Các tài liệu [8], [9] đ−ợc công bố gần đây tập trung vào DPA và những −u điểm mà nó có thể cung cấp. Trong [8] đề cập đến một nh−ợc điểm cho ph−ơng pháp đo xuyên nhiễu. Khi các sector khác nhau quét các kênh xuyên nhiễu thấp, cùng kênh đó có thể đ−ợc phát hiện bởi hai hay nhiều sector nh− kênh mong muốn, bởi vậy chúng tạo ra cùng gán kênh xung đột. Kết quả mô phỏng đ−ợc đ−a ra trong [8], các điều kiện bổ sung đã áp đặt rằng các khung lấy mẫu xuyên nhiễu (thời gian rỗi) là so le giữa các tế bào gần nhau trong cùng một nhóm để tránh tr−ờng hợp này. Nh− đã đề cập tr−ớc đây, trong môi tr−ờng đ−ờng truyền phức tạp, các tế bào gần nhau có thể không gần nhất về mặt khoảng cách. Việc xác định các tế bào nào cần phải liên kết với nhau thông qua các ph−ơng pháp so le có thể khó khăn, và có lẽ cũng là không thể khi các tế bào là thành viên của nhiều nhóm do kết quả của sự hiện diện xuyên nhiễu của chúng. Trong một vấn đề liên quan, quét xuyên nhiễu tại điểm cố định nào đó sẽ dần dần lỗi thời trong khoảng thời gian cho đến khi quét kế tiếp. Trong [8], một phần trăm tỷ số S/I của thời gian giảm đi khoảng 9 dB giữa việc quét SIR ban đầu và quét một SIR hoàn thành ở gần cuối của truyền dẫn. Các lỗi truyền dẫn nhận đ−ợc từ SIR thấp hơn sẽ là một hàm của độ dài truyền dẫn, độ dài này lại phụ thuộc vào sự thống kê l−u l−ợng. Các kết quả mô phỏng đ−ợc giới thiệu trong [8] nói chung đều sử dụng các mô hình mạng lý t−ởng với mô hình đ−ờng truyền sóng đơn giản sử dụng một số mũ suy giảm khoảng cách n = 4. Trong sự hạn chế của mô phỏng lý t−ởng này, các kết quả mô phỏng DPA chỉ ra dung l−ợng đáng kể nhận đ−ợc thông qua việc sử dụng DCA. 2.2.5 DCA đối với các mạng UTRA – TDD Nh− đã đề cập, các hệ thống CDMA nói chung không đòi hỏi quy hoạch kênh vì chúng đã đ−ợc thiết kế phù hợp xuyên nhiễu giữa các tế bào bằng cách lấy trung bình công suất xuyên nhiễu trên băng thông trải phổ. Đối với các hệ thống TDD CDMA, phân đoạn miền thời gian thành các khe chiếm dụng bởi số l−ợng ng−ời sử dụng bị hạn chế, một cơ cấu xuyên nhiễu đ−ợc thêm vào gây ra bởi xuyên nhiễu BS - BS và MS - MS trên cả đ−ờng lên và đ−ờng xuống, nh− đã đ−ợc chỉ ra ở hình 2.7. Hình 2.7 (a) Các đ−ờng tính toán xuyên nhiễu FDD (b) Các đ−ờng tính toán xuyên nhiễu TDD Trong khi các khung thời gian có thể đ−ợc đồng bộ giữa các tế bào lân cận, vẫn còn vấn đề chỉ định khác nhau các khe thời gian kênh đ−ờng xuống và đ−ờng lên dẫn đến các khe thời gian kênh đ−ờng xuống xuất hiện trong các khe thời gian kênh đ−ờng lên trong các tế bào lân cận. Kết hợp việc chỉ định khe thời gian kênh đ−ờng lên - đ−ờng xuống trong các tế bào hạn chế tính linh hoạt mà các tế bào phải điều chỉnh để thay đổi các luồng l−u l−ợng của chúng. Vấn đề xuyên nhiễu đã đ−ợc nghiên cứu qua mô phỏng trong [16]. Mặc dù việc mô phỏng không tính tới phát hiện đồng thời cho việc giảm xuyên nhiễu trong tế bào, nó đã chứng minh xuyên nhiễu ảnh h−ởng giữa các sector có thể giảm đi do sử dụng việc đồng bộ khung. Quy hoạch mạng tính đến việc chia tách khoảng cách tái sử dụng nh− với các hệ thống TDMA truyền thống cũng đ−ợc trợ giúp, nh−ng điều này sẽ giảm dung l−ợng. Trong [14], việc sử dụng DCA cho UTRA TDD đ−ợc thảo luận bằng ph−ơng pháp ghi địa chỉ xuyên nhiễu. T−ơng tự nh− đối với DPA, nó sử dụng các phép đo xuyên nhiễu trong các khe thời gian để gán các −u tiên cho các khe thời gian tại đó khe thời gian với xuyên nhiễu thấp nhất đ−ợc gán −u tiên cao nhất. Danh sách −u tiên đ−ợc cập nhật một cách định kỳ. Việc tiếp cận này sẽ nâng cao việc sử dụng phổ tần bằng cách t−ơng tự cho DPA. 2.3 Tối −u hoá gán kênh trong các mạng tế bào Việc tiếp cận nhóm có thể bị bỏ rơi hoàn toàn để ủng hộ một kế hoạch kênh trong đó việc gán kênh cho các sector BS đ−ợc thực hiện sao cho vừa đạt đ−ợc mục tiêu phục vụ l−u l−ợng vừa đạt đ−ợc SIR mục tiêu trên toàn bộ vùng phục vụ của sector. Các kênh không cần phải gán theo mẫu cụ thể bất kỳ (là mục tiêu của cách tiếp cận nhóm ở trên), nh−ng thay vào đó có thể gán tuỳ ý trên cơ sở kênh- kênh. Việc giảm nhẹ sự hạn chế này cho ta sự linh hoạt đáng kể để hoàn thành việc gán kênh hiệu quả hơn. Rõ ràng cách tiếp cận này cũng có thể đ−a vào tính toán vùng phủ sóng không đồng đều, không liền kề và các vùng xuyên nhiễu. Có nhiều thuật toán gán kênh trong cách tối −u hay tựa tối −u. Tất cả chúng đều đòi hỏi rằng hàm mục tiêu nào đó phải đ−ợc miêu tả một cách rõ ràng. Đối với tr−ờng hợp là hệ thống vô tuyến, mục tiêu là cung cấp đầy đủ nguồn tài nguyên phổ tần (các kênh) để mang l−u l−ợng mong đợi với mức độ QoS mong muốn, và thực hiện việc đó trong khi vẫn duy trì tỷ số S/I mục tiêu. Thuật toán tối −u khi đó cố gắng tìm ra một nhóm gán kênh cho các sector BS trong mạng đồng thời thoả mãn các mục tiêu này càng chặt chẽ càng tốt. Theo cách nói của các thuật toán tối −u, lỗi hay sự khác nhau giữa các kết quả trạng thái hệ thống và hàm mục tiêu đang đ−ợc giảm đến mức tối thiểu. Lỗi này cũng đ−ợc coi là chi phí. Hàm mục tiêu th−ờng đ−ợc xác định trên các l−ới nghiên cứu bao phủ vùng phục vụ mạng. Việc tiếp cận các l−ới nghiên cứu đã đ−ợc sử dụng cho các bản đồ che khuất và phủ sóng. Tại chỗ sự giao nhau mỗi l−ới hay ô vuông, các yêu cầu tỷ số S/I và l−u l−ợng đã đ−ợc xác định. Thuật toán gán kênh sau đó tham gia vào việc tìm một nhóm gán kênh cho các sector BS mà thoả mãn đ−ợc các mục tiêu này tại tất cả các vị trí l−ới. Một cách thông th−ờng, tất cả các mục tiêu không thể thoả mãn một cách đồng thời, do vậy một vài mức độ lỗi còn lại có thể chấp nhận đ−ợc cũng phải đ−ợc xác định. Trong số nhiều thuật toán tối −u khả dụng, ba cách tiếp cận nổi bật có thể ứng dụng đ−ợc cho bài toán tìm gán kênh tối −u. Về cơ bản tất cả các ph−ơng pháp đó cung cấp một cách có hệ thống việc dự đoán tại một nhóm gán kênh, và sau đó đánh giá việc dự đoán l−u l−ợng đạt đ−ợc và mục tiêu tỷ số S/I. Việc dự đoán mới sau đó thực hiện sử dụng sự hiểu biết có đ−ợc từ dự đoán thứ nhất để cho việc dự đoán tiếp theo tiến gần đến mục tiêu. Tiến trình này tiếp tục cho đến khi mục tiêu đạt đ−ợc trong một cửa sổ có thể chấp nhận đ−ợc, hay thuật toán không thể tạo ra bất kỳ sự thay đổi nào cải thiện kết quả, hay thời gian −ớc tính trở nên quá mức. Ba kỹ thuật tối −u chính đ−ợc miêu tả d−ới đây. 2.3.1 Ph−ơng pháp hạ xuống dốc nhất Ph−ơng pháp hạ xuống dốc nhất tạo ra sự điều chỉnh thử nghiệm trong tất cả các tham số khả dụng để xác định các điều chỉnh có ảnh h−ởng lớn nhất đến hạ thấp lỗi. Sự điều chỉnh đó làm giảm lỗi nhiều nhất đ−ợc thực hiện và tiến trình đ−ợc lặp lại. Nếu lỗi đ−ợc biểu diễn trực quan nh− một bề mặt đa chiều, việc tiếp cận này tìm ra độ dốc nhất hạ bề mặt lỗi tới một điểm lỗi cực tiểu. Mặt hạn chế chính của ph−ơng pháp này là nó có thể đi đến bế tắc trong việc làm giảm đến nhỏ nhất lỗi cục bộ của mọi sự thay đổi trong các kết quả gán kênh trong một lỗi cao hơn và hậu quả là sự hiệu chỉnh các tham số tiếp theo sẽ không cải thiện kết quả. Mức tối thiểu cục bộ có thể không phải là mức lỗi tối thiểu tối −u, bởi vậy chất l−ợng của kế hoạch gán kênh có thể không đạt tối −u. Một vài thủ thuật, nh− là sự thay đổi độ lớn b−ớc hiệu chỉnh tham số, đôi khi có thể đ−ợc sử dụng để nhảy ra ngoài mức tối thiểu cục bộ, nh−ng điều này có thể nhảy quá mức tối thiểu lý t−ởng tối −u. 2.3.2 Ph−ơng pháp ủ mô phỏng (SA) Kỹ thuật ủ mô phỏng (SA) đã đ−ợc mô tả trong [2], [4], [11]. SA bắt đầu với một nhóm gán kênh ngẫu nhiên s (cũng đ−ợc gọi là một trạng thái hệ thống) tại các sector. Lỗi hoặc chi phí C(s) của trạng thái này đ−ợc tính toán. Một trạng thái hệ thống mới s’ đ−ợc lựa chọn một cách ngẫu nhiên và chi phí C(s’) của nó đ−ợc tính. Nếu C(s’) ≤ C(s), thì trạng thái mới hay tập hợp gán kênh đ−ợc giữ lại và tập hợp gán kênh ngẫu nhiên mới đ−ợc tạo ra từ đó. Nếu C(s’) > C(s), cấu hình kênh đ−ợc chấp nhận với một xác suất đ−ợc xác định bởi: với T là ‘nhiệt độ’. Ph−ơng trình (2.13) đ−ợc biết nh− tiêu chuẩn vùng Metropolis [22]. Nhiệt độ cơ sở quyết định độ lớn sự thay đổi trạng thái hệ thống có thể đ−ợc tạo ra từ một trạng thái này đến trạng thái khác. Vì quá trình SA là liên tục, nhiệt độ đ−ợc hạ thấp theo kế hoạch. Tại nhiệt độ thấp cuối cùng, chỉ những thay đổi nhỏ trong các trạng thái hệ thống là có thể. Kích th−ớc thực của sự thay đổi trạng thái hệ thống đ−ợc tìm thấy từ phân bố Gau-xơ, nh− vậy nhiệt độ điều khiển thực sự độ lệch tiêu chuẩn của phân bố Gau-xơ xác định các thay đổi trạng thái. Theo ph−ơng pháp này, quá trình là t−ơng tự quá trình ủ để làm lạnh mẩu kim loại trong các b−ớc tăng nhỏ. Làm lạnh trong ph−ơng pháp này, các phần tử kim loại có cơ hội để di chuyển vào mẫu l−ới đều đặn tạo ra kim loại bền và dễ uốn với năng l−ợng nội thấp (chi phí). Trái lại, kim loại đ−ợc làm nóng có thể ‘làm nguội lạnh’ bởi việc ngâm ⎥⎦ ⎤⎢⎣ ⎡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −−= T sCsCP )()(exp,1min , (2.13) vào n−ớc lạnh. Điều này dẫn đến kim loại cứng nh−ng giòn mà sự gãy là dễ dàng hơn bởi các phân tử không đ−ợc định vị trong cấu trúc l−ới lý t−ởng. −u điểm chính của SA cho vấn đề gán kênh là điều không thể dễ dàng mắc kẹt tại cực tiểu cục bộ nh− với ph−ơng pháp hạ xuống dốc nhất. Điều này đạt đ−ợc bằng việc cho phép các trạng thái chi phí cao hơn để đôi khi có thể chấp nhận đ−ợc với xác suất đ−ợc cho bởi (2.9). Tuy nhiên, SA có thể là ph−ơng pháp cần nhiều tính toán chuyên sâu, đặc biệt nếu số l−ợng lớn của các sector và các kênh đ−ợc tính đến. 2.3.3 Ph−ơng pháp thuật toán di truyền Sự lựa chọn cách mạng bắt ch−ớc thuật toán di truyền (GA) để đạt đ−ợc một trạng thái hệ thống cung cấp lỗi cực tiểu trong việc hoàn thành mục tiêu gán kênh. Dân số đ−ợc hiệu chỉnh một cách ngẫu nhiên sử dụng các cơ chế nh− là thừa kế trong đó thành viên dân số mới đ−ợc phân phối sử dụng hầu hết ‘các gien’ từ hai bố mẹ trong dân số có tr−ớc, và sự đột biến trong đó số gien đã cho đ−ợc thay đổi một cách ngẫu nhiên. Một sự miêu tả đầy đủ việc sử dụng GA cho bài toán gán kênh có thể tìm thấy trong [10]. Việc sử dụng GA cho gán kênh trong các hệ thống tế bào đ−ợc miêu tả trong [20], [23]. Giống nh− SA, GA cung cấp một cách có hệ thống việc dự đoán để đạt đ−ợc dân số thích nghi tốt tăng lên làm cho sự thực hiện công việc tốt hơn của việc đạt đ−ợc các mục tiêu mạng. Nó cũng tạo ra sự miễn giảm hợp lý khỏi bế tắc trong cực tiểu hoá cục bộ; nh−ng cũng nh− với SA, nó có thể cần tính toán chuyên sâu cho các mạng lớn. 2.3.4 Gán kênh trong các hệ thống W- CDMA Đối với các hệ thống W- CDMA, kỹ thuật đa truy nhập đ−ợc thiết kế để phù hợp với môi tr−ờng nhiều xuyên nhiễu trong đó mỗi kênh tần số đ−ợc sử dụng trên mỗi sector. Sự phân biệt giữa các tín hiệu đ−ờng xuống và đ−ờng lên đạt đ−ợc qua việc sử dụng các mã khác nhau. Việc gán các mã cho các tín hiệu kênh đ−ờng lên và đ−ờng xuống đ−ợc thực hiện trong thời gian thực bởi phần cứng mạng vì các đ−ờng truyền giữa các BS và các MS là cần thiết cho liên lạc. Vì lý do này, kế hoạch gán kênh là không cần thiết. Tuy nhiên, có các mã tạp âm giả ngẫu nhiên (PN) đ−ợc sử dụng để phân biệt các mã trải sử dụng trên một sector với các mã trải trên một sector khác. Đôi khi, xung đột trong các mã PN có thể nảy sinh ra tại các vị trí trong vùng phục vụ mà tỷ số mức tín hiệu và các trễ thời gian giữa hai BS có cùng một xung đột mã PN. Ph−ơng trình liên quan với việc tính toán các vùng xung đột PN tiềm tàng cho các hệ thống IS - 95 CDMA có thể tìm thấy trong [29]. Các ph−ơng pháp t−ơng tự có thể quy hoạch mã xáo trộn trong dịch vụ viễn thông di động toàn cầu (UMTS) W - CDMA. Các ph−ơng pháp mã xáo trộn W - CDMA khác đ−ợc thảo luận trong [17]. Đối với TD - CDMA sử dụng trong UTRA - TDD, có khả năng cho xuyên nhiễu từ sector đến sector khác và từ MS đến MS khác, điều đó đ−ợc chỉ ra trong hình 2.7. Phụ thuộc vào việc đồng bộ khung giữa các tế bào lân cận và sự chỉ định các khe thời gian giữa đ−ờng lên và đ−ờng xuống, xuyên nhiễu giữa các tế bào có thể xuất hiện với UTRA - TDD, đặc biệt khi phân bố l−u l−ợng là không đồng đều cao. Điều này đ−ợc xử lý cơ bản bằng sử dụng các DCA chứ không phải quy hoạch mạng. Sử dụng DCA cho việc truy nhập vô tuyến mặt đất UMTS (UTRA)TDD đã đ−ợc thảo luận trong mục 2.2.5. 2.4 Dung l−ợng mạng tế bào và các ph−ơng pháp nâng cao dung l−ợng Một ph−ơng pháp đánh giá dung l−ợng mạng là tính toán dữ liệu khả dụng bps/Hz của độ rộng băng tần trên km2 của vùng phục vụ. Trong ví dụ trên, 6 MHz băng thông đ−ợc dùng cho mỗi sector phục vụ. Nếu hiệu quả của điều chế và mã hoá là 3.2 bps/Hz, ví dụ (tiêu biểu là 16- QAM mã hoá), và bán kính phục vụ của mỗi tế bào là 10 km (104 km2/sector), thì dung l−ợng cỡ khoảng 183kbps/km2. Bán kính phục vụ cho hệ thống tế bào đ−ợc thiết lập để đạt đ−ợc độ sẵn sàng tuyến thích hợp với các mức công suất sector tiêu biểu. Tuy nhiên, mẫu sử dụng lại tần số đ−ợc dựa trên tỷ số giữa bán kính phục vụ tế bào R và khoảng cách giữa các tế bào D. Nếu công suất BS đ−ợc giảm đi, sao cho bán kính phục vụ chỉ là 5 km, vùng phục vụ sector giảm xuống còn 26.2 km2 và dung l−ợng tăng lên cỡ 733kbps/km2. Tất nhiên, việc cân bằng nhiều tế bào và BS là cần thiết để bao phủ cùng một vùng phục vụ, do vậy chi phí hạ tầng mạng tăng lên một cách tỷ lệ để đạt đ−ợc dung l−ợng cao hơn. Độ khả dụng dung l−ợng sử dụng một trong các chiến l−ợc gán kênh đ−ợc miêu tả trong các mục tr−ớc bị hạn chế bởi xuyên nhiễu giữa các tế bào quyết định các tần số có thể tái sử dụng ở mức độ nào. Việc tiếp cận đã sử dụng để cải thiện tình huống: (1) tìm cách để khử hay loại bỏ xuyên nhiễu trên kênh đ−ợc chọn, (2) đối với SINR kênh cho tr−ớc, làm thích nghi các ph−ơng pháp điều chế và mã hoá để đạt đ−ợc tỷ lệ lỗi thấp hơn tại tốc độ dữ liệu cao nhất có thể. Một vài kỹ thuật này sẽ đ−ợc thảo luận trong các mục sau. An ten thích nghi, phát hiện đồng thời và thích nghi đ−ờng truyền là ba cách tiếp cận có thể đ−ợc sử dụng để triệt xuyên nhiễu. 2.4.1 An ten thích nghi Nếu anten thích nghi đ−ợc sử dụng để triệt xuyên nhiễu, khoảng cách tế bào cho việc sử dụng lại tần số có thể giảm đi và dung l−ợng của mạng đ−ợc tăng lên. Sự triệt xuyên nhiễu thông qua việc sử dụng anten MS có h−ớng tính cao trong các mạng LOS là lý do căn bản dung l−ợng của các mạng này lớn hơn các hệ thống tế bào. ảnh h−ởng này có thể đ−ợc tính một cách xấp xỉ bởi việc thừa nhận tỷ số mục tiêu đ−ợc sử dụng trong (2.11) để xác định các tín hiệu sector nào sẽ xung đột với sector khác bị giảm bởi một l−ợng phản ánh khả năng của anten triệt xuyên nhiễu từ các tế bào khác. Khi tăng giá trị triệt nhiễu này, việc sử dụng lại tần số có thể xếp chặt hơn và theo đó dung l−ợng của hệ thống đ−ợc tăng lên.Ví dụ, nếu một an ten thích nghi làm giảm sự đóng góp xuyên nhiễu đ−ợc biểu diễn qua NI trong (2.11) bởi một hệ số cải thiện anten thích nghi là α = 1/4 (khử xuyên nhiễu 6 dB), sự tăng dung l−ợng từ C đến C’ là: Nếu số mũ suy giảm đ−ờng truyền ở mục tr−ớc đ−ợc sử dụng là n = 4.38, dung l−ợng mạng đ−ợc tăng lên một hệ số là 1.88. Đối với các giá trị nhỏ hơn n, nh− với hệ thống LOS có thể mong đợi sự cải thiện lớn hơn, bởi giới hạn dung l−ợng là phụ thuộc nhiều vào xuyên nhiễu khi tổn thất đ−ờng truyền giữa máy thu và các máy phát xuyên nhiễu trong mạng là thấp hơn. Kết quả mô phỏng trong [9] gồm có ảnh h−ởng của việc tạo chùm tia tại sector và sự triệt xuyên nhiễu từ một anten thích nghi tại MS. Sử dụng các kỹ thuật này, tỷ lệ truyền lại gói giảm xuống một cách đáng kể khi các kỹ thuật nâng cao bổ sung này đ−ợc sử dụng, cho biết sự cải thiện về QoS khi sử dụng anten thích nghi. Điều này là hệ quả trực tiếp của việc triệt xuyên nhiễu. 2.4.2 Phát hiện đồng thời Phát hiện đồng thời đ−ợc sử dụng trong các kênh đ−ờng lên trong hệ thống CDMA. Trong vai trò này, nó có khả năng triệt tất cả các xuyên nhiễu trong tế bào và có khả năng tăng dung l−ợng bởi hệ số là 2.8. Nó cũng giảm nhẹ tải thực hiện điều khiển công suất nhanh và chính xác. Khái niệm phát hiện đồng thời hay phát hiện đa ng−ời sử dụng có thể đ−ợc sử dụng rộng rãi hơn để triệt xuyên nhiễu từ mọi nguồn bên ngoài nếu đã biết về tín hiệu xuyên nhiễu và thông tin trạng thái kênh (CSI) giữa máy xuyên nhiễu và máy thu nạn nhân (bị nhiễu). Thậm chí việc loại trừ xuyên nhiễu không đầy đủ cũng có thể cung cấp độ lợi dung l−ợng tỷ lệ với mức độ triệt nhiễu. Hiện nay, UMTS TDD n CC /2 ' α= (2.14) W- CDMA là công nghệ duy nhất có thể ứng dụng cho mạng băng rộng cố định tế bào bao gồm phát hiện đồng thời là một phần đặc điểm kỹ thuật của nó. 2.4.3 Thích nghi đ−ờng truyền Thích nghi đ−ờng truyền (LA) là một kỹ thuật sửa đổi đặc điểm của tín hiệu (điều chế và mã hoá), mức công suất phát, hay tham số của một anten thích nghi (nếu đ−ợc sử dụng), để duy trì chất l−ợng đ−ờng truyền khi đặc tính của các kênh thay đổi hay giảm đi so với các điều kiện danh định của chúng. Các kỹ thuật nh− thế có thể đ−ợc ứng dụng cho các đ−ờng truyền riêng biệt đơn lẻ sao cho chúng có thể đáp ứng việc thay đổi các điều kiện môi tr−ờng đ−ờng truyền nh− m−a mù, pha- đinh đa đ−ờng... LA cũng có thể đ−ợc ứng dụng cho các đ−ờng truyền trong các mạng LOS và mạng tế bào trong đó xuyên nhiễu là yếu tố hạn chế. Đối với một đ−ờng truyền đã cho trong mạng, LA có thể cho phép CSI hiện thời và SINR đ−ợc khai thác ở mức độ lớn nhất. Nếu SINR cao đã đạt đ−ợc cho một phần của việc truyền dẫn, cách thức có thể đ−ợc thay đổi để sử dụng hiệu quả hơn bộ tín hiệu điều chế có sự chiếm dụng phổ tần thấp hơn. Khả năng này có thể đạt đ−ợc dung l−ợng cao hơn khi sử dụng độc lập DCA. 2.5 Kết luận Gán kênh là một quá trình lựa chọn cách sử dụng tốt nhất nguồn tài nguyên mạng vô tuyến ở dạng tần số, các khe thời gian, và mã hoá để mang l−u l−ợng dữ liệu giữa các nút mạng. Trong khi phần cứng của mạng (các máy phát, các máy thu, các anten...) là công nghệ có thể, giá trị thông tin thêm vào mạng xuất phát từ việc sử dụng hiệu quả nguồn tài nguyên thông qua các chiến l−ợc gán kênh thông minh và linh hoạt. Đối với các hệ thống LOS sử dụng các anten tăng ích cao cố định tại MS và các mức độ hợp lý của việc sector hoá tại các BS với sự phân cực luân phiên, có thể đạt đ−ợc hệ số sử dụng lại tần số bằng một (mỗi tần số có thể đ−ợc sử dụng trên một sector). Anten thích nghi sử dụng trong các hệ thống LOS có thể cải thiện độ dự trữ đ−ờng truyền bằng cách định h−ớng độ khuếch đại tới các MS liên lạc và cung cấp sự linh hoạt để định hình lại mạng khi có thêm ng−ời dùng và BS. Các hệ thống tế bào có thể dùng các chiến l−ợc gán kênh, nh− ph−ơng pháp FCA và DCA sử dụng nguồn tài nguyên mạng để mang l−u l−ợng đến địa điểm và thời gian nó cần. Vài ph−ơng pháp DCA đã đ−ợc đề xuất với sự thoả hiệp chất l−ợng khác nhau chủ yếu là với các hệ thống chuyển mạch- kênh. Đối với các mạng số liệu chuyển mạch gói hiện tại và t−ơng lai, DPA có thể đạt đ−ợc việc sử dụng phổ tần rất hiệu quả trên cơ sở việc mô phỏng mới. Vì dung l−ợng mạng vô tuyến mật độ cao bị hạn chế bởi xuyên nhiễu, dung l−ợng đạt đ−ợc với chiến l−ợc gán kênh bất kỳ có thể đ−ợc tăng lên thông qua nhiều ph−ơng pháp triệt xuyên nhiễu. Anten thích nghi, phát hiện đồng thời, thích nghi đ−ờng truyền là các ph−ơng pháp triệt xuyên nhiễu và cải thiện chất l−ợng đ−ờng truyền riêng lẻ trong sự giảm cấp tạm thời do pha-đinh hay các cụm xuyên nhiễu. Chiến l−ợc gán kênh thực chất là một phần của mục tiêu lớn hơn là tạo và quản lý phổ tần vô tuyến nh− thế nào. Trên thực tế, nguồn phổ tần tự nhiên là hạn chế, phổ tần khả dụng chỉ bị hạn chế bởi trạng thái hiện thời của công nghệ đ−ợc ứng dụng và các ph−ơng pháp cho việc sử dụng nó. Khi công nghệ phát triển và mật độ của các điểm truy nhập vô tuyến cố định đã triển khai tăng c−ờng, phổ tần mới đ−ợc tạo ra. Đây là quan điểm chính xác và có tính xây dựng hơn về việc phổ tần đ−ợc phát triển và sử dụng nh− thế nào so với quan điểm mà các nhà quản lý sử dụng đối với tài nguyên phổ tần hiện thời. Ch−ơng 3 Tối −u hoá gán kênh cố định trong mạng di động tế bào Việc tối −u hoá gán kênh cố định trong mạng di động tế bào là bài toán tối −u NP. Đối với mạng bất kỳ có kích th−ớc hợp lý chỉ có thể nhận đ−ợc các giải pháp gồm tối −u bằng các thuật toán kinh nghiệm. Trong ch−ơng này sáu thuật toán gán kênh đ−ợc xem xét và đ−ợc đánh giá. Đó là tổ hợp của ba chiến l−ợc gán kênh và hai ph−ơng pháp xếp thứ tự tế bào. Kết quả mà chúng ta tìm thấy là (i) thứ tự màu nút của tế bào là ph−ơng pháp xếp thứ tự hiệu quả hơn thứ tự cấp độ nút; (ii) chiến l−ợc vét cạn tần số là phù hợp hơn cho hệ thống với l−u l−ợng đ−ợc phân bố có tính đồng đều không cao; và (iii) kết hợp tần số và chiến l−ợc vét cạn yêu cầu với việc thứ tự lại màu nút là thuật toán hiệu quả nhất. Phạm vi tần số đạt đ−ợc qua việc sử dụng thuật toán đã đề xuất là thấp hơn, điều đó đ−ợc trình bày trong ch−ơng này và trong nhiều tr−ờng hợp là bình đẳng cho các cận d−ới có tính lý thuyết. 3.1 Giới thiệu Vấn đề gán một tập kênh cho mỗi tế bào sao cho hiệu quả nhất về phổ đ−ợc gọi là vấn đề gán kênh. Gán kênh là điều rất quan trọng trong quy hoạch mạng di động tế bào bởi việc gán kênh hiệu quả sẽ tạo ra hiệu quả sử dụng phổ tần có sẵn [6], [12], [13]. Tuy nhiên, vấn đề gán kênh lại thuộc vào lớp các bài toán tối −u tổ hợp [15]. Nói chung, đối với các mạng di động có kích th−ớc hợp lý việc giải quyết bài toán này gần nh− là không thể. Một số cách tiếp cận có tính thực tế đối với vấn đề này đ−ợc đ−a ra trong sách báo. Đó là việc sử dụng cách tiếp cận mang tính lý thuyết của graph truyền thống [26]; cách tiếp cận bằng kỹ thuật ủ mô phỏng [11], cách tiếp cận mạng nơron. Mỗi cách tiếp cận đã đ−a ra đều có những điểm hạn chế riêng. Cách tiếp cận mạng nơron [18], [19] tỏ ra không thích hợp cho việc gán kênh trong vì nó tạo ra những giải pháp nghèo nàn, ngay cả trong các tr−ờng hợp đơn giản. Việc sử dụng kỹ thuật ủ mô phỏng [11] có thể tránh đ−ợc các giải pháp tối thiểu cục bộ nh−ng chi phí thời gian hoạt động là tốn kém. Mặt khác, chất l−ợng giải pháp là rất khó kiểm soát. Việc nghiên cứu tiếp theo h−ớng này là cần thiết. H−ớng tiếp cận theo lý thuyết graph đã đ−ợc nghiên cứu một cách rộng rãi và có rất nhiều kết quả nghiên cứu đã đ−ợc báo cáo. Sau đây, những kết quả quan trọng nhất sẽ đ−ợc tổng kết. Dựa trên kinh nghiệm của việc gán kênh tr−ớc tiên cho tế bào có độ khó gán cao nhất. Trong [6] đã đề xuất một thuật toán lặp với một nhóm ban đầu của các con số đ−ợc tạo ra một cách ngẫu nhiên để biểu diễn những khó khăn trong việc gán kênh của các tế bào riêng lẻ. Thuật toán này có một tốc độ hội tụ chậm và thời gian cho việc chạy thử cao đặc biệt khi kích th−ớc hệ thống lớn. Trong [12] chỉ tiêu theo kinh nghiệm về độ khó gán kênh đã đ−ợc đề xuất và các tế bào đ−ợc sắp xếp thành danh sách theo thứ tự màu nút hoặc thứ tự cấp độ nút. Dựa trên danh sách đó, các kênh đã đ−ợc gán bởi hoặc chiến l−ợc vét cạn tần số (F) hay chiến l−ợc vét cạn yêu cầu (R). Tiếp theo, trong [26], chỉ tiêu kinh nghiệm cải tiến về độ khó khăn trong việc gán kênh đã đ−ợc đề cập và ph−ơng pháp sắp xếp tế bào mới đ−ợc gọi là sắp xếp tế bào theo cột đã đ−ợc giới thiệu. Ng−ời ta chứng minh rằng các thuật toán đã đề xuất trong [26] cho chất l−ợng tốt nhất so với tất cả thuật toán hiện có trên các ví dụ thử nghiệm 21 tế bào. Vì thuật toán kinh nghiệm không đ−a ra thông tin về chất l−ợng của giải pháp, các cận d−ới trong vấn đề gán kênh đã nhận đ−ợc trong [13] bằng xem xét mạng nhỏ đ−ợc tách riêng ra khỏi hệ thống nguyên thuỷ. Gần đây, cận d−ới chặt hơn trong một số điều kiện nhất định đã đ−ợc đ−a ra ở [27], [28]. Hai thuật toán dựa trên việc tiếp cận tô màu graph cũng đã đ−ợc đề xuất. Trong ch−ơng 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. Không giống cách tiếp cận thông th−ờng, các tế bào đ−ợc sắp xếp lại sau mỗi gán kênh theo độ phức tạp sắp xếp đ−ợc chỉnh sửa của chúng. 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. Hiệu quả của các thuật toán này đã đ−ợc nghiên cứu và so sánh với các kết quả đã đ−ợc xem xét ở phần tr−ớc cũng nh− cận d−ới lý thuyết cũng đ−ợc đánh giá. Chúng ta nhận thấy rằng (i) thứ tự màu nút là một ph−ơng pháp sắp xếp có hiệu quả hơn là thứ tự cấp độ nút; (ii) chiến l−ợc vét cạn tần số thích hợp hơn cho các hệ thống với l−u l−ợng đ−ợc phân bố có tính đồng đều không cao, và chiến l−ợc vét cạn yêu cầu là phù hợp hơn cho hệ thống với l−u l−ợng đ−ợc phân bố đồng đều hơn và (iii) chiến l−ợc FR với thứ tự lại màu nút hay là các thuật toán FR/CR là thuật toán hiệu quả nhất. Phạm vi tần số tìm đ−ợc bằng các thuật toán của chúng ta là nhỏ hơn đáng kể phạm vi tìm đ−ợc bởi các thuật toán trong [26] và bằng hoặc rất gần các cận d−ới lý thuyết. Trong mục sau, vấn đề gán kênh sẽ đ−ợc trình bày chi tiết và mục đích của chúng ta sẽ đ−ợc làm rõ. Trong mục 3.3, chúng ta nhìn lại vài kinh nghiệm cơ bản trong việc gán kênh. Trong mục 3.4 các thuật toán F/CR, F/DR, R/CR, R/DR sẽ đ−ợc trình bày. Chiến l−ợc FR là sự kết hợp giữa chiến l−ợc vét cạn yêu cầu và chiến l−ợc vét cạn tần số, sau đó sẽ đ−ợc nghiên cứu trong mục 3.5. Trong mục 3.6, chất l−ợng 6 thuật toán gán kênh đ−ợc đề xuất sẽ đ−ợc đánh giá và so sánh với các thuật toán đã đ−ợc đề cập trong [26]. Cuối cùng, kết luận sẽ đ−ợc rút ra ở mục 3.7. 3.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 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. ? Hình 3.1 Gán kênh cố định trong hệ thống di động tế bào 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, Kênh 1 2 3 4 5 x Mhz y Mhz Phổ tần 2, 3…} theo tần số sóng mang của chúng (hình 3.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 [12] 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. Tốc độ l−u l−ợng trong một mạng tế bào biến đổi từ tế bào này tới tế bào khác. Các vùng với tỷ lệ l−u l−ợng cao hơn đáng kể đ−ợc gọi là điểm nóng. Thông th−ờng, một điểm nóng bao gồm một vài tế bào gây xuyên nhiễu với mỗi tế bào có một đòi hỏi kênh cao. Các tế bào bên trong điểm nóng đ−ợc gọi là các tế bào điểm nóng. Phạm vi tần số của hệ thống th−ờng quyết định đ−ợc bởi phạm vi điểm nóng “nóng nhất”. Phạm vi điểm nóng phụ thuộc vào kênh đ−ợc gán cho các tế bào điểm nóng của nó nh− thế nào. Nói cách khác, nếu các kênh đ−ợc gán cho các tế bào điểm nóng (thuộc cùng điểm nóng) đ−ợc đóng gói một cách hiệu quả, một phạm vi tần số nhỏ cho tất cả các hệ thống cũng có thể đạt đ−ợc. Do đó, thuật toán gán kênh hiệu quả sẽ tập trung vào việc thoả mãn những yêu cầu của mỗi nhóm tế bào điểm nóng. Nhiều nghiên cứu tr−ớc đó [12], [26], [30] tập trung tr−ớc tiên vào việc gán kênh cho tế bào có độ khó gán kênh cao nhất. Các chỉ tiêu kinh nghiệm về những khó khăn trong việc gán kênh đã đ−ợc xác định và sau đó các tế bào đã đ−ợc sắp xếp vào một danh sách. Các kênh đ−ợc gán dựa trên danh sách. Chúng ta tìm ra hai vấn đề đối với việc tiếp cận này. Vấn đề đầu tiên liên quan đến trật tự của tế bào. Khi các kênh đ−ợc gán cho tế bào, độ khó của sắp xếp tế bào riêng lẻ thay đổi. Do đó cần sắp xếp lại các tế bào sau mỗi lần gán kênh. Vấn đề thứ hai là trong cách tiếp cận này chỉ tập trung vào việc gán kênh cho các tế bào có độ khó gán kênh cao nhất. Có thể không nhận dạng đ−ợc các khu vực điểm nóng và bởi vậy có thể dẫn đến việc chỉ định kênh không hiệu quả khi mà các tế bào liên tiếp trong danh sách đã đ−ợc sắp xếp không thuộc cùng một điểm nóng. 3.3 Những quy tắc kinh nghiệm cơ bản 3.3.1 Hai ph−ơng pháp sắp xếp tế bào Gọi di là một số đo độ khó gán kênh cho tế bào i. Trong [26], di đ−ợc định nghĩa: nếu mi ≠ 0; ngoài ra, di = 0. Vì số hạng cii ở vế phải của ph−ơng trình (3.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: Sử dụng thứ tự cấp độ nút [30], các tế bào đ−ợc sắp xếp theo trật tự giảm dần giá trị di. Bởi vậy, tế bào đầu tiên có −u tiên cao nhất cho việc đạt đ−ợc một kênh đầu tiên. Sử dụng thứ tự màu nút [30], các tế bào đầu tiên đ−ợc sắp xếp bởi thứ tự cấp độ nút. Tế bào cuối cùng trong danh sách đ−ợc di chuyển đến danh sách rỗng ví dụ danh sách A. Bậc của (N-1) tế bào còn lại đ−ợc tính toán lại với yêu cầu kênh của tế bào cuối cùng bị loại trừ. (N-1) tế bào còn lại sau đó đ−ợc thứ tự lại bởi cấp độ nút của chúng đã đ−ợc sửa. Sau đó, di chuyển tế bào cuối cùng trong danh sách rút gọn đến danh sách A và đặt nó ngay tr−ớc các tế bào đã liệt kê. Thủ tục này tiếp tục cho đến khi tất cả N tế bào đ−ợc di chuyển đến danh sách A. Điều này đ−ợc biết đến nh− là thứ tự màu nút. Hai ph−ơng pháp sắp xếp tế bào ở trên đã đ−ợc sử dụng rộng rãi khi thiết kế các thuật toán kinh nghiệm. Tuy nhiên ch−a biết rõ ph−ơng Niccmd N j iiijji ≤≤−= ∑ = 1 1 (3.1) Nicmd N j ijji ≤≤= ∑ = 1 1 (3.2) pháp nào có chất l−ợng tốt hơn. Trong mục 3.6, hiệu quả của hai ph−ơng pháp sắp xếp tế bào sẽ đ−ợc nghiên cứu. 3.3.2 Hai chiến l−ợc gán kênh Cho danh sách theo thứ tự của các tế bào (đã nhận đ−ợc bởi thứ tự cấp độ nút hoặc thứ tự màu nút), 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) [30] 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 (đ−ợc vét cạn). 3.4 Gán kênh với việc sắp xếp lại tế bào 3.4.1 Bốn thuật toán gán kênh Mục đích của sắp xếp các tế bào là nhận dạng các tế bào khó gán kênh nhất. Khi các kênh đ−ợc gán cho tế bào, yêu cầu kênh của tế bào giảm đi và độ khó gán kênh của nó cũng nh− của các tế bào lân cận nó cũng giảm. Để phản ánh thực chất độ khó việc gán kênh tức thời, danh sách sắp xếp nên đ−ợc sắp xếp lại tr−ớc khi gán kênh kế tiếp. Dựa trên hai nguyên lý sắp xếp tế bào cơ bản, 2 ph−ơng pháp sắp xếp lại tế bào, cụ thể là sắp xếp lại màu nút (CR) và sắp xếp lại cấp độ nút (DR) đ−ợc thiết kế. Kết hợp mỗi ph−ơng pháp này với chiến l−ợc vét cạn tần số và chiến l−ợc vét cạn yêu cầu, ta có bốn thuật toán cụ thể là F/CR, F/DR, R/CR và R/DR. Chúng đ−ợc miêu tả theo mã giả ngẫu nhiên. * 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 độ 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ự cấp độ 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. 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. 3.4.2 Độ phức tạp Giả sử tổng số yêu cầu kênh là M = ∑Ni=1 mi. Với các thuật toán F/CR hay F/DR, b−ớc 2 bao gồm N thao tác cho việc tìm di. Giả thiết sự phân loại ảo đ−ợc sử dụng, số thao tác trong b−ớc 3 đối với sắp xếp màu nút là O(N3) và cho sắp xếp cấp độ nút là O(N2). B−ớc 2 đến 4 tạo thành một chu trình và sẽ thực hiện M lần. Tổng số sự so sánh cho thực hiện M lần của b−ớc 4 là 1+2+…+M-1, hay O(M2). Do đó, sự phức tạp thời gian toàn bộ của thuật toán F/CR là MO(N3) + O(M2) = O(MN3+M2). Sự phức tạp thời gian toàn bộ của thuật toán F/DR là O(MN2 + M2). Với các thuật toán R/CR hay R/DR, b−ớc 3 đến 7 thực hiện M lần để gán M kênh. T−ơng tự với thuật toán F/CR và F/DR, sự phức tạp thời gian của b−ớc 4 là O(N3) nếu thứ tự màu nút đ−ợc sử dụng và O(N2) nếu thứ tự cấp độ nút đ−ợc sử dụng. Tổng số sự so sánh cho thực hiện M lần của b−ớc 5 là O(M2). Sự phức tạp thời gian tổng cộng tìm đ−ợc là O(MN3+M2) cho R/CR và O(MN2+M2) cho R/DR. 3.4.3 Ví dụ Để chứng minh cho hiệu quả sử dụng sắp xếp lại tế bào, xem xét hệ thống 3 tế bào đơn giản chỉ ra trong hình 3.2(a). Tế bào A, B và C có yêu cầu kênh 4, 3 và 1 t−ơng ứng. Giả sử hạn chế xuyên nhiễu kênh lân cận và hạn chế xuyên nhiễu kênh cùng trạm là a = 2 và s = 3. Bậc của các tế bào A, B và C đ−ợc tìm thấy là 20, 19 và 14 từ ph−ơng trình (3.2). Với ví dụ cụ thể này, điều đó chứng tỏ rằng 4 thuật toán đã đề xuất trong phần tr−ớc thực hiện nh− nhau. Do đó, để thuận tiện chúng ta sẽ sử dụng “sắp xếp lại tế bào” và “không sắp xếp lại tế bào” để phân biệt hai loại gán kênh này. 4 3 1 A B C (a) Hệ thống 3 tế bào A, B, C Thứ tự 1 2 3 4 5 6 7 8 A A A A B B B C Tế bào Kênh 1 3 5 7 9 11 13 15 17 19 21 Phạm vi (b) Không sắp xếp lại tế bào Thứ tự 1 2 3 4 5 6 7 8 A A B B A A B C Tế bào Kênh 1 3 5 7 9 11 13 15 17 19 21 Phạm vi (c) Có sắp xếp lại tế bào và ph−ơng pháp quyết định thứ nhất Thứ tự 1 2 3 4 5 6 7 8 A B A B A C B A Tế bào Kênh 1 3 5 7 9 11 13 15 17 19 21 Phạm vi (d) Có sắp xếp lại tế bào và ph−ơng pháp quyết định thứ hai Hình 3.2 Kế hoạch gán kênh cho hệ thống 3 tế bào Đối với việc gán kênh không sắp xếp lại, danh sách tế bào đã đ−ợc sắp xếp ban đầu (A, B, C) đ−ợc sử dụng cho đến khi tất cả các yêu cầu kênh đ−ợc thoả mãn. Kết quả kế hoạch gán kênh đ−ợc chỉ ra trong hình 3.2(b). Trật tự gán kênh cũng đ−ợc chỉ ra trong hình. Phạm vi tần số đ−ợc tìm thấy là 20. Khi việc gán kênh với sắp xếp lại tế bào đ−ợc sử dụng, danh sách đã đ−ợc sắp xếp lại của tế bào đ−ợc cập nhật mỗi khi 1 kênh đ−ợc gán. Trong tr−ờng hợp có hơn 1 tế bào có cùng độ khó gán kênh, 2 ph−ơng pháp quyết định đ−ợc sử dụng: (1) Lựa chọn tế bào mà một kênh đ−ợc gán sớm nhất hoặc (2) ng−ợc lại. (Chú ý rằng bất kỳ ph−ơng pháp quyết định nào cũng có thể đ−ợc sử dụng). Khi sử dụng ph−ơng pháp quyết định thứ nhất, kết quả kế hoạch gán kênh đ−ợc chỉ ra trong hình 3.2(c) và chuỗi danh sách sắp xếp đ−ợc sử dụng là (A, B, C) → (A, B, C) → (B, A, C) → (B, A, C) → (A, B, C) → (A, B, C) → ( B, C, A) → (C, B, A). Phạm vi tần số là 18. Sử dụng ph−ơng pháp quyết định thứ 2, chuỗi trật tự danh sách đ−ợc sử dụng là: (A, B, C) → (B, A, C) → (A, B,C) → (B, A, C) → (A, C, B) → (C, B, A) → (B, A, C) → (A, B, C) và phạm vi tần số là 15 nh− đ−ợc biểu diễn ở hình 3.2(d). Có thể thấy phạm vi tần số 15 là tối −u cho ví dụ này. Tóm lại, phạm vi tần số giảm từ 20 đến 15 với việc sử dụng sắp xếp lại tế bào. 3.5 Tối −u việc gán kênh tại các điểm nóng Nh− đã đề cập ở phần giới thiệu, ph−ơng pháp gán kênh theo kinh nghiệm có hai vấn đề. Trong mục tr−ớc, chúng ta đã giải quyết vấn đề thứ nhất bằng sự sắp xếp lại các tế bào tr−ớc khi gán kênh kế tiếp. Trong mục này, chúng ta tập trung vào vấn đề thứ 2: hiệu quả việc gán kênh cho điểm nóng. Thông th−ờng, một điểm nóng bao gồm một số tế bào điểm nóng và phạm vi tần số điểm nóng phụ thuộc vào các kênh đ−ợc gán cho tế bào điểm nóng của chúng nh− thế nào. Tập trung vào tối −u việc gán kênh tại điểm nóng, một chiến l−ợc mới đ−ợc gọi là vét cạn tần số kết hợp và chiến l−ợc vét cạn yêu cầu (FR) đã đ−ợc đề xuất. Chiến l−ợc FR có thể kết hợp với 2 ph−ơng pháp sắp xếp lại tế bào để tạo ra hai thuật toán gán kênh FR/CR và FR/DR. Tr−ớc khi tiếp tục, ta xét kĩ hơn 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.5.1 Chiến l−ợc F và chiến l−ợc R - Nhận xét đầu tiên của chúng ta 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. Nếu chiến l−ợc F đ−ợc sử dụng, gán kênh f cho tế bào cần phải kiểm tra các ràng buộc đã gây bởi việc gán kênh từ (f-s+1) đến (f+s-1). Số kênh đ−ợc kiểm tra gần nh− hai lần so với trong chiến l−ợc R. Kết quả là, kênh f có xác suất bị từ chối bởi một tế bào là cao hơn. Kết quả này không chặt trong mối quan hệ tế bào đồng kênh của 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ể (chẳng hạn các tế bào với các yêu cầu không thoả mãn và không vi phạm bất kỳ sự ràng buộc gán kênh nào), 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. Xét một ví dụ đơn giản, giả sử khi kênh 1 đ−ợc gán cho tế bào đầu tiên trong danh sách đã đ−ợc sắp xếp, tế bào đầu tiên vẫn là tế bào khó khăn gán kênh nhất sau khi sắp xếp lại tế bào. Vì cùng một kênh, chẳng hạn kênh 1, không thể đ−ợc gán hai lần cho cùng một tế bào. Do đó việc gán kênh kế tiếp là gán kênh 1 cho tế bào khác, tế bào này không phải là khó nhất cho việc gán kênh. Trái lại, chiến l−ợc F không có vấn đề này. Từ hai nhận xét trên, chúng ta có thể thấy rằng các hệ thống với những thay đổi nhỏ trong những yêu cầu kênh từ tế bào này đến tế bào khác (hoặc những yêu cầu kênh phân bố không đồng đều ít hơn), tối đa hoá số tế bào đồng kênh là quan trọng hơn. Bởi vậy, chiến l−ợc R h−ớng tới cho một chất l−ợng tốt hơn. Các hệ thống với những yêu cầu kênh phân bố không đồng đều cao, điều đó là rất quan trọng để thoả mãn các yêu cầu kênh của các tế bào đầu tiên khó khăn nhất cho việc gán kênh. Do đó, chiến l−ợc F h−ớng tới hoạt động tốt hơn. 3.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 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. Rất khó khăn để có một quy tắc về ng−ỡng để xác định tế bào xuyên nhiễu nào của tế bào i thuộc vào cùng điểm nóng và tế bào xuyên nhiễu nào không thuộc cùng điểm nóng. Chúng ta dùng ph−ơng pháp kinh nghiệm bằng cách xác định rằng điểm nóng i chứa các tế bào nằm trong phạm vi nhiễu của tế bào i và có yêu cầu kênh t−ơng đối cao. Để đơ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. Chú ý rằng đây chỉ là một ph−ơng pháp kinh nghiệm để nhận dạng điểm nóng. Ph−ơng pháp này thật đơn giản nh−ng không tối −u, ngoài ra còn có nhiều ph−ơng pháp khác nữa. Ngay khi điểm nóng ở tế bào i đ−ợc nhận dạng sử dụng ph−ơng pháp trên, gán kênh toàn bộ mở rộng để thực hiện gán cục bộ. Gán cục bộ sử dụng chiến l−ợc F để gán các kênh cho tế bào điểm nóng của điểm nóng i (nh−ng không bao gồm tế bào i). 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 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ó trật tự sử dụng thứ tự màu nút hoặc thứ tự cấp độ 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 ; ng−ợc lại 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ự cấp độ 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ộ. Các giá trị tối −u của X và Y sao cho phạm vi tần số của hệ thống là cực tiểu hoá rất khó khăn để đạt đ−ợc. Thực tế, các giá trị tối −u nên đ−ợc điều chỉnh sau mỗi việc gán kênh ngay khi thực hiện sắp xếp lại tế bào. Để đơn giản, ta giả thiết giá trị của X và Y trong luận văn nà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. Có thể thấy rằng các thuật toán FR/CR và FR/DR có cùng sự phức tạp về thời gian nh− của F/CR và F/DR, nghĩa là O (MN3 + M2) cho FR/CR và O(MN2+ M2) cho FR/DR. Đó là vì việc gán cục bộ chỉ có độ phức tạp O(M + N). 3.6 Đánh giá chất l−ợng Ta sử dụng các ví dụ dùng 21 tế bào nh− trong [13], [26] cho việc đánh giá chất l−ợng. Để dễ so sánh, các cận d−ới gán kênh lý thuyết cho hệ thống này đã đ−ợc đ−a ra [13], [27]. Hình 3.3 chỉ ra 2 tr−ờng hợp yêu cầu kênh. Số kênh biểu diễn trong mỗi tế bào là yêu cầu kênh của tế bào đó. Các tế bào đ−ợc đánh số từ 1 ữ 21 theo trật tự từ trái sang phải và từ trên xuống d−ới. Trong ch−ơng trình của chúng ta, khi thứ tự cấp độ nút đ−ợc sử dụng, tế bào với số tế bào nhỏ nhất đ−ợc lựa chọn đầu tiên. Khi thứ tự màu nút đ−ợc sử dụng, tế bào với số tế bào lớn nhất đ−ợc lựa chọn đầu tiên. Giả sử bộ ba có thứ tự (Nc, a, s) biểu thị hệ thống với nhóm kích th−ớc Nc, ràng buộc kênh lân cận a và ràng buộc kênh đồng site s. Kết quả gán kênh đ−ợc tóm tắt trong các bảng 3.1, 3.2, 3.3. 8 25 8 28 8 18 77 52 8 13 15 57 15 15 813 10 31 36 28 8 (a) Yêu cầu kênh tr−ờng hợp I 5 5 5 40 12 30 3025 8 40 45 15 30 25 252020 20 25 15 30 (b) Yêu cầu kênh tr−ờng hợp II Hình 3.3 Mạng 21 tế bào với 2 tr−ờng hợp yêu cầu kênh Cột SMK t−ơng ứng với kích th−ớc phạm vi tần số đạt đ−ợc từ 8 thuật toán trong [26]. Cột LB t−ơng ứng với cận d−ới có tính lý thuyết trong [13], [27]. Những cận d−ới này đã có đ−ợc bởi sự xem xét tách riêng ra mạng con của hệ thống nguyên thuỷ. Cần chú ý rằng ta không biết đ−ờng biên xếp khít nhau nh− thế nào. Bảng 3.1 Phạm vi tần số nhận đ−ợc bởi F/CR, F/DR, R/CR và R/DR Tr−ờng hợp Cấu hình mạng LB F/CR F/DR R/CR R/DR SMK I I I I I I (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 427 427 427 427 533 533 435 433 431 432 533 533 472 475 448 476 533 533 427 442 489 468 568 557 431 439 481 496 568 557 436-554 442-554 460-543 447-543 536-565 533-566 II II II II II II (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 258 253 258 258 309 309 286 265 293 264 309 309 339 309 289 269 315 315 262 263 267 264 318 325 278 271 291 277 321 337 272-327 265-340 283-360 269-347 310-384 310-358 Bảng 3.2 Phạm vi tần số nhận đ−ợc bởi FR/CR và FR/DR với (7,2,5) và yêu cầu kênh tr−ờng hợp I Thuật toán Y X = 1 X =2 X =3 X = 4 X = 5 FR/CR Y = 1 Y = 2 Y = 3 488 485 487 450 459 466 446 428 445 445 437 438 446 433 437 FR/DR Y = 1 Y = 2 Y = 3 508 491 493 451 462 472 457 438 446 456 453 448 458 441 444 Bảng 3.3 Phạm vi tần số nhận đ−ợc bởi FR/CR và FR/DR với 0 ≤ X ≤ 5 và1 ≤ Y ≤ 3 Tr−ờng hợp Cấu hình mạng LB FR/CR FR/DR SMK I I I I I I (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 427 427 427 427 533 533 427 (0,Y) (1,1)-(1,3) 430 (1,3) 428 (3,2) (4,2) (5,3) 428 (3,2) 533 (3,1)-(5,1) (3,2) (5,2) (3,3) 533 (3,1)-(5,1) 427 (1,2) (1,3) 428 (1,3) 431 (5,2) (3,3) 438 (3,2) 533 (2,1)-(5,1) 533 (3,1)-(5,1) 436-554 442-554 460-543 447-543 536-565 533-566 II II II II II II (12,2,3) (7,2,3) (12,2,5) (7,2,5) (12,2,7) (7,2,7) 258 253 258 258 309 309 262 (0,Y) 257 (1,3) 263 (1,2) 263 (2,2) (4,3) 310 (4,1) (5,1) 309 (5,2) 278 (0,Y) 265 (1,2) 272 (2,3) 262 (1,3) 316 (1,1) (4,3) 320 (3,1) 272-327 265-340 283-360 269-347 310-384 310-358 3.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, bảng 3.1 tóm tắt 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. Phạm vi tối thiểu tìm thấy trong mỗi hàng đ−ợc gạch chân. Từ bảng này chúng ta có thể thấy các thuật toán 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ự cấp độ nút. Tuy nhiên, khuynh h−ớng nh− vậy không thể hiện rõ đối với các thuật toán R/CR và R/DR. Điều này có nguyên nhân là các kênh đ−ợc gán không theo chính xác độ khó gán kênh khi sử dụng chiến l−ợc R (xem phần 3.5.1). Nh− chúng ta đã dự đoán trong phần 3.5.1, thuật toán F/CR thực hiện tốt hơn trong tr−ờng hợp I với những yêu cầu kênh (thuật toán đ−ợc phân bố một cách không đồng đều) và thuật toán R/CR thực hiện tốt hơn trong tr−ờng hợp II với những yêu cầu kênh (thuật toán đ−ợc phân bố khá đồng đều). Đối với mỗi tr−ờng hợp nghiên cứu, phạm vi tối thiểu tìm thấy bởi các thuật toán là thấp hơn nhiều điều tìm đ−ợc bởi thuật toán trong [26]. Ví dụ, đối với yêu cầu kênh tr−ờng hợp I và cấu hình mạng (12, 2, 5), phạm vi tối thiểu chúng ta tìm đ−ợc là 431 và bởi thuật toán trong [26] là 460. 3.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. Bảng 3.2 chỉ ra 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 [26] chỉ là 447 và trong [7] chỉ là 446. 3.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. Bảng 3.3 tóm tắt phạm vi tối thiểu tìm đ−ợc bởi các thuật toán FR/CR và FR/DR. Cặp thứ tự (X, Y) đã chỉ ra trong bảng biểu thị giá trị từ đó tìm ra phạm vi tần số. (0, Y) có nghĩa Y có thể là bất kỳ giá trị nào. Phạm vi tối thiểu của mỗi hàng trong bảng đ−ợc gạch chân, phạm vi 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 [26]. 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 trong bảng 3.1, 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. Tóm lại, đối với các yêu cầu của chúng ta kênh tr−ờng hợp I những phạm vi thấp nhất tìm đ−ợc bởi các thuật toán chỉ cao hơn cận d−ới lý thuyết nhiều nhất là một kênh. Đối với yêu cầu kênh tr−ờng hợp II, phạm vi thấp nhất tìm ra bằng các thuật toán của chúng ta cao hơn cận d−ới lý thuyết nhiều nhất là 5 kênh. 3.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 luận văn 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à sáu thuật toán gán kênh mới là những sự kết hợp của ba chiến l−ợc gán kênh và hai ph−ơng pháp sắp xếp lại tế bào đã đ−ợc đề cập và nghiên cứu. Vấn đề chúng ta đã tìm ra là: (i) thứ tự màu nút của các tế bào là một ph−ơng pháp thứ tự hiệu quả hơn thứ tự cấp độ nút; (ii) chiến l−ợc R phù hợp hơn cho hệ thống với l−u l−ợng phân bố không đồng đều cao và chiến l−ợc F thì phù hợp hơn cho hệ thống với l−u l−ợng phân bố không đồng đều thấp hơn và (iii) thuật toán FR/CR là thuật toán hiệu quả nhất cho giá trị phạm vi tần số thấp nhất trong hầu hết các tr−ờng hợp. Bên cạnh đó, phạm vi thấp nhất tìm ra bởi các thuật toán của chúng ta thì thấp hơn nhiều bởi các thuật toán đã đ−ợc báo cáo trong sách báo và trong nhiều tr−ờng hợp bằng với các cận d−ới lý thuyết. 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 luận văn 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ẽ. Kết luận Sau một thời gian tìm hiểu, nghiên cứu với sự h−ớng dẫn giúp đỡ tận tình của Thầy giáo - T.S Đỗ Quốc Trinh, cùng với sự cố gắng