On the span in channel assignment problems: bounds, computing and counting
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
New Citation Alert!
Please log in to your account
Information & Contributors
Bibliometrics & citations, view options.
- Socała A (2016) Tight Lower Bound for the Channel Assignment Problem ACM Transactions on Algorithms 10.1145/2876505 12 :4 (1-19) Online publication date: 2-Sep-2016 https://dl.acm.org/doi/10.1145/2876505
- Kowalik L Socała A (2016) Assigning Channels Via the Meet-in-the-Middle Approach Algorithmica 10.1007/s00453-015-0004-z 74 :4 (1435-1452) Online publication date: 1-Apr-2016 https://dl.acm.org/doi/10.1007/s00453-015-0004-z
- Socała A Indyk P (2015) Tight lower bound for the channel assignment problem Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms 10.5555/2722129.2722174 (662-675) Online publication date: 4-Jan-2015 https://dl.acm.org/doi/10.5555/2722129.2722174
- Show More Cited By
Index Terms
Mathematics of computing
Discrete mathematics
Graph theory
Graph algorithms
Graph enumeration
Theory of computation
Randomness, geometry and discrete structures
Recommendations
The minimum span of l(2,1)-labelings of certain generalized petersen graphs.
In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be ...
Channel assignment problem and relaxed 2-distant coloring of graphs
Let G be a simple graph. Suppose f is a mapping from V ( G ) to nonnegative integers. If, for any two adjacent vertices u and v of G, | f ( u ) − f ( v ) | ≥ 2, then f is called a 2-distant coloring of G. In this paper, we introduce a ...
Anti-Ramsey numbers for matchings in 3-regular bipartite graphs
The anti-Ramsey number AR(Kn, H) was introduced by Erdźs, Simonovits and Sós in 1973, which is defined to be the maximum number of colors in an edge coloring of the complete graph Kn without any rainbow H. Later, the anti-Ramsey numbers for several ...
Information
Published in.
Elsevier Science Publishers B. V.
Netherlands
Publication History
Contributors, other metrics, bibliometrics, article metrics.
- 13 Total Citations View Citations
- 0 Total Downloads
- Downloads (Last 12 months) 0
- Downloads (Last 6 weeks) 0
- Obata Y Nishizeki T (2015) Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs Theoretical Computer Science 10.1016/j.tcs.2015.07.052 607 :P2 (208-220) Online publication date: 23-Nov-2015 https://dl.acm.org/doi/10.1016/j.tcs.2015.07.052
- Cerioli M Posner D (2012) On L(2,1)-coloring split, chordal bipartite, and weakly chordal graphs Discrete Applied Mathematics 10.1016/j.dam.2012.03.018 160 :18 (2655-2661) Online publication date: 1-Dec-2012 https://dl.acm.org/doi/10.1016/j.dam.2012.03.018
- Cygan M Kowalik Ł (2011) Channel assignment via fast zeta transform Information Processing Letters 10.1016/j.ipl.2011.05.008 111 :15 (727-730) Online publication date: 1-Aug-2011 https://dl.acm.org/doi/10.1016/j.ipl.2011.05.008
- Král' D Nejedlý P (2009) Distance constrained labelings of K4 -minor free graphs Discrete Mathematics 10.1016/j.disc.2008.05.022 309 :18 (5745-5756) Online publication date: 1-Sep-2009 https://dl.acm.org/doi/10.1016/j.disc.2008.05.022
- Griggs J Král' D (2009) Graph labellings with variable weights, a survey Discrete Applied Mathematics 10.1016/j.dam.2008.08.024 157 :12 (2646-2658) Online publication date: 1-Jun-2009 https://dl.acm.org/doi/10.1016/j.dam.2008.08.024
- Dvořák Z Král' D Nejedlý P Škrekovski R (2009) Distance constrained labelings of planar graphs with no short cycles Discrete Applied Mathematics 10.1016/j.dam.2008.08.013 157 :12 (2634-2645) Online publication date: 1-Jun-2009 https://dl.acm.org/doi/10.1016/j.dam.2008.08.013
- Gonçalves D (2008) On the L(p,1)-labelling of graphs Discrete Mathematics 10.1016/j.disc.2007.07.075 308 :8 (1405-1414) Online publication date: 1-Apr-2008 https://dl.acm.org/doi/10.1016/j.disc.2007.07.075
View options
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Share this publication link.
Copying failed.
Share on social media
Affiliations, export citations.
- Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
- Download citation
- Copy citation
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
Channel Assignment Techniques
Cite this chapter.
- Gordon L. Stüber 2
284 Accesses
First generation macrocellular systems typically use fixed channel assignment (FCA), where disjoint subsets of the available channels are permanently allocated to the cells in advance according to their estimated traffic loads. The cells are arranged in tessellating reuse clusters whose size is determined by the co-channel reuse constraint. For example, the North American AMPS system typically uses a 7-cell reuse cluster with 120° sectoring. The 12.5 MHz bandwidth allocation for AMPS can support a total of 416 two-way channels, 21 of which are control channels (one for each sector in a cluster), leaving a total of 395 traffic channels. This yields an allocation of 56 channels/cell with uniform FCA.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
Author information
Authors and affiliations.
Georgia Institute of Technology, USA
Gordon L. Stüber
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
Copyright information
© 1996 Springer Science+Business Media New York
About this chapter
Stüber, G.L. (1996). Channel Assignment Techniques. In: Principles of Mobile Communication. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-6268-6_11
Download citation
DOI : https://doi.org/10.1007/978-1-4757-6268-6_11
Publisher Name : Springer, Boston, MA
Print ISBN : 978-1-4757-6270-9
Online ISBN : 978-1-4757-6268-6
eBook Packages : Springer Book Archive
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
- Engineering Mathematics
- Discrete Mathematics
- Operating System
- Computer Networks
- Digital Logic and Design
- C Programming
- Data Structures
- Theory of Computation
- Compiler Design
- Computer Org and Architecture
Channel Allocation Problem in Computer Network
Channel allocation is a process in which a single channel is divided and allotted to multiple users in order to carry user specific tasks. There are user’s quantity may vary every time the process takes place. If there are N number of users and channel is divided into N equal-sized sub channels, Each user is assigned one portion. If the number of users are small and don’t vary at times, then Frequency Division Multiplexing can be used as it is a simple and efficient channel bandwidth allocating technique.
Channel allocation problem can be solved by two schemes: Static Channel Allocation in LANs and MANs, and Dynamic Channel Allocation.
These are explained as following below.
1. Static Channel Allocation in LANs and MANs: It is the classical or traditional approach of allocating a single channel among multiple competing users using Frequency Division Multiplexing (FDM) . if there are N users, the frequency channel is divided into N equal sized portions (bandwidth), each user being assigned one portion. since each user has a private frequency band, there is no interference between users.
However, it is not suitable in case of a large number of users with variable bandwidth requirements. It is not efficient to divide into fixed number of chunks.
2. Dynamic Channel Allocation:
In dynamic channel allocation scheme, frequency bands are not permanently assigned to the users. Instead channels are allotted to users dynamically as needed, from a central pool. The allocation is done considering a number of parameters so that transmission interference is minimized.
This allocation scheme optimises bandwidth usage and results is faster transmissions.
Dynamic channel allocation is further divided into:
- Centralised Allocation
- Distributed Allocation
Possible assumptions include:
Station Model:
Assumes that each of N stations independently produce frames. The probability of producing a packet in the interval IDt where I is the constant arrival rate of new frames.
Single Channel Assumption:
In this allocation all stations are equivalent and can send and receive on that channel.
Collision Assumption:
If two frames overlap in time-wise, then that’s collision. Any collision is an error, and both frames must re transmitted. Collisions are only possible error.
Time can be divided into Slotted or Continuous.
Stations can sense a channel is busy before they try it. Protocol Assumption:
- N independent stations.
- A station is blocked until its generated frame is transmitted.
- probability of a frame being generated in a period of length Dt is IDt where I is the arrival rate of frames.
- Only a single Channel available.
- Time can be either: Continuous or slotted.
- Carrier Sense: A station can sense if a channel is already busy before transmission.
- No Carrier Sense: Time out used to sense loss data.
Similar Reads
Please login to comment....
- How to Underline in Discord
- How to Block Someone on Discord
- How to Report Someone on Discord
- How to add Bots to Discord Servers
- GeeksforGeeks Practice - Leading Online Coding Platform
Improve your Coding Skills with Practice
What kind of Experience do you want to share?
share this!
September 24, 2024
This article has been reviewed according to Science X's editorial process and policies . Editors have highlighted the following attributes while ensuring the content's credibility:
fact-checked
trusted source
Channel conveyance and flood risk: Are current models missing the mark?
by Geological Society of America
River floods are environmental hazards that can have devastating effects on human life, agriculture, and infrastructure. Hydrologic models are used to map flood hazards to better understand risk, dictate insurance costs, and inform land-use planning. However, new research being presented Wednesday at the Geological Society of America's GSA Connects 2024 meeting suggests that these models may be missing a key variable that could underestimate risk.
Channel conveyance—or the volume of water a river channel can hold in its banks—is calculated by measuring the depth and width of a river channel. Most hydrologic models assume that channel conveyance is constant, but this is based on periodic measurements that can be taken decades apart.
Brooke Santos, the presenter, questioned the consistency of channel conveyance and worked with the Yanites' Research Group at Indiana University (IU) to better understand the relationship between channel conveyance and flood hazards.
The team collected aerial images and used structure from motion photogrammetry to make 3D reconstructions of river landscapes before, immediately after, and six years following Typhoon Morakot, Taiwan's deadliest recorded typhoon. Santos measured channels at each interval and identified up to 10 m of sediment deposition in rivers immediately following the typhoon.
"There's a thought that flooding incises, or removes, the sediment in a channel, but we're seeing that floods actually deposit a significant amount of sediment into these channels," says Santos. "This increased sediment will impact channel conveyance because it changes the river's depth."
Santos then used the reconstructions as a base for hydrologic models to create maps of flood risks for each interval at varying flood intensities. She found that the landscapes following Typhoon Morakot had a greater flood area, and these results suggest that changes in channel conveyance can result in an increased area of hazard.
Although this research was conducted in Taiwan, Santos notes that their results can be applicable to many areas as changes in channel conveyance have been measured globally.
"Debris flows, earthquakes, large precipitation events, and other processes that result in an influx of sediment into a river system can change channel conveyance and impact flood hazards," according to Santos.
"It's important to include these changes in our models, especially as climate change can increase the frequency and severity of flooding."
Provided by Geological Society of America
Explore further
Feedback to editors
Extreme botany: Paramotorists soar across remote Peru desert to collect threatened plants
4 hours ago
New insights into hot carrier solar cells: Study explores hot electron tunneling and collection to enhance efficiency
6 hours ago
Atmospheric methane increase during pandemic due primarily to wetland flooding, satellite data analysis finds
7 hours ago
Thermal effects in spintronics systematically assessed for first time
Maintaining an essential habitat: What's good for pollinators is good for utility companies too
8 hours ago
AI network shows potential for predicting crop yield
9 hours ago
Atmospheric blocking slows ocean-driven melting of Greenland's largest glacier tongue
Fruit-only diet found to improve bats' immune response to viruses
Graphene spike mat uses ordinary fridge magnet tech to fight antibiotic resistance
11 hours ago
1,000-year-old textiles reveal cultural resilience in the ancient Andes
Relevant physicsforums posts, the secrets of prof. verschure's rosetta stones.
Sep 19, 2024
Why does crude oil seep out of the ground on this beautiful Caribbean Island?
Sep 7, 2024
Should We Be Planting More Trees?
Alaska - pedersen glacier: landslide triggered tsunami.
Aug 23, 2024
Iceland warming up again - quakes swarming
Shiveluch volcano erupts on kamchatka peninsula.
Aug 18, 2024
More from Earth Sciences
Related Stories
Research suggests watershed scale determines timing of flood in mountainous river regardless of topography
Jul 1, 2024
New insight into river flows and sediment transport under ice cover
Feb 20, 2019
Rivers are changing all the time, and it affects their capacity to contain floods
Nov 12, 2019
Earthquakes can change the course of rivers—with devastating results. We may now be able to predict these threats
May 30, 2023
Traditional infrastructure design often makes extreme flooding events worse, researchers find
Sep 4, 2024
Scientists identify how the dissection of Arctic landscapes is changing with accelerating climate change
Sep 12, 2023
Recommended for you
Climate models predict abrupt intensification of northern wildfires due to permafrost thawing
12 hours ago
Tropical and subtropical industrial fisheries account for about 70% of methylmercury fished from the ocean: Study
Understanding Antarctica's contribution to sea level rise
13 hours ago
Extinct volcanoes a 'rich' source of rare earth elements, research suggests
Let us know if there is a problem with our content.
Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form . For general feedback, use the public comments section below (please adhere to guidelines ).
Please select the most appropriate category to facilitate processing of your request
Thank you for taking time to provide your feedback to the editors.
Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.
E-mail the story
Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient's address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Phys.org in any form.
Newsletter sign up
Get weekly and/or daily updates delivered to your inbox. You can unsubscribe at any time and we'll never share your details to third parties.
More information Privacy policy
Donate and enjoy an ad-free experience
We keep our content available to everyone. Consider supporting Science X's mission by getting a premium account.
E-mail newsletter
IEEE Account
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
IMAGES
VIDEO
COMMENTS
The channel assignment problem between sender and receiver can be easily transformed into Maximum Bipartite Matching(MBP) problem that can be solved by converting it into a flow network. Step 1: Build a Flow Network . There must be a source and sink in a flow network. So we add a dummy source and add edges from source to all senders.
An optimization problem exists in the context of local area network security. The network provides a number of physical or logical "channels", each carrying a set of levels or compartments of information. A channel is accessible to users cleared for all the levels it carries. The problem is to assign the set of levels to be carried by each channel so as to minimize the total number of channels ...
A channel assignment problem is a triple (V, E, w) where V is a vertex set, E is an edge set and w is a function assigning edges positive integer weights. An assignment c of integers between 1 and K to the vertices is proper if | c (u)-c (v) | ⩾ w (uv) for each uv ∈ E; the smallest K for which there is a proper assignment is called the span. The input problem is set to be l-bounded if the ...
The task of assigning frequency channels to the cells satisfying the interference constraints and using as small bandwidth as possible is known as the channel assignment problem (CAP). In its most general form, the CAP is equivalent to the generalized graph-coloring which is a well-known NP-complete problem [10--12].
In its simplest (and most unrealistic) form, the channel assignment problem is equivalent to the Euclidean graph coloring problem, hence it is NP-hard. This problem can be treated with simple greedy heuristics [5] [3] [1]. Be-cause a server station must communicate with several mobile hosts at once, however, we must assign more than
The λ‐function λ G ( x 1, …, x k) is the infimum of the spans of all the proper labelings with respect to x 1, …, x k. We show that the λ‐function of any graph G is piecewise linear in x 1, …, x k with finitely many linear parts (unless the λ‐function is infinite). Moreover, we show that for all integers k and χ, there exist ...
Dynamic channel assignment (DCA) is one well-known solution to the microcellular channel assignment problem, where the dynamic nature of the strategy permits adaptation to spatial and temporal traffic variations while the distribution of control reduces the required computation and communication among base stations (BSs), thereby reducing system latencies.
3-CNF-SAT O(n)! Family Intersection O(n)! Common Matching Weight O n logn ! Channel Assignment O n logn Figure 1: The sequence of the used reductions and the size of the instance.
The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. We consider a standard model for channel assignment, the constraint matrix model, which extends ideas of graph colouring. Given a graph G=(V,E) and a length l(uv) for each edge uv of G, we ...
With the rapid growth of mobile communications, solving the channel assignment problem has now become a new challenge in research. In this paper, we present the channel assignment problem (CAP) from a multi-objective approach. From this new idea, the communication system can be easily managed in case of an unexpected rise in demand in some particular cells. We carry out the experiments with ...
A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\\in L(v)$ for each vertex v and $|c(u)-c(v)|\\ge w(uv)$ for each edge uv. A weighted degree $\\deg_w(v ...
Since, channel assignment problem has been shown to be an NP-hard problem. Also, it is shown that the channel assignment problem is very similar to the graph k-colorability problem. But Graph k-Colorability (for k ≥ 3) Problem (GCP) is a well known NP-Complete problem. There are many approaches has been proposed to solve graph k-colorability ...
The multiple t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling is an appreciated model for channel assignment problem in mobile communications systems.It is also a natural generalization of multiple graph coloring problem. This paper is devoted to solve some special cases of channel assignment problem as well as to extend the theory of multiple coloring to n-fold t-separated L(j)-labeling.
Channel Assignment Techniques 557 problems, including service interruption, deadlock, and instability. A service interruption occurs when a channel allocation causes an existing link to fall below the threshold CII. The interrupted mobile station (MS) then tries to find an alternate link and if unsuccessful a service termination occurs. ...
Channel Allocation Problem in Computer Network. Channel allocation is a process in which a single channel is divided and allotted to multiple users in order to carry user specific tasks. There are user's quantity may vary every time the process takes place. If there are N number of users and channel is divided into N equal-sized sub channels ...
A survey on the channel assignment problem in wireless networks. Goutam K. Audhya, Goutam K. Audhya. BSNL, Calcutta 700001, India ... present a discussion on the various challenges and approaches that have been used by different researchers to solve the problem of channel allocation taking into account different interference issues and ...
The increased usage of mobile devices and the scarce, regulated radio resources in wireless networks present a challenge to efficiently allocate channels to users. Existing algorithms designed to assign channels in a network range from dynamic channel allocation (DCA) algorithms to fixed channel allocation (FCA) algorithms - each with their own advantages and drawbacks. In this paper, we ...
More specifically, we apply Lagrangian decomposition to decompose the main problem into two Open Vehicle Routing Problems (OVRPs) and one Assignment Problem (AP). In the OVRP, a vehicle does not return to the depot after serving the last customer on the route, or likewise the return trip to the depot is not charged ( Li et al. 2007 ; Irnich et ...
Generally, the channel assignment problem (CAP) for mobile cellular systems is solved by graph coloring algorithms. These algorithms, though sometimes yielding optimal solutions, do not supply any information on how far away it is from the optimum or for which situations an optimal solution can be found. In view of these undesirable features, two relevant results are presented in the paper ...
Got it. Channel allocation is a process in which a single channel is divided and allotted to multiple users in order to carry user specific tasks. There are user's quantity may vary every time the process takes place. If there are N number of users and channel is divided into N equal-sized sub channels, Each user is assigned one portion.
Channel conveyance—or the volume of water a river channel can hold in its banks—is calculated by measuring the depth and width of a river channel. ... Let us know if there is a problem with ...
The channel assignment problem in its most general form is NP-complete. Prior studies assume that the graph modelling the cellular network is an arbitrary graph. However, we show that the graph modelling the cellular network has a very regular structure and exploiting this regular structure, the channel assignment problem can be solved ...