Tóm tắt luận án Nghiên cứu cải tiến hiệu suất cấp phát kênh tần số mạng di động tế bào

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ĐỖ HỮU TRÍ NGHIÊN CỨU CẢI TIẾN HIỆU SUẤT CẤP PHÁT KÊNH TẦN SỐ MẠNG DI ĐỘNG TẾ BÀO Chuyên ngành: Kỹ thuật máy tính Mã số: 62.52.70.10 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI - NĂM 2012 Công trình được hoàn thành tại Học viện Công nghệ Bưu chính Viễn thông Người hướng dẫn khoa học: 1. PGS.TS. Vũ Duy Lợi 2. TS. Bùi Thiện Minh Phản biện 1: PGS.TS. Nguyễn Quốc Bình Phản biện 2: PGS.TS. Nguyễn Đình Việt Phản biện 3: TS. Nguyễn Phạm Anh Dũng Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Học viện họp tại Học viện Công nghệ Bưu chính Viễn thông Vào hồi 14 giờ ngày 24 tháng 8 năm 2012 Có thể tìm hiểu luận án tại các thư viện: - Thư viện Quốc gia - Thư viện Học viện Công nghệ Bưu chính Viễn thông 1 NGHIÊN CỨU CẢI TIẾN HIỆU SUẤT CẤP PHÁT KÊNH TẦN SỐ MẠNG DI ĐỘNG TẾ BÀO I. ĐẶT VẤN ĐỀ Một trong những xu hướng phát triển của ngành công nghiệp máy tính là tính di động ngày càng tăng. Cùng với kích cỡ được thu nhỏ, nhiều máy tính cầm tay đã có tốc độ mạnh bằng hoặc hơn các máy tính để bàn. Người sử dụng có khả năng thiết lập và duy trì một phiên liên lạc giữa máy tính với máy tính khi di chuyển từ nơi này sang nơi khác. Với việc tích hợp công nghệ thoại và thông tin số liệu máy tính ngày nay càng thân thiện với người sử dụng và được coi là thiết bị di động hoàn hảo, chủ chốt trong bất kỳ mạng không dây nào. Cùng với sự phát triển không ngừng của các hệ thống thông tin di động, việc liên lạc của các phần tử mạng với nhau thông qua môi trường truyền dẫn vô tuyến đặt ra nhiều bài toán phải giải quyết, trong đó quan trọng nhất là vấn đề sử dụng môi trường này như thế nào để đạt hiệu quả cao nhất. Trước những yêu cầu ngày càng cao của người sử dụng dịch vụ về chất lượng, dung lượng, tính đa dạng của dịch vụ, tốc độ truyền dữ liệu, … việc nghiên cứu, ứng dụng các công nghệ và kỹ thuật tiên tiến luôn là những đòi hỏi cấp thiết. Nhằm làm tăng dung lượng mạng, nhiều kỹ thuật khác nhau đã được sử dụng như chia nhỏ mạng thành tế bào, chỉ định phổ tần mới, các thuật toán đa truy nhập, gán kênh động,…Đặc biệt, trong điều kiện nguồn tài nguyên vô tuyến cấp cho mỗi mạng là hữu hạn, vấn đề cấp phát các kênh tần số là một trong những yếu tố quan trọng có ảnh hưởng tới dung lượng và hiệu suất hoạt động của mạng. Các công trình nghiên cứu trước đây đã đưa ra nhiều thuật toán cấp phát kênh nhằm làm tối đa khả năng tái sử dụng đồng thời giảm tới mức thấp nhất khả năng khoá kênh. Việc tiếp tục nghiên cứu, phát triển các thuật toán cấp phát kênh nhằm đảm bảo kênh tần số được sử dụng hiệu quả, đáp ứng các dịch vụ đa phương tiện ngày càng đa dạng đang thực sự là vấn đề cấp thiết. II. MỤC TIÊU LUẬN ÁN Mục tiêu của luận án là nghiên cứu cải tiến, nâng cao hiệu suất hoạt động của các thuật toán cấp phát kênh tần số trong mạng di động tế bào. Cụ thể là: - Nghiên cứu, hệ thống hóa, phân loại các thuật toán cấp phát kênh tần số trong mạng di động tế bào; phân tích, so sánh, đánh giá ưu, nhược điểm của các thuật toán. - Nghiên cứu sâu thuật toán cân bằng tải động sử dụng mượn kênh chọn lọc và thuật toán cấp phát kênh thích nghi trong mạng di động tế bào; phân tích, đánh giá hiệu quả hoạt động của các thuật toán trên để từ đó đề xuất một số điểm cải tiến nhằm tái sử dụng nguồn tài nguyên một cách hiệu quả. 2 - Đề xuất một số cải tiến trong thuật toán cân bằng tải động sử dụng mượn kênh chọn lọc và thuật toán cấp phát kênh thích nghi; thực hiện mô phỏng, kiểm chứng, đánh giá hiệu quả hoạt động của các đề xuất bằng chương trình máy tính. III. PHƯƠNG PHÁP NGHIÊN CỨU Phương pháp nghiên cứu ở đây là kết hợp nhuần nhuyễn giữa nghiên cứu lý thuyết về kiến trúc, nguyên tắc hoạt động cũng như cơ chế cấp phát kênh tần số của mạng di động tế bào với việc mô phỏng bằng chương trình máy tính để kiểm chứng, đánh giá hiệu quả hoạt động của các đề xuất, cải tiến cấp phát kênh tần số trong mạng di động tế bào. IV. ĐÓNG GÓP CỦA LUẬN ÁN 1- Hệ thống hóa, phân loại các thuật toán cấp phát kênh trong mạng di động tế bào; phân tích, đánh giá, so sánh ưu nhược điểm của các thuật toán. 2- Cải tiến thuật toán cân bằng tải động với mượn kênh chọn lọc và thuật toán gán kênh thích nghi ở những nội dung sau đây: 2.1 - Xây dựng phương pháp cấu hình nhóm compact của một ô có nhu cầu mượn kênh, đặc biệt là trong các trường hợp có ô ở tâm của mỗi nhóm, ở biên của mạng và ở biên của hai nhóm và ở biên của nhiều nhóm compact. 2.2 - Nghiên cứu, xác định số lượng kênh mà một ô có nhu cầu cần mượn (X) và mối quan hệ giữa số kênh có thể mượn được và số kênh cần khóa ở ô đồng kênh. 2.3 - Nghiên cứu, xác định số lượng kênh có thể cho mượn (Y) và điều kiện cần thỏa mãn khi cho mượn Y kênh. 2.4 - Nghiên cứu để xác định chính xác toạ độ ô phải khóa đồng kênh khi một ô cho mượn kênh; giá trị ngưỡng lạnh được tính toán lại sau mỗi lần khoá đồng kênh góp phần làm tăng số lượng kênh của một ô có thể cho mượn. 2.5 - Nghiên cứu, xác định thứ tự ưu tiên khi cho mượn kênh để tăng số lượng kênh có thể cho mượn và giảm độ phức tạp của thuật toán 2.6 - Mở rộng khả năng tham gia cấp phát kênh của các ô lân cận của một ô có nhu cầu cấp phát kênh. 3- Thực hiện mô phỏng bằng chương trình máy tính để kiểm chứng thuật toán cải tiến, ưu việt hơn so với thuật toán cân bằng tải động với mượn kênh chọn lọc và thuật toán gán kênh thích nghi. V. BỐ CỤC LUẬN ÁN Ngoài phần Mở đầu và Kết luận, luận án gồm 5 chương. Chương 1 giới thiệu tổng quan về mạng tế bào: sự phát triển, khái niệm tế bào và cấp phát, sử dụng kênh trong mạng tế bào, tái sử dụng kênh và đánh giá hiệu suất của các thuật toán cấp phát kênh. Chương 2 trình bày một cách hệ thống về các thuật toán cấp phát kênh, bao gồm: phân loại các thuật toán 3 cấp phát kênh (cấp phát kênh cố định, cấp phát kênh động, cấp phát kênh lai); đánh giá, so sánh ưu nhược điểm của các thuật toán. Chương 3 trình bày chi tiết thuật toán cân bằng tải động với mượn kênh chọn lọc và thuật toán cấp phát kênh thích nghi; đánh giá, so sánh ưu nhược điểm của các thuật toán; từ đó đề xuất một số nội dung cụ thể cần cải tiến. Chương 4 đề xuất thuật toán cấp phát kênh tần số mới trên cơ sở cải tiến thuật toán cân bằng tải động với mượn kênh chọn lọc và thuật toán cấp phát kênh thích nghi. Chương 5 trình bày chương trình máy tính và kết quả mô phỏng các nội dung cải tiến được đề xuất tại chương 4. VI. TÓM TẮT LUẬN ÁN Chương 1. Giới thiệu tổng quan 1.1 Sự phát triển của mạng di động tế bào Mạng thông tin di động tế bào đã trải qua 3 thế hệ: 1G, 2-2.5G và 3G. Hệ thống thế hệ thứ nhất 1G là các hệ thống di động tương tự, được thiết kế để truyền tải thoại. Thế hệ 2 (2-2.5G) sử dụng công nghệ số. Hệ thống thế hệ 3 (3G) đáp ứng đáng kể phần thiếu hụt của các tiêu chuẩn thế hệ hai hiện có, cả về loại hình dịch vụ và tốc độ truy nhập. Hệ thống di động số hiện tại được thiết kế tối ưu cho thông tin thoại, trong khi đó hệ thống 3G chú trọng đến khả năng truyền thông đa phương tiện. 1.2 Cấp phát kênh và tái sử dụng kênh Khái niệm tế bào Khái niệm tế bào xuất phát từ các hệ thống mạng của Bell theo chuẩn AMPS năm 1979, đó là một kiến trúc mạng được tổ hợp từ các ô hình lục lăng (Hình 1.1-a). Mỗi ô có một trạm gốc cung cấp các kênh tần số cho các thiết bị di động. Trạm gốc trong AMPS được coi là một ô. Mỗi ô được liên kết với trung tâm chuyển mạch MSC có vai trò điều khiển các cuộc gọi, hoạt động như một cổng để kết nối với mạng khác. Hình 1.1: a) Kiến trúc mạng di động b) Nhóm compact gồm 7 ô, i=2,j=1 Bắt đầu từ bất kỳ ô nào, di chuyển i ô theo hướng bất kỳ một trong sáu hình lục lăng bên cạnh của ô đó, đổi hướng ngược chiều kim đồng hồ 60 độ và di chuyển j ô (Hình 1-b). Ô đích là ô đồng kênh gần nhất với ô ban đầu. Đối với mỗi ô, có hai tập hợp của 6 ô đồng kênh gần nhất, tuỳ thuộc vào việc di chuyển theo chiều kim đồng hồ và ngược chiều kim đồng hồ. Bằng cách lặp lại mô hình này, các cụm các ô được hình thành, trong đó mỗi ô được biểu diễn tập hợp các kênh tần số khác nhau. Một cụm các 4 ô như vậy được gọi là một tổ hợp ô cố định (compact pattern). Số ô trong một tổ hợp ô cố định được tính bởi công thức N=i2 + ij + j2. Cấp phát kênh Phổ tần số được chia thành tập các kênh vô tuyến riêng biệt. Để chia phổ tần số thành các kênh như vậy, nhiều kỹ thuật như phân chia theo tần số (FD), phân chia theo thời gian (TD), hoặc phân chia theo mã (CD) được sử dụng. Trong FD, phổ tần số được chia thành các băng tần riêng biệt, trong khi đó ở TD mỗi một cuộc gọi được phát trên tần số chung nhưng theo các khoảng thời gian khác nhau. Khoảng thời gian này đủ bé để người sử dụng không thấy có sự rời rạc khi nghe người khác nói. Trong CD, các kênh được phân biệt nhờ sử dụng các thuật toán điều chế theo mã khác nhau. Tái sử dụng kênh Coi Si (k) là tập thứ i các thuê bao mà có thể liên lạc với nhau bằng việc cùng sử dụng tần số k. Do những đặc tính vật lý của môi trường song vô tuyến, cũng tần số k này có thể được tái sử dụng đồng thời bởi tập thứ j khác nếu thuê bao của tập i và j cách nhau một khoảng đáng kể. Tất cả các thuê bao mà sử dụng cùng tần số như vậy được coi là các tập đồng kênh hoặc gọi theo cách đơn giản là đồng kênh. Khoảng cách nhỏ nhất mà các tập đồng kênh có thể được tái sử dụng với nhiễu gây ra có thể chấp nhận được gọi là “khoảng cách tái sử dụng đồng kênh”. Khoảng cách nhỏ nhất đảm bảo rằng mức tỉ số tín hiệu trên nhiễu (SIR) ở mỗi tập đồng kênh lớn hơn một ngưỡng xác định (SIRmin). 1.3 Đánh giá hiệu suất thuật toán cấp phát kênh Hiệu suất (performance) là khái niệm tổng quát xác định chất lượng hoạt động của một hệ thống - xét từ góc độ của người sử dụng - về độ sẵn sàng (availability), tính hiệu quả (effectivity), độ tin cậy (reliability) và độ an toàn (security) của hệ thống đó. Có 3 phương pháp đánh giá hiệu suất: a) Mô hình hóa sử dụng các công cụ toán học, còn gọi là mô hình hóa giải tích (analytical modeling); b) Mô hình hóa sử dụng chương trình máy tính (simulative modeling); và c) Đo thực tế (Measurement). Trong mạng di động tế bào, một số độ đo hiệu suất quan trọng là: (a) Ở mức cuộc gọi: xác suất từ chối cuộc gọi, xác suất rớt cuộc gọi, thời gian trễ cho thiết lập cuộc gọi, thời gian trễ chuyển giao, … (b) Ở mức tín hiệu: cường độ tín hiệu thu được, nhiễu xuyên kênh, tỷ suất sóng mang - nhiễu trên tạp âm CIR, Trong khuôn khổ luận văn, độ đo hiệu suất ở mức cuộc gọi được xác định là yếu tố chính đánh giá hiệu quả hoạt động của các thuật toán cấp phát kênh trong mạng di động tế bào. Ngoài ra, một số độ đo khác được sử dụng trong quá trình phân tích, đánh giá, so sánh và cải tiến các thuật toán cấp phát kênh là: (a) Số kênh cần cấp phát (lớn nhất) của các thuê bao được đáp ứng; (b) Số ô đồng kênh phải khóa (nhỏ nhất) khi thực hiện cấp 5 phát kênh; (c) (Tăng cường) khả năng tham gia cấp phát kênh của các ô lân cận của ô có nhu cầu cấp phát kênh; (d) Thứ tự ưu tiên cấp phát kênh (để làm giảm xác suất rớt cuộc gọi). Chương 2. Các thuật toán cấp phát kênh 2.1 Tổng quan về các thuật toán cấp phát kênh Có 3 nhóm thuật toán cấp phát kênh chính sau đây: a) Cấp phát kênh cố định FCA (Fixed Channel Allocation); b) Cấp phát kênh động DCA (Dynamic Channel Allocation); và c) Cấp phát kênh lai HCA (Hybrid Channel Allocation). 2.2 Các thuật toán cấp phát kênh cố định FCA [2, 5]. Trong cấp phát kênh cố định FCA, các ô được thiết lập và các kênh được gán cố định cho vị trí các ô; các tập kênh tần số này sẽ không thay đổi trừ khi cần cấu hình lại cho một giai đoạn mới. Các ô sẽ chỉ sử dụng tập kênh đã được gán. 2.3 Các thuật toán cấp phát kênh động DCA [5, 8, 9, 10]. Trong DCA, các kênh rỗi được lưu giữ tập trung tại một trung tâm (central pool). Khi có một yêu cầu kênh từ một trạm gốc, MSC chọn kênh thích hợp mà cho hiệu quả cao nhất có tính đến các ràng buộc về nhiễu tín hiệu. Các kênh được gán trong suốt thời gian diễn ra cuộc gọi, sau khi cuộc gọi kết thúc, kênh được trả lại cho trung tâm hoặc tái cấp phát cho thuê bao trong cùng ô mà đã điều khiển kênh này trước đó. 2.4 Các thuật toán cấp phát kênh lai HCA Các thuật toán cấp phát kênh lai HCA là sự kết hợp giữa FCA và DCA. Trong HCA, tổng số kênh rỗi được phân chia thành tập hợp các kênh cố định và tập hợp các kênh động. Tập hợp các kênh cố định được ưu tiên gán cho các yêu cầu theo thuật toán FCA trong mọi trường hợp. Tập hợp các kênh động được gán cho tất cả các yêu cầu cấp phát kênh trong hệ thống. Khi có một yêu cầu cấp phát kênh và các kênh thuộc tập hợp kênh cố định không còn kênh nào rỗi thì kênh rỗi thuộc tập hợp kênh động sẽ được gán cho yêu cầu đó tuân thủ bất cứ thuật toán cấp phát kênh động cụ thể nào đó. 2.5 Đánh giá, so sánh FCA và DCA [3] FCA DCA
Hiệu quả hơn khi tải lưu lượng lớn
Không mềm dẻo trong cấp phát kênh
Phản ứng nhạy cảm với thời gian và sự thay đổi thành phần của tải
Tỷ suất buộc kết thúc cuộc gọi cao
Hiệu quả hơn khi tải lưu lượng nhỏ
Mềm dẻo trong cấp phát kênh
Mức độ tái sử dụng kênh không luôn luôn là cao nhất
Tỷ suất buộc kết thúc cuộc gọi thấp 6
Độ phức tạp tính toán thấp
Độ trễ thiết lập cuộc gọi thấp
Độ phức tạp thực hiện thấp
Tải điều khiển báo hiệu thấp
Thực hiện điều khiển tập trung
Độ phức tạp tính toán cao
Độ trễ thiết lập cuộc gọi từ trung bình đến cao
Độ phức tạp thực hiện từ trung bình đến cao
Tải điều khiển báo hiệu từ trung bình đến cao
Thực hiện điều khiển tập trung, không tập trung, phân tán phụ thuộc vào thuật toán cụ thể 2.6 Kết luận Các thuật toán DCA thực hiện tốt hơn trong trường hợp mật độ lưu lượng thấp. Các thuật toán FCA cải tiến có hiệu suất cao hơn trong trường hợp tải lưu lượng lớn. Các thuật toán DCA sử dụng kênh hiệu quả hơn và đối với cùng tỉ lệ khóa kênh, các cuộc gọi buộc phải chấm dứt (rớt cuộc gọi) của thuật toán DCA thấp hơn so với các thuật toán FCA cơ bản. Tuy nhiên, cấp phát kênh gần tối ưu đòi hỏi thông tin cần trao đổi rất lớn vì sử dụng các thuật toán cấp phát tập trung. Điều đó có nghĩa là các thuật toán này không thích hợp đối với các mạng lớn. Các thuật toán DCA phân tán với việc hạn chế truyền thông giữa các ô đã làm thông tin trao đổi giảm đi nhưng lại dẫn đến hiệu suất cấp phát giảm. Các thuật toán này được đề suất cho các hệ thống tế bào ô nhỏ vì cấu trúc ô cho phép chia sẻ thông tin giữa các ô bị ảnh hưởng bởi nhiễu ít và không phải chịu giám sát tại mỗi trạm gốc. Đối với các hệ thống ô lớn, thuật toán FCA với mượn kênh cho kết quả tốt và độ phức tạp tính toán thấp hơn DCA. Tuy nhiên, các thuật toán FCA này lại áp dụng việc điều khiển tập trung tại MSC, mặc dù chúng kém phức tạp hơn các thuật toán DCA nhưng vẫn cần thiết duy trì việc cập nhật thông tin trên toàn mạng di động dẫn đến việc phản hồi chậm và tải tín hiệu lớn. Chương 3. Thuật toán cân bằng tải động với mượn kênh chọn lọc và phiên bản cải tiến 3.1 Thuật toán cân bằng tải động với mượn kênh chọn lọc Mô hình hệ thống và giả thiết a) Xác định nhóm compact Mỗi ô được cấp phát một tập kênh C, tập kênh này lại được tái sử dụng trong ô khác với khoảng cách đủ để nhiễu đồng kênh gây ra là không đáng kể (khoảng cách tái sử dụng đồng kênh). Hai tham số i và j được gọi là các tham số shift: bắt đầu từ bất kỳ ô nào, di chuyển i ô theo hướng bất kỳ một trong sáu hình lục lăng bên cạnh của ô đó, đổi hướng ngược chiều kim đồng hồ 60 độ và di chuyển j ô; ô đích là ô đồng kênh gần nhất với ô ban đầu. Bằng cách lặp lại mô hình này, các cụm các ô được hình thành, trong đó mỗi ô được cấp phát tập hợp các kênh khác nhau. Một cụm các ô 7 như vậy được gọi là một nhóm Compact; số ô trong nhóm Compact tính bởi công thức N=i2 + ij + j2 [4]. b) Phân lớp ô Mỗi ô được cấp phát một tập C kênh; một ô được phân lớp là nóng hoặc lạnh phụ thuộc vào độ lạnh dc của nó được xác định bởi tỉ số giữa số kênh rỗi và C, dc= số kênh rỗi/C. Nếu dc nhỏ hơn hoặc bằng một ngưỡng xác định h thì đó là ô nóng, ngược lại sẽ là ô lạnh. Việc xác định h phụ thuộc vào trung bình các cuộc gọi đến và tỉ lệ các cuộc gọi bị chấm dứt của toàn mạng. c) Phân lớp thuê bao trong ô Thuê bao trong ô được phân lớp thành một trong 3 loại: mới, rời ô hoặc khác. Thuê bao là mới nếu nó ở trong ô trong nhỏ hơn một khoảng thời gian τ. Thuê bao rời ô là thuê bao bên trong vùng bóng và đang nhận cường độ tín hiệu giảm dần từ trạm gốc của ô A trong khoảng thời gian cuối cùng ∝. Thuê bao không phải là mới hoặc rời ô sẽ được phân thành lớp khác. Cơ chế cân bằng tải động a) Nguyên tắc hoạt động Một ô lạnh không thể mượn kênh và tương tự, ô nóng không thể cho mượn kênh. Các thuê bao rời ô nóng có thứ tự ưu tiên cao nhất trong việc mượn kênh. Khi một ô trở nên nóng và cần phải mượn kênh, kênh được mượn từ các ô lạnh và được lưu trong tập kênh có sẵn của ô mượn gọi là tập kênh mượn, trong những điều kiện nhất định, các kênh này được tái gán cho các thuê bao rời ô và kênh mà thuê bao rời ô đã sử dụng trước đây sẽ được trả lại cho tập kênh có sẵn của ô, do vậy tập kênh của ô nóng luôn được cập nhật bổ sung. Khi một kênh đã được một ô lạnh mượn, để tránh nhiễu đồng kênh với ô mượn thì kênh này phải bị khoá không chỉ ở ô cho mượn mà còn ở các ô đồng kênh của ô cho mượn mà không đồng kênh với ô mượn. b) Cơ chế mượn kênh - Điều kiện mượn kênh: Một ô nóng chỉ mượn kênh từ các ô lạnh thích hợp trong nhóm compact của nó. Có 3 tham số xác định mức độ thích hợp của một ô lạnh L để cho mượn kênh: a) Độ lạnh dc(L): Tỉ số giữa kênh rỗi của ô L trên tổng số kênh đã cấp phát cho ô L. Ô càng lạnh càng thích hợp trong việc cho mượn kênh. b) Gần D(B,L): Khoảng cách giữa ô mượn kênh B và ô cho mượn L. c) Ô nóng đồng kênh H(B,L): Số ô nóng đồng kênh với ô cho mượn kênh L mà không đồng kênh với ô mượn B. - Tiêu chuẩn mượn kênh: Ô L là ô có khả năng cho mượn tốt nhất nếu hàm F(B,L) của nó đạt giá trị lớn nhất. - Xác định số kênh cần mượn: Độ lạnh trung bình của mạng ký hiệu là dc avr được tính bằng trung bình cộng của độ lạnh của tất cả các ô dc một 8 cách định kỳ. Giả sử số lượng kênh rỗi trong ô nóng là h.C; X là số lượng kênh mà nó cần mượn từ các ô lạnh được xác định như sau: X= C.(dc avr - h) c) Thuật toán mượn kênh (1) Khởi tạo: MSC gửi các bản tin yêu cầu đến các trạm BTS để thu thập và tính toán các thông số cần thiết. - Tại MSC: tính các thông số H[i,j], dc, h, X; - Tại các BTS: sử dụng các tham số C, p, dc, h để tính thông số r; mỗi ô nóng tính giá trị NumDepart[i]. (2) Nhận giá trị NumDepart[i]. (3) Lựa chọn các ô lạnh lân cận có giá trị NumDepart[i] khác 0; sắp xếp các ô theo thứ tự giảm dần của giá trị F(B,L). (4) Với mỗi ô trong danh sách trên, thực hiện mượn kênh cho đến khi số kênh mượn bằng NumDepart[i]; khóa kênh cho mượn ở các ô đồng kênh với L nhưng không đồng kênh với B. (5) Thực hiện bước (4) cho đến khi số kênh cần mượn được mượn đủ. (6) Tính F(B,L) cho tất cả các ô lạnh còn lại trong tổ hợp ô cố định, nghĩa là trừ các ô lạnh đã xử lý trong các bước (3), (4), (5). (7) Mượn kênh ở ô có giá trị F(B,L) lớn nhất; khóa kênh cho mượn ở các ô đồng kênh với L nhưng không đồng kênh với B; tính lại F(B,L) với giá trị mới dc. (8) Thực hiện bước (7) cho đến khi số kênh cần mượn được mượn đủ. d) Thuật toán tái gán kênh Thuật toán gán kênh ưu tiên các yêu cầu (cấp phát) kênh dựa theo lớp mà chúng thuộc vào. Có 4 lớp yêu cầu kênh: - Lớp 1 là các yêu cầu chuyển giao từ các thuê bao đi qua vùng biên của các ô. Có mức ưu tiên cao nhất để nhận kênh. - Lớp 2 là các yêu cầu kênh phục vụ thiết lập cuộc gọi; có mức ưu tiên thứ 2. - Lớp 3 là các yêu cầu dành cho tái gán kênh. Có 2 kiểu tái gán kênh: a) kiểu 1 là việc tái gán một kênh địa phươ